Xác suất và kỳ vọng

Mức độ: Chuyên sâu

“Trung bình phải gieo bao nhiêu lần?”, “Xác suất thắng là bao nhiêu?”, “Kỳ vọng số … là bao nhiêu?” là dạng câu hỏi ngày càng hay gặp trong đề học sinh giỏi và lập trình thi đấu. Hầu hết các bài này không cần lý thuyết xác suất phức tạp, chỉ cần ba công cụ: đếm, tính chất cộng của kỳ vọng, và quy hoạch động trên kỳ vọng.

Các bạn cần nắm vững bài Hoán vị, chỉnh hợp, tổ hợp và bài Lũy thừa nhanh (nghịch đảo modulo).

Xác suất bằng cách đếm

Khi các kết quả đồng khả năng, xác suất của một sự kiện là

P = (số kết quả thuận lợi) / (tổng số kết quả).

Ví dụ gieo 2 con xúc xắc có 36 kết quả, tổng bằng 7 có 6 kết quả, xác suất 6/36 = 1/6.

Câu hỏi “ít nhất một …” thường dễ hơn khi tính phần bù: P(ít nhất một) = 1 - P(không có cái nào).

In phân số theo modulo

Xác suất, kỳ vọng thường là phân số với tử, mẫu rất lớn. Đề hay yêu cầu in p × q^-1 mod (10⁹ + 7) cho phân số p/q, với q^-1 là nghịch đảo của q theo modulo (tính bằng q^{MOD - 2} theo định lý Fermat nhỏ).

Ví dụ phân số 1/2 in ra 500000004, vì 2 × 500000004 = 1000000008 ≡ 1. Phân số 3/2 in ra 3 × 500000004 mod (10⁹ + 7) = 500000005.

Cách viết này giữ được mọi phép cộng, trừ, nhân, chia phân số: cứ tính như bình thường, mọi phép chia đổi thành nhân với nghịch đảo.

Kỳ vọng và tính chất cộng

Kỳ vọng của đại lượng ngẫu nhiên X là giá trị trung bình có trọng số: E[X] = tổng x × P(X = x). Ví dụ gieo một xúc xắc: E = (1 + 2 + … + 6)/6 = 7/2.

Tính chất quan trọng nhất:

E[X + Y] = E[X] + E[Y], kể cả khi X và Y phụ thuộc nhau.

Cách dùng: viết đại lượng cần tính thành tổng các biến chỉ thị X_i (bằng 1 nếu sự kiện thứ i xảy ra, 0 nếu không). Khi đó E[X_i] = P(sự kiện i), và

E[tổng] = tổng các xác suất.

Ví dụ: hoán vị ngẫu nhiên của n số, kỳ vọng số vị trí i có số i (điểm cố định)? Mỗi vị trí có xác suất 1/n, có n vị trí, kỳ vọng là n × 1/n = 1, với mọi n. Không cần biết phân phối của số điểm cố định (rất phức tạp).

Đại lượng	Viết thành tổng	Kỳ vọng
Số nghịch thế của hoán vị	tổng theo cặp (i, j)	n(n - 1)/4
Số hộp rỗng khi ném n bóng vào m hộp	tổng theo hộp	m × ((m - 1)/m)ⁿ
Số kỷ lục của hoán vị	tổng theo vị trí, P = 1/i	1 + 1/2 + … + 1/n
Số đoạn bit 1	đếm điểm bắt đầu đoạn	(n + 1)/4

Một công thức khác hay dùng, với X nhận giá trị nguyên không âm:

E[X] = P(X ≥ 1) + P(X ≥ 2) + P(X ≥ 3) + …

Rất tiện cho giá trị lớn nhất, nhỏ nhất: P(max ≥ k) = 1 - P(mọi giá trị nhỏ hơn k).

Chờ đến khi thành công

Mỗi lần thử thành công với xác suất p, độc lập. Gọi E là kỳ vọng số lần thử. Lần đầu thành công thì dừng; thất bại thì như bắt đầu lại:

E = 1 + (1 - p) × E, nên E = 1/p.

Gieo xúc xắc đến khi ra mặt 6: trung bình 6 lần.

Sưu tập thẻ: có n loại thẻ đồng khả năng, cần bao nhiêu gói để đủ bộ? Chia thành n giai đoạn; khi đã có i loại, mỗi gói cho loại mới với xác suất (n - i)/n, giai đoạn kéo dài trung bình n/(n - i). Cộng lại: n × (1 + 1/2 + … + 1/n), xấp xỉ n ln n.

Quy hoạch động kỳ vọng

Gọi E[s] là kỳ vọng (số bước, chi phí, …) còn lại khi đang ở trạng thái s. Ở trạng thái kết thúc E = 0. Ở trạng thái khác:

E[s] = (chi phí một bước) + tổng P(s → t) × E[t].

Nếu các bước chỉ đi “tới” (không quay lại trạng thái cũ), tính E ngược từ trạng thái cuối về đầu, giống quy hoạch động thông thường.
Nếu có thể quay lại (rắn trong rắn và thang, sấp làm mất chuỗi ngửa), các phương trình tạo vòng. Khi đó hoặc biến đổi khéo (viết mọi E theo một ẩn chung), hoặc giải hệ phương trình tuyến tính bằng khử Gauss.

Ví dụ ếch đứng ở ô 0, mỗi lần nhảy 1 hoặc 2 ô với xác suất 1/2, dừng khi tới ô n hoặc xa hơn:

Python
C++

MOD = 10 ** 9 + 7
n = 10
nd2 = pow(2, MOD - 2, MOD)               # 1/2 theo modulo
E = [0] * (n + 2)                        # E[i] = 0 với i ≥ n
for i in range(n - 1, -1, -1):
    E[i] = (1 + (E[i + 1] + E[i + 2]) * nd2) % MOD
print(E[0])

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n = 10;
    long long nd2 = (MOD + 1) / 2;           // 1/2 theo modulo
    vector<long long> E(n + 2, 0);           // E[i] = 0 với i ≥ n
    for (int i = n - 1; i >= 0; i--)
        E[i] = (1 + (E[i + 1] + E[i + 2]) % MOD * nd2) % MOD;
    cout << E[0] << endl;
    return 0;
}

Lưu ý: kỳ vọng tính ngược (từ đích về đầu), còn xác suất để đến một trạng thái thì thường tính xuôi (từ đầu đi tới). Đừng nhầm hai chiều.

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Xác suất bằng cách đếm

Bài 1. Tổng của n con xúc xắc

Gieo n con xúc xắc 6 mặt (1 ≤ n ≤ 20). Nhập n và s. In ra xác suất tổng số chấm bằng s, dưới dạng phân số tối giản a/b (xác suất 0 in 0/1).

Ví dụ: nhập 2 7 thì in ra 1/6.

Kiểm tra: nhập 20 70.

Xem đáp số

2631346887493/50779978334208

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Trùng ngày sinh

Có n người (1 ≤ n ≤ 1000), ngày sinh của mỗi người là một trong 365 ngày, đồng khả năng và độc lập. In ra xác suất có ít nhất hai người trùng ngày sinh, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 23 thì in ra 0.507297.

Kiểm tra: nhập 50.

Xem đáp số

0.970374

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Rút bài có đúng r lá đỏ

Bộ bài có n lá, trong đó m lá đỏ. Rút ngẫu nhiên k lá (mọi bộ k lá đồng khả năng). Nhập n, m, k, r (0 ≤ m ≤ n ≤ 10⁶, 0 ≤ k ≤ n, 0 ≤ r ≤ k). In ra xác suất rút được đúng r lá đỏ, theo modulo 10⁹ + 7.

Ví dụ: nhập 10 4 3 1 thì in ra 500000004.

Kiểm tra: nhập 1000000 300000 500000 150000.

Xem đáp số

199355277

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tính chất cộng của kỳ vọng

Bài 4. Số nghịch thế của hoán vị ngẫu nhiên

Chọn ngẫu nhiên một hoán vị của 1, 2, …, n (1 ≤ n ≤ 10¹⁸). Một nghịch thế là cặp vị trí i nhỏ hơn j mà số ở vị trí i lớn hơn số ở vị trí j. In ra kỳ vọng số nghịch thế, theo modulo 10⁹ + 7.

Ví dụ: nhập 3 thì in ra 500000005.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

588

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Hộp rỗng

Ném lần lượt n quả bóng vào m cái hộp, mỗi quả rơi vào một hộp ngẫu nhiên đồng khả năng, độc lập. Nhập n, m (1 ≤ n, m ≤ 10¹⁸). In ra kỳ vọng số hộp rỗng, theo modulo 10⁹ + 7.

Ví dụ: nhập 2 2 thì in ra 500000004.

Kiểm tra: nhập 1000000000000000000 999999999999.

Xem đáp số

877576123

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Giá trị lớn nhất khi gieo nhiều lần

Gieo một con xúc xắc m mặt (ghi 1 đến m) n lần. Nhập n, m (1 ≤ n ≤ 10¹⁸, 1 ≤ m ≤ 10⁶). In ra kỳ vọng của giá trị lớn nhất trong n lần gieo, theo modulo 10⁹ + 7.

Ví dụ: nhập 2 6 thì in ra 472222230.

Kiểm tra: nhập 1000000000000000000 1000000.

Xem đáp số

16336056

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Số kỷ lục

Một hoán vị ngẫu nhiên của 1, …, n là thứ tự xuất hiện điểm số của n vận động viên. Vị trí i là một kỷ lục nếu điểm ở đó lớn hơn mọi điểm trước nó (vị trí 1 luôn là kỷ lục). Nhập n (1 ≤ n ≤ 10⁶). In ra kỳ vọng số kỷ lục, theo modulo 10⁹ + 7.

Ví dụ: nhập 3 thì in ra 833333341.

Kiểm tra: nhập 1000000.

Xem đáp số

881884276

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số đoạn bit 1

Một dãy n bit (1 ≤ n ≤ 10¹⁸), mỗi bit là 0 hoặc 1 với xác suất 1/2, độc lập. In ra kỳ vọng số đoạn các bit 1 liên tiếp (ví dụ 0110111 có 2 đoạn), theo modulo 10⁹ + 7.

Ví dụ: nhập 3 thì in ra 1.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

500000016

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Chờ đến khi thành công

Bài 9. Gieo đến khi được tổng s

Gieo hai con xúc xắc 6 mặt nhiều lần cho tới khi tổng hai mặt bằng s. Nhập s. In ra kỳ vọng số lần gieo dưới dạng phân số tối giản a/b, hoặc -1 nếu không bao giờ đạt được.

Ví dụ: nhập 7 thì in ra 6/1.

Kiểm tra: nhập 12.

Xem đáp số

36/1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Sưu tập đủ bộ thẻ

Mỗi gói bim bim có một thẻ, là một trong n loại đồng khả năng (1 ≤ n ≤ 10⁶). In ra kỳ vọng số gói cần mua để có đủ n loại, theo modulo 10⁹ + 7.

Ví dụ: nhập 2 thì in ra 3.

Kiểm tra: nhập 1000000.

Xem đáp số

269826812

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. k mặt ngửa liên tiếp

Tung một đồng xu cân đối cho tới khi được k lần ngửa liên tiếp. Nhập k (1 ≤ k ≤ 10¹⁸). In ra kỳ vọng số lần tung, theo modulo 10⁹ + 7.

Ví dụ: nhập 2 thì in ra 6.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

438952511

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Chờ một dãy mẫu

Tung đồng xu cân đối, ghi lại N (ngửa) hoặc S (sấp), cho tới khi xâu ghi được kết thúc bằng xâu mẫu P. Nhập P (chỉ gồm N và S, độ dài từ 1 đến 10⁵). In ra kỳ vọng số lần tung, theo modulo 10⁹ + 7.

Ví dụ: nhập NSN thì in ra 10.

Kiểm tra: nhập NNSSNNSNSNNSSNNS.

Xem đáp số

65672

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Sưu tập k loại khác nhau

Như bài 10 nhưng chỉ cần có k loại khác nhau (1 ≤ k ≤ n ≤ 10⁶). Nhập n, k. In ra kỳ vọng số gói cần mua, theo modulo 10⁹ + 7.

Ví dụ: nhập 4 2 thì in ra 333333338.

Kiểm tra: nhập 1000000 500000.

Xem đáp số

156552731

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Quy hoạch động kỳ vọng và xác suất

Bài 14. Ếch nhảy 1 hoặc 2 ô

Con ếch đứng ở ô 0, mỗi lần nhảy tới 1 ô hoặc 2 ô với xác suất 1/2 mỗi loại. Ếch dừng khi đứng ở ô thứ n hoặc xa hơn. Nhập n (1 ≤ n ≤ 10⁶). In ra kỳ vọng số lần nhảy, theo modulo 10⁹ + 7.

Ví dụ: nhập 2 thì in ra 500000005.

Kiểm tra: nhập 1000000.

Xem đáp số

19207023

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Rắn và thang

Bàn cờ có các ô 1 đến N (2 ≤ N ≤ 100), quân cờ bắt đầu ở ô 1. Mỗi lượt gieo xúc xắc 6 mặt và đi tới số ô bằng số chấm; nếu vượt quá N thì đứng yên. Có một số ô là chân thang hoặc đầu rắn: đi vào ô đó thì lập tức chuyển tới ô đích tương ứng. Dòng đầu có N và k, k dòng sau mỗi dòng có hai số u, v (u khác 1 và N, mỗi u xuất hiện nhiều nhất một lần, ô v không phải là chân thang hay đầu rắn). In ra kỳ vọng số lượt để tới ô N, theo modulo 10⁹ + 7. Dữ liệu đảm bảo luôn tới được ô N.

Ví dụ: nhập 4 0 thì in ra 6.

Kiểm tra: nhập

Xem đáp số

667863973

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đi ngẫu nhiên trên đồ thị một chiều

Đồ thị có n đỉnh (2 ≤ n ≤ 10⁵) và m cạnh có hướng u → v với u nhỏ hơn v (m ≤ 2 × 10⁵, không có cạnh lặp). Xuất phát ở đỉnh 1, mỗi bước chọn ngẫu nhiên đều một cạnh đi ra từ đỉnh hiện tại; dừng khi tới đỉnh không có cạnh đi ra. Dòng đầu là n, m, m dòng sau mỗi dòng là u, v. In ra kỳ vọng số bước, theo modulo 10⁹ + 7.

Ví dụ:

Nhập	In ra
`4 4` `1 2` `1 3` `2 4` `3 4`	`2`

Kiểm tra: nhập

Xem đáp số

500000006

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Rút đến bi đỏ đầu tiên

Hộp có r bi đỏ và b bi xanh (1 ≤ r ≤ 10¹⁸, 0 ≤ b ≤ 10¹⁸). Rút lần lượt từng viên, không hoàn lại, cho tới khi rút được bi đỏ đầu tiên. In ra kỳ vọng số viên đã rút (kể cả viên đỏ), theo modulo 10⁹ + 7.

Ví dụ: nhập 1 1 thì in ra 500000005.

Kiểm tra: nhập 1000000000000000000 999999999999999999.

Xem đáp số

720000007

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Ai thắng trước

Hai bạn An và Bình lần lượt chơi, An đi trước. Mỗi lượt, người chơi thắng ngay với xác suất p = a/b (1 ≤ a ≤ b ≤ 10⁹), nếu không thì đến lượt người kia. Nhập a, b. In ra xác suất An thắng, theo modulo 10⁹ + 7.

Ví dụ: nhập 1 6 thì in ra 909090916.

Kiểm tra: nhập 123456789 987654321.

Xem đáp số

486938353

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Con bạc thua sạch

Một người có i đồng, chơi nhiều ván, mỗi ván thắng 1 đồng với xác suất p = a/b, thua 1 đồng với xác suất 1 - p. Người đó dừng khi có n đồng (thắng) hoặc hết tiền (thua). Nhập i, n, a, b (0 ≤ i ≤ n ≤ 10¹⁸, 1 ≤ a nhỏ hơn b ≤ 10⁹). In ra xác suất người đó đạt n đồng, theo modulo 10⁹ + 7.

Ví dụ: nhập 1 2 1 2 thì in ra 500000004.

Kiểm tra: nhập 500000000000000000 1000000000000000000 1 3.

Xem đáp số

149276165

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Tổng của một đoạn ngẫu nhiên

Cho dãy n số a₁, …, a_n (1 ≤ n ≤ 2 × 10⁵, 0 ≤ a_i ≤ 10⁹). Chọn ngẫu nhiên một đoạn con [l, r] (1 ≤ l ≤ r ≤ n), mọi đoạn đồng khả năng. In ra kỳ vọng tổng các số trong đoạn, theo modulo 10⁹ + 7. Dòng đầu là n, dòng sau là dãy số.

Ví dụ:

Nhập	In ra
`3` `1 2 3`	`333333339`

Kiểm tra: nhập

8
5 1 4 1 5 9 2 6

Xem đáp số

444444461

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English