Xác suất và đỏ đen

Có một sự thật trong casino là người chơi luôn tin rằng nhà cái đã chơi ăn gian để thắng tiền của họ. Thậm chí, có nhiều người còn tin rằng bằng một cách nào đó, casino luôn cho những người chơi mới dễ thắng, còn người chơi lâu hơn thì sẽ thua. Bởi vậy mới có câu: “Cờ bạc đãi ma mới“. Trong bài viết này, mình muốn chia sẻ một góc nhìn chặt chẽ hơn nhờ vào công thức chặn Chernoff (Chernoff Bounds) trong môn xác suất thống kê bằng ví dụ về trò chơi Roullete trong casino.

Trò Roulette kiểu Mỹ có tổng cộng 38 ô, bao gồm các số từ 1 đến 36 chia là 18 ô đỏ, 18 ô đen, và hai ô đặc biệt màu xanh là 0 và 00. Trước khi bánh xe quay, người chơi đặt tiền vào các loại cược khác nhau trên bàn cược. Để đơn giản, ta chỉ xét kiểu đặt cược theo màu. Người chơi sẽ đặt vào màu đỏ hoặc màu đen với tỷ lệ trả thưởng là 1:1. Sau khi người chơi đã đặt cược, người quản trò (dealer) sẽ quay bánh xe và thả một quả bóng nhỏ theo hướng ngược chiều với bánh xe. Bánh xe sẽ từ từ dừng lại, và quả bóng rơi vào một trong các ô. Nếu quả bóng rơi vào ô trùng khớp với màu lựa chọn cược của người chơi, họ sẽ thắng và được trả thưởng theo tỷ lệ của loại cược đó.

Chặn Chernoff

Chernoff Bounds là một công cụ mạnh trong lý thuyết xác suất, dùng để ước tính xác suất tổng của các biến ngẫu nhiên lệch khỏi giá trị kỳ vọng của nó. .

Ý tưởng chính của chặn Chernoff:

Giả sử ta có một tập hợp các biến ngẫu nhiên độc lập, mỗi biến có giá trị nằm trong một phạm vi xác định (thường là 0 hoặc 1). Khi đó, ta có thể sử dụng chặn Chernoff để ước tính xác suất tổng các biến này khác biệt đáng kể so với kỳ vọng của nó.

Chặn Chernoff hữu ích trong các bài toán về xác suất thấp xảy ra các sự kiện "hiếm", chẳng hạn như tổng các biến ngẫu nhiên vượt qua một ngưỡng nhất định hoặc lệch xa khỏi giá trị kỳ vọng.

Công thức

Giả sử ta có \(X_1, X_2,\dots, X_n\) là các biến ngẫu nhiên độc lập Bernoulli tức là mỗi \(X_i\) có giá trị là 0 hoặc 1 với \(P(X_i=1)=p\). Gọi \(X=X_1+X_2+\dots+X_n\), \(\mathbb E(X)=np\). Chặn Chernoff đưa ra các giới hạn xác suất về sự khác biệt giữa \(X\) và \(\mathbb E(X)\):

• (1) Xác suất tổng \(X\) vượt quá một ngưỡng \((1+\delta)\mathbb E(X)\): \(\displaystyle P(X>(1+\delta)\mathbb E(X)) \le \exp \left( - \frac {\delta^2 \mathbb E(X)} {2+\delta} \right), \quad \delta \gt 0\)

• (2) Xác suất tổng \(X\) thấp hơn một ngưỡng \((1-\delta)\mathbb E(X)\): \(\displaystyle P(X>(1-\delta)\mathbb E(X)) \le \exp \left( - \frac {\delta^2 \mathbb E(X)} {2} \right), \quad 0 \lt \delta \lt 1\)

Ví dụ

Giả sử bạn tung một đồng xu cân bằng 1,000 lần. Kỳ vọng số lần mặt ngửa xuất hiện là: \(\mathbb E(X) = 1,000 \times 0.5 = 500\). Giả sử bạn muốn tính xác suất rằng số lần xuất hiện mặt ngửa vượt quá 600 lần. Áp dụng công thức Chernoff(1), ta có:

$$\begin{align*} X = 600 \gt (1+\delta)\mathbb E(X) = (1+\delta)\times500 = 500\delta + 500 \\ \iff \frac {600 - 500}{500} = 0.2 \gt \delta \end{align*}$$

Đặt \(\delta = 0.2\),

$$P(X\gt 600)\le \exp\left ( -\frac {(0.2)^2 \times 500} {2 + 0.2} \right) \approx 0.000112$$

Điều này có nghĩa là xác suất số lần mặt ngửa xuất hiện hơn 600 lần trong 1000 lần tung chỉ khoảng \(0.0112\%\), một xác suất cực kỳ nhỏ!

Ví dụ 1

Tính xác suất người chơi chỉ đặt màu đỏ và thắng trên 550 ván trong 1,000 ván chơi trong trò roullete, với giả định là người chơi chỉ đặt $1 mỗi ván.

Giả định:

• Xác suất thắng mỗi ván là \(p=\frac {18} {38} \approx 0.4737\), xác suất thua là \( 1-p \approx 0.5263\)

• Kỳ vọng số lần thắng là \(\mathbb E(X) =np=1,000\times 0.4737 = 473.7\)

Áp dụng chặn Chernoff:

Sử dụng công thức Chernoff (1): \(\displaystyle P(X>(1+\delta)\mathbb E(X)) \le \exp \left( - \frac {\delta^2 \mathbb E(X)} {2+\delta} \right), \quad \delta \gt 0\)

Đi tính \(\delta = \frac{550-473.7}{473.7} \approx 0.1609\)

Đưa vào công thức \(\displaystyle P(X \gt 550)=P( X \gt (1-0.1609)\mathbb E(X)) \le \exp \left( -\frac{0.1609^2 \times 473.7}{2+0.1609} \right) \approx 0.0034\)Như vậy, tỷ lệ người chơi có thể thắng trên 550 ván khi đặt màu đỏ trong 1,000 ván không vượt quá 0.34%.

Ví dụ 2

Tính tỷ lệ để casino lời trên 10% so với kỳ vọng với 1,000 ván chơi.

Vì casino lời $1 nếu thắng và lỗ $1 nếu thua nên lợi nhuận kỳ vọng là \(1,000\times(0.5263 \times $1 + (-$1)\times0.4737) = $52.6\). Vậy 10% so với kỳ vọng sẽ là \($52.6 \times 1.1 =$57.86\).

Nếu gọi \(X\) là số ván người chơi thua (casino lời $1), vậy \(1000−X\) là số ván người chơi thắng (casino lỗ $1), ta có:

$$X \times (-1) + (1,000-X)\times 1 = 1,000 - 2X \gt 57.86 \implies X \gt 528.93$$

Tức là ta cần tính xác suất số ván người chơi thua lớn hơn hoặc bằng 529.

Áp dụng chặn Chernoff:

Chúng ta cần tính xác suất \(X>529\), tức là \(X > (1+\delta)\mathbb E(X) \implies \delta \approx 0.0051\)

$$\displaystyle P(X>(1+\delta)\mathbb E(X)) \le \exp \left( - \frac {\delta^2 \mathbb E(X)} {2+\delta} \right) \approx 0.9932$$

Vậy xác suất để casino lời hơn 10% so với kỳ vọng trong 1000 ván Roulette là khoảng 99.32%. Điều này có nghĩa là khả năng casino lời hơn 10% so với giá trị kỳ vọng là rất cao.

Demo

Kết luận

Qua một số ví dụ đơn giản đã nêu, các kỹ thuật xác suất chỉ ra rằng để chiến thắng được casino là rất khó và họ luôn luôn có lợi thế so với người chơi mặc dù họ chẳng cần thiết phải áp dụng phương pháp gì đặc biệt như người chơi vẫn tưởng. Chẳng qua là càng chơi nhiều, bạn càng thua nhiều và họ càng thắng nhiều, có thế thôi!