Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$

Discrete random variables

Ta thường không quan tâm đến thí nghiệm mà chỉ quan tâm đến một số hệ quả từ thí nghiệm đó. Chẳng hạn, những tay cờ bạc chỉ quan tâm đến số tiền họ được hay mất, không quan tâm mấy đến trò chơi. Nhiều hệ quả từ thí nghiệm có thể được biểu diễn bằng một hàm trên không gian mẫu của thí nghiệm.

Định nghĩa 1. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ . Một biến ngẫu nhiên là một hàm $X:\Omega\to\mathbb{R}$ sao cho với mỗi $x\in\mathbb{R}$ , $\{\omega\in\Omega\mid X(\omega)\leq x\}\in\mathcal{F}.$

Một biến ngẫu nhiên được gọi là rời rạc nếu nó chỉ nhận giá trị trong một tập hợp đếm được.

Không khó khăn lắm để thấy rằng nếu $X$ và $Y$ là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc) thì $X+Y$ , $XY$ , và $\alpha X$ ( $\alpha\in\mathbb{R}$ ) cũng là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc).

Định nghĩa 2. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến ngẫu nhiên $X:\Omega\to\mathbb{R}$ . Hàm phân bố của biến ngẫu nhiên $X$ là hàm $F_X:\mathbb{R}\to [0;1]$ xác định bởi

$F_X(x)=\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\}),\quad\forall x\in\mathbb{R}.$

Để cho gọn, ta viết sự kiện $\{\omega\in\Omega\mid X(\omega)\leq x\}$ bởi $\{ X\leq x\}$ . Khi đó xác suất $\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\})$ sẽ được viết là $\mathbb{P}( X\leq x)$ .

Ví dụ 1. Tung một đồng xu hai lần. Không gian mẫu của phép thử là $\Omega =\{NN,SS,SN,NS\}$ . Xét biến ngẫu nhiên $X$ , số mặt ngửa, xác định bởi

$X(NN)=2, X(SS)=0, X(SN)=1, X(NS)=1.$

Hàm phân bố của $F_X:\mathbb{R}\to [0;1]$ của $X$ xác định bởi

$F_X(x)=\begin{cases}0,\quad x<0\\ 1/4,\quad 0\leq x<1\\ 3/4,\quad 1\leq x<2\\ 1,\quad x\geq 2.\end{cases}$

Ví dụ 2. Xét không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến cố $A$ . Hàm chỉ báo của $A$ là hàm $I_A: \Omega\to \mathbb{R}$ xác định bởi

$I_A(\omega)=\begin{cases}1,\quad \omega\in A\\ 0,\quad \omega\not\in A.\end{cases}$

Ta thấy $I_A$ là một biến ngẫu nhiên rời rạc với hàm phân bố $F:\mathbb{R}\to [0;1]$ xác định bởi

$F(x)=\begin{cases}0,\quad x<0\\ 1-\mathbb{P}(A),\quad 0\leq x<1\\ 1,\quad x\geq 1. \end{cases}$

Nếu $\{A_i\}_{i\in I}$ là một họ các biến cố đôi một rời nhau sao cho $\displaystyle A\subset \bigcup_{i\in I} A_i$ thì

$I_A(\omega)=\sum_{i\in I}I_{A\cap A_i}(\omega),\quad \forall \omega\in \Omega.$ $\Box$

Định lý 1. Hàm phân bố $F_X$ của biến ngẫu nhiên $X$ có các tính chất sau

(a) với mỗi số thực $x_1$ và $x_2$ , nếu $x_1<x_2$ thì $F_X(x_1)\leq F_X(x_2)$ .

(b) $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ và $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ .

(c) $F_X$ liên tục phải tại mọi điểm.

Chứng minh. Xét hai số thực $x_1$ và $x_2$ với $x_1<x_2$ . Biến cố $\{X\leq x_2\}$ là hợp của hai biến cố rời nhau $\{X\leq x_1\}$ và $\{x_1<X\leq x_2\}$ nên

$F_X(x_2)=\mathbb{P}(X\leq x_2)=\mathbb{P}(X\leq x_1)+\mathbb{P}(x_1<X\leq x_2)\geq \mathbb{P}(X\leq x_1)=F_X(x_1).$

Ta có $\{X\leq n\}_{n\geq 1}$ là một dãy tăng các sự kiện có hợp bằng $\Omega$ , theo định lý 1 trong [1], ta có

$1=\mathbb{P}(\Omega)=\mathbb{P}\left(\bigcup_{n=1}^{+\infty}\{X\leq n\}\right)=\lim_{n\to +\infty}\mathbb{P}(X\leq n),$

kết hợp với tính đơn điệu của $F_X$ ta được $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ . Tính chất $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ được chứng minh theo cách tương tự.

Bây giờ xét một số thực $x_0$ . Ta thấy $\{x_0<X\leq x_0+\frac{1}{n}\}_{n\geq 1}$ là một dãy giảm các sự kiện có giao bằng rỗng, theo định lý 2 trong [1], ta có

$0=\mathbb{P}\left(\bigcap_{n=1}^{+\infty}\left\{x_0<X\leq x_0+\frac{1}{n}\right\}\right)=\lim_{n\to +\infty}\left(F_X\left(x_0+\frac{1}{n}\right)-F_X(x_0)\right),$

kết hợp với tính đơn điệu của $F_X$ ta có $F_X$ liên tục phải tại $x_0$ . $\Box$

Continue reading →

Conditional probability

Bạn đọc nên xem lại hai bài sau

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

—

Nhiều phát biểu về cơ hội có dạng: Nếu $B$ xảy ra thì xác suất để $A$ xảy ra là $p$ . Trong bài này ta sẽ quan tâm đến các phát biểu như vậy.

Ví dụ 1. Giả sử một lớp học có $n$ học sinh, trong đó có $n_1$ bạn giỏi toán và $n_2$ bạn nữ. Chọn ngẫu nhiên một học sinh trong lớp. Gọi $A$ là biến cố học sinh được chọn giỏi toán, và $B$ là biến cố học sinh được chọn là nữ. Khi đó theo định nghĩa ngây thơ của xác suất, $\mathbb{P}(A)=n_1/n$ và $\mathbb{P}(B)=n_2/n$ . Bây giờ ta tập trung vào nhóm các bạn học sinh nữ trong lớp. Xác suất để em được chọn trong nhóm này mà giỏi toán bằng $m/n_2$ , ở đây $m$ là số học sinh nữ trong lớp giỏi toán. Nếu kí hiệu $\mathbb{P}(A\mid B)$ là xác suất này, thì

$\displaystyle \mathbb{P}(A\mid B)=\frac{m}{n_2}=\frac{m/n}{n_2/n}=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$ $\Box$

Ta có định nghĩa hình thức sau

Định nghĩa 1. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(B)>0$ . Xác suất của $\displaystyle A$ biết $\displaystyle B$ đã xảy ra, cũng được gọi là xác suất của $\displaystyle A$ với điều kiện $\displaystyle B$ , kí hiệu $\displaystyle \mathbb{P}(A\mid B)$ , được định nghĩa bởi

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$

Chú ý rằng $\displaystyle\mathbb{P}(A\mid B)$ là xác suất của $\displaystyle A$ khi biết $\displaystyle B$ xảy ra, nó không phải là xác suất của biến cố $\displaystyle A\mid B$ , không có biến cố $\displaystyle A\mid B$ . Nếu $\displaystyle \mathbb{P}(A)>0$ thì $\displaystyle \mathbb{P}(A\mid A)=1$ .

Ví dụ 2. Xét phép thử ngẫu nhiên: Tung lần lượt hai con xúc xắc cân đối. Biết rằng con xúc xắc đầu hiện $\displaystyle 3$ chấm, xác suất để tổng số chấm lớn hơn $\displaystyle 6$ là bao nhiêu?

Lời giải. Không gian mẫu của phép thử là $\displaystyle \Omega=\{1,2,3,4,5,6\}^2$ . Như quy ước đối với không gian xác suất rời rạc, $\displaystyle \mathcal{F}$ là họ tất cả các tập con của $\displaystyle \Omega$ . Cuối cùng, $\displaystyle \mathbb{P}(A)=\mid A\mid / 36$ với mỗi $\displaystyle A \subset \Omega$ .

Bây giờ gọi $\displaystyle B$ là biến cố con đầu ra $\displaystyle 3$ chấm, và $\displaystyle A$ là biến cố tổng các chấm lớn hơn $\displaystyle 6$ . Khi đó

$\displaystyle B=\{(3, b): 1 \leq b \leq 6\}, \quad A=\{(a, b): a+b>6\},$ $\displaystyle \quad A \cap B=\{(3,4),(3,5),(3,6)\}.$ Suy ra

$\displaystyle \mathbb{P}(A \mid B)=\frac{\mathbb{P}(A \cap B)}{\mathbb{P}(B)}=\frac{|A \cap B|}{|B|}=\frac{3}{6}=\frac{1}{2}.$ $\Box$

Ví dụ 3. Rút ngẫu nhiên hai quân bài từ một bộ bài cho trước, mỗi lần rút một quân và không trả lại. Gọi $\displaystyle A$ là sự kiện quân bài thứ nhất mang chất cơ và $\displaystyle B$ là sự kiện quân bài thứ hai có màu đỏ. Tính $\displaystyle \mathbb{P}(A\mid B)$ và $\displaystyle \mathbb{P}(B\mid A)$ .

Lời giải. Không gian xác suất được xây dựng theo cách tự nhiên. Với không gian xác suất này, $\displaystyle \mathbb{P}(A)=1/4$ , $\displaystyle \mathbb{P}(B)=1/2$ , và $\displaystyle\mathbb{P}(A\cap B)=\frac{25}{204}.$ Từ đây ta thu được

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}=\frac{25}{102}\approx 0,25$

và

$\displaystyle\mathbb{P}(B\mid A)=\frac{\mathbb{P}(B\cap A)}{\mathbb{P}(A)}=\frac{25}{51}\approx 0,49.$ $\Box$

Từ định nghĩa của xác suất có điều kiện ta có

Định lý 1 (Công thức Bayes). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ . Khi đó

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(B\mid A)\mathbb{P}(A)}{\mathbb{P}(B)}.$

Định lý 2 (Công thức xác suất toàn phần). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Giả sử $\displaystyle A_1$ , $\displaystyle A_2$ , $\displaystyle \ldots$ , $\displaystyle A_n$ là một phân hoạch của $\displaystyle\Omega$ sao cho $\displaystyle \mathbb{P}(A_i)>0$ với mọi $\displaystyle i$ . Khi đó với mỗi biến cố $\displaystyle B$ ,

$\displaystyle\mathbb{P}(B)=\sum_{i=1}^n\mathbb{P}(B\mid A_i)\mathbb{P}(A_i).$

Công thức xác suất toàn phần cho một liên hệ giữa xác suất có điều kiện và xác suất không điều kiện. Để tính một xác suất, ta có thể dùng công thức này để chia bài toán thành các bài toán đơn giản hơn, và nó thường được sử dụng cùng với công thức Bayes.

Ví dụ 4. Có hai chiếc hộp, $\displaystyle \alpha$ và $\displaystyle \beta$ , đựng các viên bi xanh và đỏ. Hộp $\displaystyle \alpha$ chứa hai viên bi đỏ và ba viên bi xanh, hộp $\displaystyle \beta$ chứa ba viên bi đỏ và bốn viên bi xanh. Một viên bi được lấy ngẫu nhiên từ hộp $\displaystyle \alpha$ và bỏ vào hộp $\displaystyle \beta$ . Sau đó, lấy ngẫu nhiên một viên bi trong hộp $\displaystyle \beta$ và kiểm tra màu của nó. Xác suất để nó có màu xanh là bao nhiêu?

Lời giải. Không gian xác suất được mô tả theo cách tự nhiên. Gọi $\displaystyle A$ là biến cố viên bi lấy sau mang màu xanh, và $\displaystyle B$ là biến cố viên bi lấy trước mang màu xanh. Tính toán đơn giản ta được $\displaystyle \mathbb{P}(B)=3/5>0$ và $\displaystyle\mathbb{P}(\overline{B})=2/5>0$ , do đó theo công thức xác suất toàn phần, ta có

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B}).$

Mà ta lại có $\displaystyle \mathbb{P}(A\mid B)=5/8$ và $\displaystyle \mathbb{P}(A\mid \overline{B})=1/2$ , suy ra $\displaystyle \mathbb{P}(A)=23/40= 0,575.$ $\Box$

Ví dụ 5. Có hai nhà máy sản xuất cốc, nhà máy I và nhà máy II. Biết rằng $\displaystyle 20\%$ số cốc từ nhà máy I và $\displaystyle 5\%$ từ nhà máy II bị lỗi. Mỗi tuần, I sản xuất số lượng cốc gấp đôi II. Xác suất để một chiếc cốc được chọn ngẫu nhiên trong một tuần sản xuất đạt yêu cầu là bao nhiêu? Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I là bao nhiêu?

Lời giải. Gọi $\displaystyle A$ là biến cố mà chiếc cốc được chọn là đạt yêu cầu, và gọi $\displaystyle B$ là biến cố nó được sản xuất tại $\displaystyle I$ . Khi đó

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B})$

$=\frac{4}{5}\cdot\frac{2}{3}+\frac{19}{20}\cdot\frac{1}{3}=\frac{51}{60}\approx 0,85.$

Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I, theo công thức Bayes, là

$\displaystyle \mathbb{P}(B\mid \overline{A})=\frac{\mathbb{P}(\overline{A}\mid B)\mathbb{P}(B)}{\mathbb{P}(\overline{A})}=\frac{\frac{1}{5}\cdot \frac{2}{3}}{1-\frac{51}{60}}=\frac{8}{9}\approx 0,889.$ $\Box$

Ví dụ 6. Có một đồng xu công bằng và một đồng xu không công bằng với xác suất hiện mặt sấp khi tung là $\displaystyle 3/4$ . Chọn ngẫu nhiên một trong hai đồng xu và tung nó ba lần. Nó hiện mặt sấp cả ba lần. Tính xác suất để đồng xu được chọn là đồng xu công bằng.

Lời giải. Gọi $\displaystyle A$ là biến cố đồng xu được chọn đều hiện mặt sấp khi tung ba lần, và $\displaystyle B$ là biến cố đồng xu được chọn là đồng xu công bằng. Theo công thức Bayes và công thức xác suất toàn phần, ta có

$\displaystyle \mathbb{P}(B \mid A)=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A)}=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A \mid B) \mathbb{P}(B)+\mathbb{P}\left(A \mid \overline{B}\right) \mathbb{P}\left(\overline{B}\right)}$

$=\frac{(1 / 2)^3 \cdot 1 / 2}{(1 / 2)^3 \cdot 1 / 2+(3 / 4)^3 \cdot 1 / 2}\approx 0.23$ . $\Box$

Ví dụ 7. Xét một trò chơi trong đó một người chơi phải chọn một trong ba cánh cửa. Một trong ba cánh cửa giấu một giải thưởng có giá trị là một chiếc ô tô mới, trong khi mỗi một trong hai cánh cửa còn lại giấu một chiếc bút chì. Sau khi người chơi lựa chọn, người dẫn chương trình (biết xe ở đâu) sẽ mở một trong hai cánh cửa mà người chơi không chọn và cho biết phía sau cánh cửa đó có một cái bút chì. Vào thời điểm này, người chơi phải lựa chọn giữa hai cánh cửa còn lại. Người chơi nên giữ nguyên lựa chọn hay thay đổi?

Lời giải. Bởi vì còn hai cách cửa, một chứa ô tô và cánh còn lại chứa bút chì, nên nhiều người cho rằng chọn lại hay giữ nguyên thì khả năng là như nhau. Đây là câu trả lời sai.

Gọi $\displaystyle A_i$ là biến cố giải thưởng ô tô nằm sau cánh cửa $\displaystyle i$ . Giả sử người chơi đã chọn cánh cửa $\displaystyle 1$ . Gọi $\displaystyle B$ là sự kiện người dẫn chương trình mở ra cánh cửa số $\displaystyle 2$ có giải thưởng là cái bút chì. Theo định nghĩa của xác suất có điều kiện và công thức xác suất toàn phần,

$\displaystyle \mathbb{P}\left(A_1 \mid B\right)=\frac{\mathbb{P}\left(A_1 \cap B\right)}{\mathbb{P}(B)}=\frac{\mathbb{P}\left(B \mid A_1\right)\mathbb{P}\left(A_1\right)}{\mathbb{P}\left(B \mid A_1\right) \mathbb{P}\left(A_1\right)+\mathbb{P}\left(B \mid A_2\right) \mathbb{P}\left(A_2\right)+\mathbb{P}\left(B \mid A_3\right) \mathbb{P}\left(A_3\right)}.$

Bây giờ lập luận đơn giản cho ta $\displaystyle\mathbb{P}(A_i)=1/3$ với mọi $\displaystyle i$ , $\displaystyle \mathbb{P}\left(B \mid A_1\right)=1 / 2$ , $\displaystyle P\left(B \mid A_2\right)=0$ , và $\displaystyle \mathbb{P}\left(B \mid A_3\right)=1$ . Suy ra $\displaystyle \mathbb{P}\left(A_1 \mid B\right)=1/3\approx 0,333.$ Như vậy người chơi nên thay đổi lựa chọn của mình. $\Box$

Từ đầu cho đến thời điểm hiện tại ta đã thấy nhiều ví dụ mà $\displaystyle \mathbb{P}(A\mid B)\not=\mathbb{P}(B)$ , nghĩa là khi ta bổ sung thông tin $\displaystyle B$ thì khả năng xảy ra $\displaystyle A$ thay đổi. Nếu khi bổ sung $\displaystyle B$ mà khả năng xảy ra $\displaystyle A$ không thay đổi ta nói $\displaystyle A$ và $\displaystyle B$ là độc lập.

Định nghĩa 2. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Một họ các biến cố $\displaystyle \{A_i\}_{i\in I}$ được gọi là độc lập nếu với mỗi tập con hữu hạn $\displaystyle J$ của $\displaystyle I$ ,

$\displaystyle\mathbb{P}\left(\bigcap_{j\in J}A_j\right)=\prod_{j\in J}\mathbb{P}(A_j).$

Từ định nghĩa này ta thấy nếu $\displaystyle A$ và $\displaystyle B$ là hai sự kiện độc lập với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ thì $\displaystyle \mathbb{P}(A\mid B)=\mathbb{P}(A)$ và $\displaystyle \mathbb{P}(B\mid A)=\mathbb{P}(B)$ .

Probability space

Các bạn đọc lại bài https://nttuan.org/2024/01/24/naive-definition-of-probability/ để theo dõi bài cho dễ dàng.

Một họ $\mathcal{G}$ các tập con của một tập hợp $\Omega$ được gọi là một đại số các tập con của $\Omega$ nếu nó có ba tính chất sau:

(1) $\Omega\in\mathcal{G}$ .

(2) Nếu $C\in \mathcal{G}$ thì $\Omega\setminus C\in\mathcal{G}$ .

(3) Nếu $C_1,C_2,\ldots,C_n\in\mathcal{G}$ thì $\displaystyle \bigcup_{i=1}^nC_i\in\mathcal{G}$ .

Ví dụ 1. Với tập hợp $\displaystyle \Omega$ , ta có họ $\displaystyle \mathcal{G}=\{\emptyset,\Omega\}$ là một đại số các tập con của $\displaystyle \Omega$ . $\Box$

Bổ đề 1. Cho $\displaystyle \mathcal{G}$ là một đại số các tập con của $\displaystyle \Omega$ . Khi đó

(1) $\displaystyle \emptyset\in\mathcal{G}$ .

(2) Nếu $\displaystyle C_1,C_2,\ldots,C_n\in\mathcal{G}$ thì $\displaystyle \bigcap_{i=1}^nC_i\in\mathcal{G}$ .

(3) Nếu $\displaystyle C_1,C_2\in\mathcal{G}$ thì $C_1\setminus C_2\in\mathcal{G}$ .

Chứng minh. Vì $\displaystyle \Omega\in\mathcal{G}$ nên $\displaystyle \emptyset=\Omega\setminus\Omega$ cũng thuộc $\displaystyle \mathcal{G}$ . Nếu $\displaystyle C_1$ , $\displaystyle C_2$ , $\displaystyle \ldots$ , $\displaystyle C_n\in\mathcal{G}$ thì

$\displaystyle \Omega\setminus \bigcap_{i=1}^nC_i=\bigcup_{i=1}^n(\Omega\setminus C_i)\in\mathcal{G},$

suy ra $\displaystyle \bigcap_{i=1}^nC_i\in\mathcal{G}$ . Cuối cùng, nếu $\displaystyle C_1$ , $\displaystyle C_2\in\mathcal{G}$ thì $\displaystyle C_1\setminus C_2=\Omega\setminus ((\Omega\setminus C_1)\cup C_2)\in\mathcal{G}.$ $\Box$

Định nghĩa 1. Một họ $\displaystyle \mathcal{G}$ các tập con của một tập hợp $\displaystyle \Omega$ được gọi là một $\displaystyle \sigma-$ đại số các tập con của $\displaystyle \Omega$ nếu nó có ba tính chất sau:

(1) $\displaystyle \Omega\in\mathcal{G}$ .

(2) Nếu $\displaystyle C\in \mathcal{G}$ thì $\displaystyle \Omega\setminus C\in\mathcal{G}$ .

(3) Nếu $\displaystyle C_1,C_2,\ldots\in\mathcal{G}$ thì $\displaystyle \bigcup_{i=1}^{\infty}C_i\in\mathcal{G}$ .

Lúc này ta gọi $\displaystyle \Omega$ là không gian mẫu và các phần tử của $\displaystyle \mathcal{G}$ là các biến cố, hay sự kiện.

Mỗi $\displaystyle \sigma-$ đại số là một đại số, ngược lại không đúng.

Ví dụ 2. $\displaystyle \sigma-$ đại số nhỏ nhất các tập con của $\displaystyle \Omega$ là $\displaystyle \{\emptyset,\Omega\}$ . $\Box$

Ví dụ 3. Nếu $\displaystyle A$ là một tập con của $\displaystyle \Omega$ thì $\displaystyle \{\emptyset,\Omega,A,\overline{A}\}$ là một $\displaystyle \sigma-$ đại số các tập con của $\displaystyle \Omega$ . $\Box$

Ví dụ 4. Họ tất cả các tập con của $\displaystyle \Omega$ là $\displaystyle \sigma-$ đại số lớn nhất các tập con của $\displaystyle \Omega$ . $\Box$

Định nghĩa 2. Một không gian đo được là một cặp $\displaystyle (\Omega,\mathcal{F})$ , trong đó $\displaystyle \Omega$ là một tập hợp và $\displaystyle \mathcal F$ là một $\displaystyle \sigma-$ đại số các tập con của $\displaystyle \Omega$ . Khi $\displaystyle \Omega$ là hữu hạn hoặc đếm được thì không gian đo được $\displaystyle (\Omega,\mathcal{F})$ được gọi là rời rạc.

Mỗi khi xét không gian đo được rời rạc $(\Omega,\mathcal{F})$ , ta chỉ xét $\mathcal F$ là $\sigma-$ đại số tất cả các tập con của $\Omega$ .

Định nghĩa 3. Cho một không gian đo được $\displaystyle (\Omega,\mathcal{F})$ . Độ đo xác suất $\displaystyle \mathbb{P}$ trên $\displaystyle (\Omega,\mathcal{F})$ là một hàm $\displaystyle \mathbb{P}:\mathcal{F}\to [0;1]$ thỏa mãn đồng thời hai điều sau:

(1) $\displaystyle \mathbb{P}(\emptyset)=0$ và $\mathbb{P}(\Omega)=1$ .

(2) Nếu $\displaystyle A_1,A_2,\ldots$ là một dãy các phần tử đôi một rời nhau của $\displaystyle \mathcal F$ thì $\displaystyle \mathbb{P}\left(\bigcup_{i=1}^{\infty}A_i\right)=\sum_{i=1}^{\infty}\mathbb{P}(A_i).$

Lúc này thì bộ ba $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ được gọi là không gian xác suất. Với mỗi sự kiện $\displaystyle A$ , ta gọi $\displaystyle \mathbb{P}(A)$ là xác suất của $\displaystyle A$ .

Với không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và biến cố $\displaystyle A$ , ta gọi $\displaystyle A$ là biến cố rỗng nếu $\displaystyle \mathbb{P}(A)=0$ và là biến cố chắc chắn nếu $\displaystyle \mathbb{P}(A)=1$ . Ta có thể xác định một không gian xác suất tương ứng với mỗi phép thử. Khi đó các bài toán liên quan đến phép thử sẽ chuyển về các bài toán trong không gian xác suất tương ứng.

Ví dụ 5. Một đồng xu, có thể không cân, được tung lên một lần. Với phép thử này ta xác định không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ như sau: Không gian mẫu $\displaystyle \Omega=\{0;1\}$ (như trong bài trước, sấp được ghi là $\displaystyle 1$ và ngửa được ghi là $\displaystyle 0$ ), $\displaystyle \mathcal{F}$ là họ tất cả các tập con của $\displaystyle \Omega$ , và độ đo xác suất $\displaystyle \mathbb{P}:\mathcal{F}\to [0;1]$ được định nghĩa bởi

$\displaystyle\mathbb{P}(\emptyset)=0,\,\mathbb{P}(\Omega)=1,\,\mathbb{P}(\{1\})=p,\,\mathbb{P}(\{0\})=1-p.$

Ở đây $\displaystyle p$ là một số thực thuộc đoạn $\displaystyle [0;1]$ . Đồng xu này là cân đối nếu $\displaystyle p=1/2$ . $\Box$

Ví dụ 6. Một con xúc xắc được tung một lần. Với phép thử này ta xác định không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ như sau: Không gian mẫu $\displaystyle \Omega=[6]$ , $\mathcal{F}$ là họ tất cả các tập con của $\displaystyle \Omega$ , và độ đo xác suất $\displaystyle \mathbb{P}:\mathcal{F}\to [0;1]$ được định nghĩa bởi

$\displaystyle \mathbb{P}(A)=\sum_{i\in A}p_i, \quad \forall A\subset \Omega.$

Ở đây $\displaystyle p_1,p_1,\ldots,p_6$ là các số thực không âm có tổng bằng $\displaystyle 1$ . Xác suất để xuất hiện mặt có $\displaystyle i$ chấm là $\displaystyle p_i$ . Con xúc xắc này là cân đối nếu các $\displaystyle p_i$ đều bằng $\displaystyle 1/6$ . Khi đó $\displaystyle \mathbb{P}(A)=\frac{\mid A\mid }{6}, \quad \forall A\subset \Omega,$ bằng xác suất xảy ra $\displaystyle A$ theo định nghĩa ngây thơ (cổ điển) của xác suất. $\Box$

Sau đây là một số tính chất của độ đo xác suất.

Bổ đề 2. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Khi đó

(1) Với mỗi biến cố $A$ , ta có $\displaystyle \mathbb{P}(\overline{A})=1-\mathbb{P}({A})$ .

(2) Nếu $\displaystyle A$ và $\displaystyle B$ là các biến cố thỏa mãn $\displaystyle A\subset B$ thì $\displaystyle \mathbb{P}({B})=\mathbb{P}({A})+\mathbb{P}({B\setminus A})\geq \mathbb{P}({A}).$

(3) Nếu $\displaystyle A_1,A_2,\ldots,A_n$ là $\displaystyle n>1$ biến cố thì

$\displaystyle \mathbb{P}\left(\bigcup_{i=1}^nA_i\right)=\sum_{i=1}^n\mathbb{P}({A_i})-\sum_{i<j}\mathbb{P}({A_i\cap A_j})+\sum_{i<j<k}\mathbb{P}({A_i\cap A_j\cap A_k})$ $\displaystyle -\ldots +(-1)^{n+1}\mathbb{P}(A_1\cap A_2\cap \ldots \cap A_n).$

Chứng minh. Xét một biến cố $\displaystyle A$ . Vì $\displaystyle\Omega=A\cup\overline{A}$ và $\displaystyle A\cap\overline{A}=\emptyset$ nên

$\displaystyle 1=\mathbb{P}(\Omega)=\mathbb{P}(A\cup\overline{A})=\mathbb{P}({A})+\mathbb{P}\overline{A}),$

suy ra $\displaystyle \mathbb{P}(\overline{A})=1-\mathbb{P}({A})$ . Bây giờ xét hai biến cố $\displaystyle A$ và $\displaystyle B$ với $\displaystyle A\subset B$ . Vì biến cố $\displaystyle B$ là hợp của hai biến cố rời nhau $\displaystyle A$ và $\displaystyle B\setminus A$ nên

$\displaystyle\mathbb{P}({B})=\mathbb{P}({A})+\mathbb{P}({B\setminus A})\geq \mathbb{P}({A}).$

Ta sẽ chứng minh khẳng định cuối cùng bằng quy nạp theo $\displaystyle n$ . Xét hai biến cố $\displaystyle A$ và $\displaystyle B$ . Biến cố $\displaystyle A\cup B$ là hợp của hai biến cố rời nhau $\displaystyle A$ và $\displaystyle B\setminus A$ nên

$\displaystyle\mathbb{P}(A\cup {B}) =\mathbb{P}({A})+\mathbb{P}({B\setminus A})= \mathbb{P}({A})+\mathbb{P}({B\setminus (A\cap B)})=\mathbb{P}({A})+\mathbb{P}({B})-\mathbb{P}(A\cap B),$

suy ra khẳng định đúng với $\displaystyle n=2$ . Bây giờ giả sử khẳng định đúng với số nguyên dương $\displaystyle n= k\, (k>1)$ . Xét $\displaystyle k+1$ biến cố $\displaystyle A_1$ , $\displaystyle A_2,\ldots,$ $\displaystyle A_{k+1}$ . Vì khẳng định đúng với $\displaystyle n=2$ nên

$\displaystyle \mathbb{P}\left(\bigcup_{i=1}^{k+1}A_i\right)=\mathbb{P}\left(\left(\bigcup_{i=1}^{k}A_i\right)\bigcup A_{k+1}\right)$

$\displaystyle =\mathbb{P}\left(\bigcup_{i=1}^{k}A_i\right)+\mathbb{P}\left(A_{k+1}\right)-\mathbb{P}\left(\left(\bigcup_{i=1}^{k}A_i\right)\bigcap A_{k+1}\right)$

$\displaystyle =\mathbb{P}\left(\bigcup_{i=1}^{k}A_i\right)+\mathbb{P}\left(A_{k+1}\right)-\mathbb{P}\left(\bigcup_{i=1}^{k}\left(A_i\bigcap A_{k+1}\right)\right).$

Đến đây dùng giả thiết quy nạp ta thấy khẳng định đúng với $\displaystyle n=k+1$ . Theo nguyên lý quy nạp toán học, khẳng định đúng với mỗi số nguyên $\displaystyle n>1$ . $\Box$