Trong phần 2 của loạt bài viết về xác suất trong lập trình thi đấu, chúng ta sẽ tiếp tục tìm hiểu các khái niệm nâng cao hơn. Nếu bạn chưa đọc phần 1, hãy xem lại để nắm vững các kiến thức cơ bản trước khi tiếp tục. Chúng ta sẽ phân tích một số khái niệm như biến ngẫu nhiên, giá trị kỳ vọng, tính chất tuyến tính của giá trị kỳ vọng và xác suất có điều kiện.
III. Một số kiến thức nâng cao
1. Biến ngẫu nhiên (Random Variable)
Biến ngẫu nhiên là các biến có giá trị ngẫu nhiên, đại diện cho kết quả của một phép thử. Ví dụ, khi tung xúc sắc, biến ngẫu nhiên có thể có các giá trị là {1, 2, 3, 4, 5, 6}. Có hai dạng biến ngẫu nhiên:
- Rời rạc (Discrete): Giá trị rời rạc, có thể đếm được.
- Liên tục (Continuous): Giá trị nằm trong khoảng liên tục.
2. Giá trị kì vọng (Expected Value)
Giá trị kỳ vọng là trung bình có trọng số của một biến ngẫu nhiên, được tính qua tổng các tích giữa xác suất và thể hiện của biến. Công thức tính giá trị kỳ vọng E(X) cho biến ngẫu nhiên X như sau:
E(X) = x₁ * p₁ + x₂ * p₂ + ... + xₙ * pₙ
3. Tính chất tuyến tính của Giá trị kỳ vọng (Linearity of Expectation)
Giá trị kỳ vọng có tính chất tuyến tính, nghĩa là:
E(a₁X₁ + a₂X₂ + ... + aₙXₙ) = a₁E(X₁) + a₂E(X₂) + ... + aₙE(Xₙ)
Điều này mang lại sự tiện lợi trong tính toán khi có nhiều biến ngẫu nhiên.
4. Xác suất có điều kiện (Conditional Probability)
Là xác suất của một sự kiện A xảy ra, với điều kiện biết rằng sự kiện B đã xảy ra. Công thức cho xác suất có điều kiện P(A|B) là:
P(A|B) = P(A ∩ B) / P(B)
5. Tính xác suất từng bước một
Đây là phương pháp giải quyết bài toán xác suất có liên quan tới các biến cố ảnh hưởng lẫn nhau. Có thể hình dung chúng như các đỉnh trên đồ thị, với xác suất là cạnh nối giữa chúng.
Ví dụ về Nested Randomness
Khi gọi hàm randomInt(int N) lồng nhau, xác suất các nguyên được sinh ra sẽ không đều. Dựa vào số lần lồng nhau, bạn có thể tính xác suất cụ thể cho các số nguyên nào xuất hiện.
Giải thuật
Phần này nghiên cứu chi tiết về cách tính xác suất khi sử dụng hàm ngẫu nhiên và các bài toán đi kèm.
