I. Mở đầu

Xác suất và Thống kê là một nhánh của Toán học, có rất nhiều ứng dụng trong thực tế, đặc biệt là trong việc phân tích dữ liệu. Xác suất và Thống kê xuất hiện trong mọi lĩnh vực, nhờ vào đó mà giúp các doanh nghiệp đưa ra chiến lược kinh doanh, giúp con người dự báo thời tiết,...Chính vì vậy, những bài toán liên quan tới xác suất ít nhiều đều được lấy từ những ví dụ thực tế. Nếu các bạn đã học về xác suất ở môn Toán bậc THPT, không khó để nhận ra những bài toán kiểu như ví dụ dưới đây:

Xếp ngẫu nhiên ba bạn nam và ba bạn nữ ngồi vào sáu ghế kê theo hàng ngang. Tìm xác suất sao cho các bạn nam và nữ ngồi xen kẽ nhau?

Không khó để nhận ra các bài toán xác suất, tuy nhiên để giải được chúng là một chuyện hoàn toàn khác. Trong bài viết này, chúng ta sẽ cùng thảo luận về kiến thức Xác xuất Thống kê được sử dụng trong lĩnh vực lập trình thi đấu. Khi nắm được các kiến thức nền tảng, các bạn sẽ có lợi thế lớn khi tham gia các cuộc thi lập trình.

II. Các kiến thức cơ bản

1. Không gian mẫu và Biến cố

Hãy tưởng tượng ta đang làm một thí nghiệm hàng nghìn, hàng triệu lần, sau đó ghi lại kết quả của tất cả các lần thí nghiệm. Tập hợp tất cả các kết quả của thí nghiệm đó được gọi là Không gian mẫu (sample space), thường được kí hiệu là $S$ hoặc $\Omega$. Mỗi một kết quả có thể xảy ra sẽ được biểu diễn bằng một và chỉ một điểm trong không gian mẫu.

Mọi hành động đều có thể trở thành một thí nghiệm trong xác suất. Chẳng hạn như:

• Tung xúc xắc $1$ lần: Không gian mẫu là $S = \{1, 2, 3, 4, 5, 6\}$.
• Tung hai đồng xu cùng lúc $1$ lần: Không gian mẫu là $S = \big\{(1, 0), (0, 1), (1, 1), (0, 0)\big\}$ với $0$ thể hiện đồng xu sấp và $1$ thể hiện đồng xu ngửa.

Ta định nghĩa một Biến cố (event) là một tập hợp các kết quả của một thí nghiệm thỏa mãn những điều kiện nhất định. Do đó, một biến cố là một tập con của không gian mẫu $S$. Nếu kí hiệu một biến cố là $E$ thì ta có:

$$E \subseteq S$$

Một biến cố có thể bao gồm một hoặc nhiều kết quả trong không gian mẫu. Nếu một biến cố bao gồm nhiều hơn một kết quả, thì nó được gọi là Biến cố phức hợp (compound event). Chẳng hạn như trong thí nghiệm tung hai đồng xu ở trên, thì biến cố $E =$ "Một đồng xu ngửa và một đồng xu sấp" sẽ là một biến cố phức hợp, vì nó bao gồm hai kết quả $(0, 1)$ và $(1, 0)$.

2. Xác suất của một biến cố

Điều ta quan tâm ở đây là khả năng để một biến cố nhất định xảy ra, hay chính là Xác suất của biến cố. Theo định nghĩa, xác suất $P(E)$ của một biến cố $E$ là một số thực nằm trong đoạn $[0, 1],$ với $0$ thể hiện biến cố đó không xảy ra và $1$ thể hiện biến cố đó chắc chắn xảy ra (nói cách khác, biến cố đó chính là toàn bộ không gian mẫu).

Hình vẽ dưới đây minh họa về xác suất $P(E)$:

Trong đó:

• Impossible Event: Biến cố không xảy ra.
• Even chance: Biến cố có xác suất 50 - 50.
• Certain: Biến cố chắc chắn xảy ra.

Do mỗi biến cố được biểu diễn bởi duy nhất một điểm trong không gian mẫu, điều này đưa đến công thức:

$$P(E) = \frac{|E|}{|S|} \ (*)$$

Tức là, xác suất xảy ra của một biến cố $E$ có thể tính bằng cách lấy số lượng kết quả của biến cố đó chia cho tổng số kết quả có thể xảy ra (kích thước của không gian mẫu). Các quy ước từ lý thuyết tập hợp như giao, hợp, hiệu, lấy phần bù,...có thể được áp dụng để diễn tả mối quan hệ giữa các biến cố. Chẳng hạn, xem xét thí nghiệm tung xúc xắc ở trên, với không gian mẫu $S = \{1, 2, 3, 4, 5, 6\},$ ta có một vài biến cố dưới đây:

• Biến cố $A =$ "Điểm thu được lớn hơn $4$": $5, 6$.
• Biến cố $B =$ "Điểm thu được là số lẻ": $1, 3, 5$.
• Biến cố $C =$ "Điểm lớn hơn $6$ và là số chẵn": $\varnothing$.

Áp dụng một số quy tắc tập hợp, ta có:

• $A \cup B =$ "Điểm thu được lớn hơn $4$ hoặc là số lẻ": $\{5, 6\}$.
• $A \cap B =$ "Điểm thu được lớn hơn $4$ và là số lẻ": $\{5\}$.
• $B' =$ "Biến cố $B$ không xảy ra": $\{2, 4, 6\}$.

Xác suất của một vài biến cố sẽ được tính như sau, theo công thức $(*)$:

• $P(A \cup B) = \frac{2}{6} = \frac{1}{3}$.
• $P(A \cap B) = \frac{1}{6}$.
• $P(B') = \frac{3}{6} = \frac{1}{2} = 1 - P(B)$.
• $P(C) = \frac{0}{6} = 0$.

Như vậy, cách làm cơ bản để tính xác suất của một biến cố là xác định được không gian mẫu của thí nghiệm. Sau đó, ta cần xác định số lượng phần tử của biến cố cần tìm. Tuy nhiên, tùy vào từng bài toán mà cách tiếp cận có thể thay đổi đi.

Ví dụ 1: Bài toán Tín hiệu tình yêu

Romeo và Juliet yêu nhau rất sâu đậm, nhưng vì gia đình ngăn cấm nên họ không thể gặp nhau một cách công khai. Vì cảm thông cho tình yêu của họ, những thiên thần đã ban cho mỗi người một chiếc máy thu/phát tín hiệu – là phát minh mới nhất của những thiên thần. Chiếc máy này có thể giúp cho Juliet gửi cho Romeo định vị của Juliet, từ đó Romeo sẽ tới điểm hẹn bí mật khi họ muốn gặp nhau.

Quy tắc của chiếc máy rất đơn giản: Coi rằng con đường giữa hai bên gia đình là một trục số thẳng, và Romeo đang đứng ở vị trí $0$. Juliet sẽ gửi cho Romeo một dãy tín hiệu gồm các kí tự + và -, + nghĩa là Romeo cần tiến thêm một bước về phía chiều dương của trục số, - nghĩa là Romeo cần lùi lại một bước về phía chiều âm của trục số.

Tuy nhiên, do chiếc máy là đồ mới sản xuất nên đôi khi gặp trục trặc, nó khiến cho có một số tín hiệu bị nhiễu và chiếc máy của Romeo không thể thu nhận được tín hiệu đó. Những tín hiệu không xác định sẽ bị hiển thị là dấu ?. Vì không thể để ai phát hiện, cho nên Romeo đành tự mình thử tất cả các cách đi có thể dựa vào dãy tín hiệu nhận được.

Yêu cầu: Hãy tính xác suất mà Romeo có thể đi tới chính xác điểm hẹn mà Juliet mong muốn?

Input:

• Dòng đầu là chuỗi kí tự S_1 chỉ gồm các kí tự $\{$+,-$\}$ – là tín hiệu mà Juliet gửi tới cho Romeo.
• Dòng thứ hai là chuỗi kí tự $S_2$ chỉ gồm các kí tự $\{$+,-,?$\}$ – là chuỗi tín hiệu mà Romeo nhận được.

Ràng buộc:

• Độ dài hai chuỗi tín hiệu bằng nhau và không vượt quá $10$.

Output:

• Ghi một số thực duy nhất là xác suất mà Romeo có thể tới chính xác điểm hẹn mà Juliet gửi tới, làm tròn tới $10$ chữ số sau dấu phẩy.

Sample Input:

++-+-
+-+-+

Sample Output:

1.0000000000

Ý tưởng

Tổng số trường hợp đường đi có thể tạo ra là $2^n$ với $n$ là độ dài của hai xâu. Như vậy không gian mẫu $S$ có kích thước là $2^n$.

Từ xâu hướng dẫn của Juliet ($S_1$), ta sẽ tính được đích đến có tọa độ bao nhiêu.

Gọi $E$ là biến cố "Đường đi của Romeo tới được đích". Để tính số lượng phần tử của biến cố $E,$ sử dụng quay lui để thử tạo ra tất cả các trường hợp của xâu $S_2,$ sau đó tính tọa độ điểm đến từ mỗi trường hợp, xem xem địa điểm cần đến xuất hiện bao nhiêu lần trong tất cả các tọa độ tạo ra. Từ đó ta có thể tính được xác suất của biến cố $E$ theo công thức.

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

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

string s1, s2;
vector < int > all_pos;

void backtrack(int i, int &cur)
{
    if (i == s2.size())
    {
        all_pos.push_back(cur);
        return;
    }

    if (s2[i] != '?')
        backtrack(i + 1, cur);
    else
    {
        for (int j = 0; j <= 1; ++j)
        {
            if (j == 0)
                cur += 1;
            else
                cur -= 1;

            backtrack(i + 1, cur);

            if (j == 0)
                cur -= 1;
            else
                cur += 1;
        }
    }
}

void solution(string &s1, string &s2)
{
    int des = 0;
    for (int i = 0; i < s1.size(); ++i)
        des = (s1[i] == '+') ? des + 1 : des - 1;
    int cur = 0;
    for (int i = 0; i < s2.size(); ++i)
        if (s2[i] != '?')
            cur = (s2[i] == '+') ? cur + 1 : cur - 1;

    backtrack(0, cur);

    int cnt = 0;
    for (auto e: all_pos)
        cnt += (e == des);

    cout << fixed << setprecision(10) << (double) cnt / (double) all_pos.size();
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s1 >> s2;

    solution(s1, s2);

    return 0;
}

3. Biến cố độc lập, Biến cố xung khắc và Biến cố phụ thuộc

Định nghĩa

Cho hai biến cố $A$ và $B$. Khi đó:

• Hai biến cố $A$ và $B$ được gọi là độc lập với nhau nếu việc xảy ra hay không xảy ra của biến cố này không làm ảnh hưởng tới xác suất xảy ra của biến cố kia. Khi $A$ và $B$ độc lập thì $A$ và $\overline{B}, \overline{A}$ và $B, \overline{A}$ và $\overline{B}$ cũng độc lập với nhau.
• Hai biến cố $A$ và $B$ được gọi là xung khắc nếu biến cố này xảy ra thì biến cố kia không xảy ra. Tức là, hai biến cố $A$ và $B$ xung khắc nhau nếu và chỉ nếu:

  $$\Omega_A \cap \Omega_B = \varnothing$$

• Hai biến cố $A$ và $B$ được gọi là phụ thuộc nếu như sự xảy ra của biến cố $A$ làm thay đổi xác suất xảy ra của biến cố $B$ hoặc ngược lại.

Các quy tắc tính xác suất

Quy tắc nhân xác suất

Nếu hai biến cố $A$ và $B$ độc lập với nhau, gọi $AB$ là biến cố "Cả $A$ và $B$ cùng xảy ra", ta có công thức:

$$P(AB) = P(A) \times P(B)$$

Còn nếu như hai biến cố $A$ và $B$ phụ thuộc lẫn nhau, thì xác suất của biến cố $AB$ được tính bằng công thức:

$$P(AB) = P(A \cup B) - \big[P(\text{chỉ }A) + P(\text{chỉ }B)\big]$$

Quy tắc cộng xác suất

Nếu như hai biến cố $A$ và $B$ độc lập với nhau, thì gọi $A \cup B$ là biến cố "$A$ hoặc $B$ xảy ra", khi đó do $|A \cup B| = |A| + |B| - |A \cup B|$ (trong lý thuyết tập hợp), nên xác suất của biến cố $A \cup B$ được tính bằng công thức:

$$P(A \cup B) = P(A) + P(B) - P(AB)$$

Gọi thêm $C = (A \cap B)'$ thì ta có một công thức khác để tính $P(A \cup B)$:

$$P(A \cup B) = 1 - P(C)$$

Còn nếu như hai biến cố $A$ và $B$ xung khắc với nhau thì xác suất để một trong hai biến cố xảy ra là:

$$P(A \cup B) = P(A) + P(B)$$

Quy tắc trừ xác suất

Từ quy tắc cộng, ta suy ra được quy tắc trừ xác suất của hai biến cố xung khắc $A$ và $B$:

$$P(A \cup B)' = 1 - P(A) - P(B)$$

Một vài câu hỏi thường gặp

Bây giờ, xét một dãy biến cố độc lập $A_1, A_2, \dots, A_n$. Có hai câu hỏi thường được quan tâm:

• Xác suất để tất cả các biến cố cùng xảy ra là bao nhiêu?
• Xác suất để ít nhất một biến cố xảy ra là bao nhiêu?

Để trả lời câu hỏi thứ nhất, ta xét biến cố đầu tiên $A_1$:

• Nếu $A_1$ không xảy ra, thì giả thuyết sẽ sai (tất cả các biến cố đều xảy ra). Do đó, cần phải chắc chắn $A_1$ sẽ xảy ra với xác suất $P(A_1),$ điều này để ta có thể kiểm tra sự xảy ra của biến cố tiếp theo $A_2$.
• Nếu biến cố $A_2$ xảy ra với xác suất là $P(A_2),$ ta lại tiếp tục thực hiện quá trình như vậy,...

Áp dụng quy tắc nhân xác suất, ta tổng hợp được xác suất để tất cả các biến cố xảy ra bằng công thức dưới đây:

$$P(\text{all}) = P(A_1) \times P(A_2) \times \cdots \times P(A_n)$$

Đối với câu hỏi thứ hai, cách đơn giản nhất là ta tìm xác suất để không có biến cố nào xảy ra, sau đó lấy phần bù. Công thức sẽ là:

$$P(\text{any}) = 1 - P(A_1') \times P(A_2') \times \cdots \times P(A_n')$$

Đó là những công thức có rất nhiều ứng dụng trong các bài toán về xác suất, bạn đọc nên nắm thật vững trước khi bước vào giải các bài tập cụ thể.

Ví dụ 2: Bài toán Nghịch lý ngày sinh (Birthday Paradox)

Trong lý thuyết Xác suất, bài toán Nghịch lý ngày sinh là một bài toán rất nổi tiếng từ thế kỷ $20$. Nghịch lý này đề cập đến một sự thật nghe có vẻ rất trái ngược, đó là chỉ cần $23$ người ở trong cùng một căn phòng thì xác suất tồn tại $2$ người có chung ngày sinh sẽ lớn hơn $50\%$. Bài toán này đã được chứng minh bằng Toán học, các bạn có thể xem thêm tại đây.

Bài toán bây giờ sẽ phức tạp hơn một chút. Cho trước một số nguyên dương $x,$ cần xác định số người $n$ nhỏ nhất trong một căn phòng để xác suất tồn tại hai người có chung ngày sinh là lớn hơn $x\%$.

Yêu cầu: Coi rằng mọi năm đều có $365$ ngày, hãy đi tìm số $n?$

Input:

• Chứa duy nhất số nguyên dương $x$.

Ràng buộc:

• $1 \le x \le 100$.

Output:

• In ra giá trị $n$ nhỏ nhất tìm được.

Sample Input:

70

Sample Output:

30

Ý tưởng

Đôi khi, trong các bài toán xác suất, cách tiếp cận dễ dàng hơn là đi giải bài toán ngược. Hãy gọi $P(same)$ là xác suất để hai người trong phòng có cùng ngày sinh với nhau và $P(different)$ là xác suất để tất cả mọi người trong phòng đều có ngày sinh khác nhau. Khi đó ta có:

$$P(same) = 1 - P(different)$$

Ta sẽ lần lượt thêm từng người vào phòng, đồng thời tính toán $P(different)$ liên tục, cho tới khi đạt được $P(same) > x \Leftrightarrow P(different) \le x$ thì đưa ra số người cần có trong phòng.

Bắt đầu từ căn phòng rỗng, khi thêm người vào thì:

• Người thứ nhất có thể có bất kỳ ngày sinh nào trong $365$ ngày.
• Người thứ hai phải có ngày sinh khác với người thứ nhất, xác suất là $1 - \frac{1}{365}$.
• Người thứ ba phải có ngày sinh khác với hai người trước đó, xác suất là $1 - \frac{2}{365}$. ...
• Người thứ $i$ phải có ngày sinh khác với $i - 1$ người trước đó, xác suất là $1 - \frac{i - 1}{365}$.

Vậy nếu như thêm người thứ $i$ vào, thì xác suất $P(different)$ sẽ trở thành:

$$P(different) = P(different) \times \left(1 - \frac{i - 1}{365}\right)$$

Code mẫu

#include <bits/stdc++.h>

using namespace std;

int min_people(int x)
{
    int people = 1;
    double target = 1 - (double) x / 100;
    double pdiff = 1;
	
    while (pdiff > target)
    {
        pdiff *= (1.0 - (double) people / 365);
        ++people;
    }
	
    return people;
}

main()
{
    int x;
    cin >> x;
	
    cout << min_people(x);
	
    return 0;
}

Như vậy, trong bài viết này, tôi đã giới thiệu tới các bạn những kiến thức cơ bản nhất về chủ đề Xác suất trong Lập trình thi đấu. Để tiếp tục theo dõi phần 2 của bài viết, mời các bạn nhấn vào đây.