Đây là bài viết thứ 2 trong series bài viết về Xác suất trong lập trình thi đấu. Trước khi đọc bài viết này, các bạn cần nắm vững các kiến thức cơ bản về Xác suất. Hãy tìm đọc lại bài viết thứ nhất của series tại đây.

Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu một số kiến thức nâng cao của Xác suất có ứng dụng trong Lập trình thi đấu!

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 (Random variables) là các biến nhận 1 giá trị ngẫu nhiên đại diện cho kết quả của phép thử. Mỗi giá trị nhận được $x$ của biến ngẫu nhiên $X$ được gọi là một thể hiện của $X,$ đây cũng là kết quả của phép thử hay còn được hiểu là một sự kiện. Lấy ví dụ:

• Biến ngẫu nhiên $X_1$ là giá trị của xúc sắc khi tung, các thể hiện của nó là $\{1, 2, 3, 4, 5, 6\}$.
• $X_2$ là $2$ lần giá trị xúc sắc (có thể viết là $2X_1$), các thể hiện của nó là $\{2, 4, 6, 8, 10, 12\}$.
• $X_3$ là bình phương giá trị xúc sắc. …

Cụ thể hơn, biến ngẫu nhiên là một hàm ánh xạ từ không gian mẫu tới một số thực:

$$X:\Omega ↦ \mathbb{R}$$

Biến ngẫu nhiên có hai dạng:

• Rời rạc (Discrete): Tập giá trị nó là rời rạc, tức là đếm được. Ví dụ như mặt chấm của con xúc xắc.
• Liên tục (Consecutive): Tập giá trị là liên tục, tức là lấp đầy một khoảng trên trục số. Ví dụ như giá thuê nhà ở Hà Nội.

2. Giá trị kì vọng (Expected value)

Với $X$ là một biến ngẫu nhiên, ta đặt $E(X)$ là giá trị trung bình có trọng số của $X$ nếu như thí nghiệm được thực hiện vô số lần. Giá trị $E(X)$ khi đó được gọi là Giá trị kì vọng (Expected value) của biến ngẫu nhiên $X$. Giá trị này được tính bằng tổng các tích giữa xác suất xảy ra của mỗi thể hiện của biến đó với thể hiện đó. Nếu như một tình huống hoặc một trò chơi có giá trị kì vọng bằng $0$ thì đó được gọi là một "trò chơi công bằng".

Tổng quát, một biến ngẫu nhiên $X$ có các thể hiện $x_1, x_2, \dots, x_n$ với xác suất lần lượt là $p_1, p_2, \dots, p_n$ thì công thức tính giá trị kì vọng $E(X)$ là:

$$E(X) = x_1 \times p_1 + x_2 \times p_2 + \cdots + x_n \times p_n$$

Ví dụ 1: Trong trò chơi "đánh đề" mà chúng ta vẫn thường thấy ở nhiều nơi, tỉ lệ thắng cược phổ biến là $1:70$ nếu như ta đánh trúng một con số trong số $100$ con số từ $00$ tới $99$. Gọi biến ngẫu nhiên $X$ là số tiền thắng được nếu đánh đề $1$ đồng vào cùng một con số, thì ta có hai thể hiện của $X$:

• Nếu thắng cược, ta thu được $70$ đồng, nhưng tỉ lệ thắng là $1\%$.
• Nếu thua cược, ta mất $1$ đồng, nhưng tỉ lệ thua là $99\%$.

Như vậy, giá trị kì vọng của $X$ là:

$$70 \times 0,01 + (-1) \times 0,99 = -0.29$$

Dựa trên kết quả này, bạn sẽ mất trung bình $0.29$ đồng với mỗi $1$ đồng đặt cược cho trò chơi may rủi này. Nói rộng hơn, nếu các bạn càng chơi, thì số tiền các bạn mất đi sẽ càng nhiều và tiến dần tới $30\%$ số tiền gốc bỏ ra. Đó là lí do vì sao các bạn đừng bao giờ nên chơi lô đề, bởi vì "đánh đề ra đê mà ở!".

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ó một số tính chất, tuy nhiên trong các bài tập liên quan tới giá trị kì vọng của lập trình thi đấu thì tính chất tuyến tính sẽ đóng vai trò chính. Vì vậy, ta sẽ chỉ bàn về tính chất nói trên trong bài viết này.

Xét các biến ngẫu nhiên $X_1, X_2, \dots, X_n$ có cùng không gian mẫu (không cần độc lập). Tính chất tuyến tính của Giá trị kì vọng cho chúng ta một phép toán tuyến tính (hay còn gọi là phép toán kì vọng) dưới đây:

$$E(a_1X_1 + a_2X_2 + \cdots + a_nX_n) = a_1E(X_1) + a_2 E(X_2) + \cdots + a_nE(X_n)$$

Ví dụ 2: Xét thí nghiệm tung hai con xúc xắc. Hãy tính giá trị kì vọng của tổng giá trị trên hai con xúc xắc?

Với bài toán này, ta đặt $X_1, X_2$ lần lượt là hai biến ngẫu nhiên thể hiện giá trị của con xúc xắc thứ nhất và con xúc xắc thứ hai. Như vậy, ta đang cần tính $E(X_1 + X_2)$.

Ta biết rằng $X_1$ và $X_2$ đều có các thể hiện là $\{1, 2, 3, 4, 5, 6\}$ với xác suất của mỗi thể hiện đều là $\frac{1}{6}$. Từ đó dễ dàng tính được:

$$E(X_1) = E(X_2) = \frac{1}{6} \times (1 + 2 + 3 + 4 + 5 + 6) = 3.5$$

Dựa trên tính chất tuyến tính, ta có:

$$E(X_1 + X_2) = E(X_1) + E(X_2) = 7$$

4. Xác suất có điều kiện (Conditional probability)

Xác suất có điều kiện (Conditional probability) là xác suất để một biến cố $A$ nào đó xảy ra, nếu như biết rằng một biến cố $B$ đã xảy ra, kí hiệu $P(A | B)$ - đọc là "Xác suất của $A,$ biết $B$".

Nếu diễn tả bằng lời, thì xác suất có điều kiện của $A$ biết $B$ được tính bằng cách nhân xác suất trước đó của biến cố $A$ với xác suất cập nhật của biến cố $A$ sau khi $B$ chắc chắn xảy ra. Còn nếu sử dụng công thức, thì với $P(B) > 0$ ta có xác suất có điều kiện của $A$ biết $B$ là:

$$P(A | B) = \frac{P(A \cap B)}{P(B)} \Leftrightarrow P(A \cap B) = P(A | B) \times P(B)$$

Ví dụ 3: Một học sinh lấy ngẫu nhiên hai viên bi từ một chiếc túi đựng ba viên bi màu đỏ, xanh dương và xanh lục (lấy không hoàn lại). Mỗi viên bi có cơ hội được lấy như nhau. Hãy tính xác suất để học sinh đó lấy được viên bi xanh lục sau khi lấy được viên bi đỏ?

Với bài toán này, gọi $A$ là biến cố học sinh lấy được viên bi xanh lục, $B$ là biến cố học sinh lấy được viên bi đỏ. Trong lần lấy đầu tiên, dễ thấy $B$ có xác suất xảy ra là $0.33$ do mỗi viên bi đều có cơ hội lấy như nhau. Ta cần tính $P(A | B)$ - xác suất có điều kiện của $A$ biết $B$.

Sau khi $B$ xảy ra, thì xác suất xảy ra $A$ tăng lên $0.5$ do lúc này trong túi chỉ còn lại $2$ viên bi. Áp dụng cách tính toán đơn giản, ta có:

$$P(A | B) = 0.33 \times 0.5 = 0.165$$

5. Tính xác suất từng bước một

Việc tính toán xác suất từng bước một là phương pháp để giải dạng bài tập về xác suất mà trong đó: Xác suất của một biến cố bị ảnh hưởng bởi biến cố khác.

Trong dạng bài tập này, chúng ta có thể hình dung các biến cố sẽ được mô tả như những đỉnh trên một đồ thị, và các cạnh thể hiện sự phụ thuộc của các biến cố. Mặc dù nghe có vẻ không liên quan, nhưng thực tế việc tính xác suất từng bước một lại giống với cách ta duyệt qua đồ thị: Bắt đầu từ đỉnh gốc - là trạng thái ban đầu và có xác suất bằng $1,$ ta xem xét các cạnh kề để di chuyển tới các khả năng khác nhau của biến cố kèm theo xác suất tương ứng.

Ví dụ 1: Nested Randomness

Xét một hàm randomInt(int N) nhận vào một số nguyên $N$ và trả về một số nguyên ngẫu nhiên có phân bố đều trong phạm vi từ $0$ đến $N-1$. Nếu hàm đó được lồng vào nhau, chẳng hạn như RandomInt(randomInt(N)), thì phân bố xác suất sẽ thay đổi và một số số nguyên có nhiều khả năng xảy ra hơn những số khác. Lưu ý rằng, hàm randomInt(0) sẽ báo lỗi nếu được gọi.

Cho trước một số nguyên $M$ thể hiện số lần hàm randomInt(N) được lồng vào nhau, số nguyên $N$ và một số nguyên $T$ bất kì.

Yêu cầu: Hãy tính xác suất để kết quả của hàm randomInt(N) khi được lồng vào nhau đúng $M$ lần sẽ là số nguyên $T?$

Input:

• Một dòng duy nhất chứa ba số nguyên $N, M$ và $T$.

Constraints:

• $1 \le N \le 1000$.
• $1 \le M \le 10$.
• $0 \le T \le N - M$.

Output:

• In ra kết quả bài toán với sai số tuyệt đối không vượt quá $10^{-9}$ so với kết quả của bài tập.

Sample Input:

5 2 1

Sample Output:

0.21666666666666667

Giải thích:

Có $3$ cách để thu được số $1$ sau khi gọi $2$ lần hàm lồng nhau randomInt(randomInt(5)): Lời gọi bên trong phải trả ra $4, 3$ hoặc $2$ - mỗi trường hợp này có xác suất là $\frac{1}{5}$. Xác suất để thu được số $1$ cuối cùng ở mỗi trường hợp trên lần lượt là $\frac{1}{4}, \frac{1}{3}$ và $\frac{1}{2}$. Như vậy, xác suất cuối cùng sẽ là: $\frac{1}{5} \times \left(\frac{1}{4} + \frac{1}{3} + \frac{1}{2}\right) = \frac{13}{60}$.

Ý tưởng

Có thể thấy rằng, hàm randomInt(N) sẽ trả về một số nguyên ngẫu nhiên trong đoạn $[0, N - 1]$ với xác suất của mỗi số trả ra là như nhau và bằng $\frac{1}{N}$.

Hãy xét $N = 4,$ thì nếu như gọi lồng hàm randomInt(N) $3$ lần chẳng hạn, ta sẽ có đồ thị biểu diễn xác suất của các trường hợp dưới đây:

Để làm rõ hình trên, xét lần lượt các lời gọi hàm lồng nhau, ta có:

• Với randomInt(4), hàm trả về các số $\in [0, 3]$ với xác suất $\frac{1}{4}$.
• Với randomInt(randomInt(4)), hàm bên trong có $4$ trường hợp xảy ra với xác suất $\frac{1}{4},$ nên cả lời gọi này sẽ có $4$ trường hợp là:
  • random(0): Được gọi với xác suất $\frac{1}{4},$ nó sẽ báo lỗi.
  • random(1): Được gọi với xác suất $\frac{1}{4},$ trường hợp này luôn luôn trả về $0$.
  • random(2): Được gọi với xác suất $\frac{1}{4},$ trường hợp này trả về $0$ hoặc $1$ với xác suất bằng $\frac{1}{2}$.
  • random(3): Được gọi với xác suất $\frac{1}{4},$ trường hợp này trả về $0$ hoặc $1$ hoặc $2$ với xác suất bằng $\frac{1}{3}$. Như vậy, có thể tính được xác suất trả về các số $0, 1, 2$ khi lồng $2$ lời gọi hàm randomInt(randomInt(4)) lần lượt là $\frac{11}{24}, \frac{5}{24}$ và $\frac{1}{12}$ (chính là hàng thứ $2$ từ trên xuống của đồ thị mô tả các trường hợp).
• Nếu xét tiếp randomInt(randomtInt(randomInt(4))) thì ta hoàn toàn tính toán tương tự và thu được kết quả:
  • random(0): Được gọi với xác suất $\frac{1}{4} + \frac{1}{8} + \frac{1}{12} = \frac{11}{24}$. Trường hợp này sẽ báo lỗi.
  • random(1): Được gọi với xác suất $\frac{1}{4} + \frac{1}{8} + \frac{1}{12} = \frac{5}{24},$ trường hợp này luôn luôn trả về $0$.
  • random(2): Được gọi với xác suất $\frac{1}{12},$ trường hợp này trả về $0$ hoặc $1$ với xác suất $\frac{1}{2}$. Như vậy, khi lồng $3$ lời gọi hàm thì xác suất trả về các số $0$ và $1$ sẽ lần lượt là $\frac{6}{24} = \frac{1}{4}$ và $\frac{1}{24}$.
• ...

Dựa vào quy luật trên, ta sẽ xây dựng $p[i]$ là xác suất để số $i$ xuất hiện, rồi lần lượt tính toán hết các $p[i]$ qua mỗi lần gọi hàm lồng nhau. Quy luật sẽ là:

• Ban đầu các $p[i] = \frac{1}{n}$ với mọi $i = 0...n - 1$. Đây là trường hợp cơ sở khi $m = 1$ (có duy nhất một lời gọi hàm).
• Lần lượt xét các lần lồng hàm, lần thứ $k \ (2 \le k \le m)$ ta có:
  • Gọi $p_1[i]$ là xác suất tạo được số $i$ ở lần gọi này sau khi đã có xác suất $p[i]$ trước đó. Ban đầu khởi tạo mọi $p_1[i] = 0 \ (0 \le i \le n - 1)$.
  • Với mỗi giá trị $i \ (0 \le i \le n - 1),$ xác suất tạo ra nó ở $k - 1$ lần lồng hàm trước đang là $p[i]$. Khi gọi thêm một lần thứ $k,$ thì dĩ nhiên hàm randomInt(i) lần này chỉ tạo được các giá trị $j = 0...i - 1$ với xác suất bằng nhau là $\frac{1}{i}$. Như vậy, tổng xác suất tạo ra số $j$ sẽ cộng thêm một lượng là $\frac{1}{i} \times p[i]$:

  $$p_1[i] = p_1[i] + \frac{p[i]}{i}$$

  • Cuối cùng chỉ cần gán $p[i] = p_1[i] \ (0 \le i \le n - 1)$ để chuẩn bị cho lần lồng hàm tiếp theo.

Kết quả cuối cùng sẽ là $p[t]$.

Độ phức tạp: $O(m \times n^2)$.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

double solution(int n, int m, int t)
{
    vector < int > p(n), p1(n);
    for (int i = 0; i < n; ++i)
        p[i] = (double) 1 / n;
		
    for (int k = 2; k <= m; ++k)
    {
        fill(p1.begin(), p1.end(), 0);
		
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                p1[j] += p[i] / i;
				
        p = p1;
    }
	
    return p[t];
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	
    int n, m, t;
    cin >> n >> m >> t;
	
    cout << solution(n, m, t);
	
    return 0;
}

Ví dụ 2: GeneticCrossover

Trong di truyền học ở động vật, phần lớn các loài sẽ có một cặp bản sao của mỗi gene, một trong số đó được di truyền từ bố mẹ. Mỗi gene có hai dạng cơ bản là "trội" hoặc "lặn" - thường được biểu diễn bằng một cặp chữ cái in hoa và in thường tương ứng (ví dụ A và a). Một cặp gene thể hiện một tính trạng, chỉ cần cặp gene này có một gene trội thì tính trạng trội của cặp gene đó sẽ được thể hiện ra trên cơ thể loài động vật, còn nếu cả hai gene đều là lặn thì tính trạng lặn của cặp gene đó sẽ được thể hiện ra.

Ngoài ra, một số gene còn có tính phụ thuộc. Nếu một gene phụ thuộc vào một gene khác thì gene đó chỉ có thể thể hiện tính trạng trội nếu gene nó phụ thuộc vào cũng thể hiện tính trạng trội. Bên cạnh đó, có những gene không phụ thuộc vào bất cứ gene nào khác và tính trạng của nó sẽ được thể hiện như giải thích ở đoạn đầu. Đảm bảo không có trường hợp một gene phụ thuộc vào chính nó hay chuỗi phụ thuộc tạo thành một vòng (ví dụ I phụ thuộc J, J phụ thuộc K, K phụ thuộc I).

Sự phụ thuộc nói trên được thể hiện bởi một mảng $d[i]$. Nếu $d[i] = j$ nghĩa là gene $i$ chỉ có thể biểu hiện trội nếu như gene $j$ cũng biểu hiện trội, còn nếu gene $j$ là gene lặn thì chắc chắn gene $i$ cũng phải là gene lặn theo. Trong trường hợp $d[i] = -1$ thì gene $i$ không có bất kì phụ thuộc nào cả.

Cho hai chuỗi gene độ dài $n$ của cá thể bố và hai chuỗi gene độ dài $n$ của cá thể mẹ. Với mỗi cặp gene, cá thể bố/mẹ sẽ cho con của chúng một trong hai gene của cặp đó. Chẳng hạn, cá thể mẹ có hai chuỗi gene là ABC và abc thì đối với cặp gene đầu tiên, cá thể mẹ có thể cho đời con gene A hoặc a, với cặp thứ hai là B hoặc b và với cặp thứ ba là C hoặc c,...Tương tự với cá thể bố. Sau cùng, cá thể con sẽ nhận được đủ $n$ cặp gene của bố và mẹ. Chất lượng con giống của cá thể con sẽ được tính theo cách sau:

• Nếu cặp gene thứ $i$ của cá thể con thể hiện tính trạng trội, thì chất lượng sẽ tăng thêm một lượng $dominant[i]$.
• Nếu cặp gene thứ $i$ của cá thể con thể hiện tính trạng lặn, thì chất lượng sẽ tăng thêm một lượng $recessive[i]$.

Yêu cầu: Hãy tính giá trị kì vọng của chất lượng con giống?

Input:

• Dòng đầu tiên chứa số nguyên dương $n$ - độ dài chuỗi gene của cá thể bố và mẹ. Các gene được đánh số từ $0$ tới $n - 1$.
• Dòng thứ hai chứa chuỗi $pa_1$ độ dài $n$ là chuỗi gene thứ nhất của cá thể bố.
• Dòng thứ ba chứa chuỗi $pa_2$ độ dài $n$ là chuỗi gene thứ hai của cá thể bố.
• Dòng thứ tư chứa chuỗi $pb_1$ độ dài $n$ là chuỗi gene thứ nhất của cá thể mẹ.
• Dòng thứ năm chứa chuỗi $pb_2$ độ dài $n$ là chuỗi gene thứ hai của cá thể mẹ.
• Dòng thứ sáu chứa $n$ số nguyên thể hiện các giá trị $dominant_{0...n - 1}$.
• Dòng thứ bảy chứa $n$ số nguyên thể hiện các giá trị $recessive_{0...n - 1}$.
• Dòng cuối cùng chứa $n$ số nguyên thể hiện các giá trị $d_{0...n - 1}$ - phụ thuộc giữa các gene với nhau.

Constraints:

• $1 \le n \le 50$.
• Các chuỗi $pa_1, pa_2, pb_1, pb_2$ chỉ gồm các chữ cái latin in thường hoặc in hoa.
• Các kí tự ở cùng vị trí của các chuỗi $pa_1, pa_2, pb_1, pb_2$ sẽ có giá trị như nhau, chỉ khác là in hoa hoặc in thường.
• $-1 \le d_i \le n - 1; \forall i: 0 \le i \le n - 1$.
• $-100 \le dominant_i, recessive_i \le 100; \forall i: 0 \le i \le n - 1$.

Output:

• In ra kết quả bài toán.

Sample Input:

5
AaaAA
AaaAA
AaaAA
AaaAA
1 2 3 4 5
-1 -2 -3 -4 -5
-1 -1 -1 -1 1

Sample Output:

-5.0

Giải thích:

Do các chuỗi gene đều giống nhau, nên đời con sẽ có hai chuỗi gene là AaaAA. Mà gene ở vị trí thứ $4$ lại phụ thuộc vào gene số $1$ (đã thể hiện tính trạng lặn), nên cặp gene thứ $4$ cũng vẫn thể hiện tính trạng lặn mặc dù nó là AA. Như vậy, các cặp gen ở vị trí $0$ và vị trí $3$ sẽ thể hiện tính trạng trội, còn lại thể hiện tính trạng lặn. Do đó giá trị kì vọng của chất lượng con giống là:

$$\big[1 + (-2) +(-3) + 4 + (-5)\big] \times 1 = -5.0$$

Ý tưởng

Dựa vào mô tả đề bài, có hai trường hợp có thể xảy ra: Một gene không phụ thuộc vào gen khác, hoặc gene này có phụ thuộc vào một gene khác.

Trường hợp thứ nhất, gọi $p$ là xác suất mà gene này là gene trội. Có 4 trường hợp:

• Ít nhất bố hoặc mẹ có hai gene trội ($p=1$)
• Mỗi bố hoặc mẹ có đúng một gene trội ($p=0.5$)
• Mỗi bố hoặc mẹ có một gene trội và người còn lại có duy nhất một gene lặn ($p=0.25$)
• Cả hai bố mẹ có hai gene lặn ($p=0$)

Trường hợp thứ hai, gene này có phụ thuộc vào một gene khác. Điều này làm bài toán trở nên phức tạp hơn do gene bị phụ thuộc có thể lại phụ thuộc vào một gene khác nữa và cứ thế… Do đó, để xác định được xác suất mà một gene phụ thộc là gen trội, ta cần xét xác suất để mỗi gene trong chuỗi phụ thuộc (bắt đầu từ gene đang xét) đều là gene trội. Xác suất để gene đang xét là gen trội sẽ bằng tích của tất cả các xác suất đó. Thuật toán thực hiện một cách đệ quy. Đoạn code mẫu dưới đây sẽ mô tả khung thuật toán chính để hoàn thiện bài tập này.

Code mẫu

int n, d[200];
double power[200];

// Here we determine the characteristic for each gene (in power[i]
// we keep the probability of gene I to be expressed dominantly).
double detchr (string &pa1, string &pb1, string &pa2, string &pb2, int nr) 
{
    double p, p1, p2;
    p = p1 = p2 = 1.0;
    if (pa1[nr] <= 'Z')
        p1 = p1 - 0.5;

  // Is a dominant gene.
    if (pb1[nr] <= 'Z')
        p1 = p1 - 0.5;
    if (pa2[nr] <= 'Z')
        p2 = p2 - 0.5;
    if (pb2[nr] <= 'Z')
        p2 = p2 - 0.5;
    p = 1 - p1 * p2;

    if (d[nr] != -1)
        power[nr] = p * detchr(p1a, p1b, p2a, p2b, d[nr]);
    // gene nr is dependent on gene d[nr].
    else 
        power[nr] = p;
  
    return power[nr];
}

double cross(string p1a, string p1b, string p2a, string p2b,
             vector dom, vector rec, vector dependencies) 
{
    double fitness = 0.0;

    n = rec.size();
    for (int i = 0; i < n; ++i)
        d[i] = dependencies[i];
    for (int i = 0; i < n; ++i)
        power[i] = -1.0;
		
    // We check if the dominant character of gene i has
    // not already been computed.
    for (int i = 0; i < n; ++i)
        if (power[i] == -1.0)
            detchr(pa1, pb1, pa2, pb2, i);

    // We compute the expected 'quality' of an animal based on the
    // probabilities of each gene to be expressed dominantly.
    for (int i = 0; i < n; ++i)
        fitness = fitness + (double) power[i] * dom[i] - (double) (1 - power[i]) * rec[i];

    return fitness;
}

Các bạn có thể tham khảo thêm một lượng lớn bài tập liên quan tới Xác suất ở cuối bài viết tại link này.

IV. Tài liệu tham khảo

• https://www.topcoder.com/community/data-science/data-science-tutorials/understanding-probabilities/
• https://vi.wikipedia.org/wiki/Xác_suất
• https://www.geeksforgeeks.org/conditional-probability/