Tag: xác suất

Ramsey numbers


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

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

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

[3] https://nttuan.org/2023/09/01/graph02/

—

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

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).