Trong bài này mình sẽ giới thiệu những kiến thức cơ bản về xác suất. Do xác suất là một lĩnh vực rất rộng, rất khó để viết toàn bộ những kiến thức cở bản trong một bài viết. Do đó, mình chỉ chọn ra những phần nhất định để trình bày. Những phần này sẽ được áp dụng trong những bài viết sau về phân tích thuật toán ngẫu nhiên.

Sự kiện và xác suất

Trước hết chúng ta định nghĩa những khái niệm cơ bản nhất về không gian xác suất:

Dựa vào định nghĩa 1, ta có bổ đề sau:

 
Chứng minh: dựa vào định nghĩa của hàm xác suất $\mathrm{Pr}$, ta có:

$\begin{array} {lcl}\mathrm{Pr}[E_1] & = & \mathrm{Pr}[E_1 - (E_1 \cap E_2)] + \mathrm{Pr}[E_1\cap E_2] \\ \mathrm{Pr}[E_2] & = & \mathrm{Pr}[E_2 - (E_1 \cap E_2)] + \mathrm{Pr}[E_1\cap E_2] \\ \mathrm{Pr}[E_1 \cup E_2] & = & \mathrm{Pr}[E_1 - (E_1 \cap E_2)] + \mathrm{Pr}[E_2 - (E_1 \cap E_2)] + \mathrm{Pr}[E_1\cap E_2]\end{array}$

Từ đó, suy ra định lý 1.

Từ định lý 1, ta dễ dàng chứng minh được định lý sau bằng quy nạp.

Định lý 1 còn được mở rộng ra trong trường hợp hữu hạn các sự kiện $E_1, E_2,\ldots, E_n$ gọi là nguyên lý bù trừ (inclusion-exclusion principle)

 
Một luật rất quan trọng để tính xác suất là luật tổng xác suất.:

 
Chứng minh: Do các sự kiện $B \cap E_i, 1 \leq i \leq n$ là đôi một không giao nhau, áp dụng tính chất của hàm xác suất ta có:

$\mathrm{Pr}[B] = \sum_{i=1}^n \mathrm{Pr}[B\cap E_i]$

Đẳng thức sau được rút ra từ định nghĩa của xác suất có điều kiện.

Định lý cuối cùng vô cùng quan trọng mình muốn nói đến đó là công thức Bayes:

 
Ta có thể dễ dàng chứng minh công thức Bayes dựa vào luật tổng xác suất.

Ví dụ: Bài toán Monty Hall là một bài toán nối tiếng minh họa việc áp dụng công thức Bayes. Bài toán như sau:

Giả sử trong một trò chơi có 3 cánh cửa, đằng sau một trong 3 cánh của đó là một chiệc xe ô tô và đằng sau hai cánh cửa còn lại là hai con dê. Bạn chỉ được phép mở cánh cửa một lần và phần thưởng cuả bạn là thứ đằng sau cánh cửa đó (tất nhiên là bạn muốn ô tô). Giả sử bạn đã chọn một cánh cửa (nhưng chưa mở), giả sử cánh cửa 1, ban tổ chức trò chơi đó sẽ mở một cánh cửa có con dê, giả sử cánh cửa 2, trong hai cánh cửa còn lại. Bây giờ trước khi bạn quyết định mở, ban tổ chức cho phép bạn đổi cánh cửa 1 và 3. Câu hỏi là bạn có đổi hay không, giả sử xác suất mỗi cánh cửa có ô tô là như nhau và bằng $1/3$?

Phần lớn mọi người khi lần đầu tiên gặp bài toán này sẽ cho rằng đổi hay không cũng không quan trọng vì xác xuất ô tô ở trong cánh cửa 1 và 3 đều bằng nhau và bằng $1/2$ khi bạn đã biết cánh cửa 2 không có ô tô. Ngay cả nhà toán học nổi tiếng Paul Erdős lúc đầu cũng không tin là bạn nên đổi; ông chỉ tin bạn nên đổi sau khi ông đã thử nghiệm giả lập với máy tính.

Vậy tại sao bạn nên đổi. Về mặt trực quan, lý do như sau: ban đầu bạn chọn cánh cửa 1, xác suất ô tô nằm trong cánh cửa 1 là $1/3$. Suy ra nếu bạn không đổi thì xác suất bạn có được ô tô là $1/3$. Còn nếu bạn đổi, xác suất bạn có được ô tô sẽ là $1 - 1/3 = 2/3$. Rõ ràng là bạn nên đổi. Bây giờ chúng ta áp dụng công thức Bayes vào bài toán này:

Gọi $A_1,A_2,A_3$ là xác suất ô tô ở sau cánh cửa $1,2,3$. Gọi $X_1$ là sự kiện người chơi chọn cánh cửa 1 và $H_2$ là sự kiện ban tổ chức mở cánh cửa 2. Như vậy sự kiện ô tô ở cánh cửa thứ 3 là $A_3 | H_2, X_1$. Do đó xác suất ô tô ở trong cánh cửa thứ 3 là $\mathrm{Pr}[A_3 | H_2, X_1]$. Ta có:

$\begin{array} {lcl} \mathrm{P}[H_2 | A_1,X_1] & = & 1/2 \\ \mathrm{P}[H_2 | A_2,X_1] & = & 0 \\ \mathrm{P}[H_2 | A_3,X_1] & = & 1 \end{array}$

Chú ý $A_i$ độc lập với $X_1$ với mọi $i = 1,2,3$, do đó $\mathrm{P}[A_i | X_1] = \mathrm{P}[A_i] = 1/3$. Áp dụng công thức Bayes ta có:

$\begin{array} {lcl} \mathrm{P}[A_3 | H_2,X_1] & = & \frac{\mathrm{P}[H_2 | A_3,X_1]\cdot \mathrm{P}[A_3 | X_1]}{\sum_{i=1}^3 \mathrm{P}[H_2 | A_i,X_1]\cdot \mathrm{P}[A_i |X_1]} = \frac{1\cdot 1/3}{1\cdot 1/3+ 1/2 \cdot 1/3 + 0 \cdot 1/3} = \frac{2}{3}\end{array}$

Biến ngẫu nhiên rời rạc

Trong ứng dụng của xác suất trong phân tích thuật toán ngẫu nhiên, chúng ta chủ yếu (nhưng không phải tất cả) bắt gặp biến ngẫu nhiên rời rạc.

Cụ thể trong định nghĩa trên, với một biến ngẫu nhiên $X$ và một giá trị $a \in \mathbb{R}$, sự kiện "$X = a$" là tập hợp $\{s \in \Omega | X(s) = a\}$, và xác suất của sự kiện này được kí hiệu là $\mathrm{Pr}[X = a]$ và bằng:

$\mathrm{Pr}[X = a] = \sum_{s \in \Omega: X(s) = a} \mathrm{Pr}[s]$

Ví dụ: Gọi $X$ là biến ngẫu nhiên biểu diễn tổng của hai con xúc xắc 6 mặt. Ở đây $\Omega = \{(a,b) | 1\leq a \leq 6, 1 \leq b \leq 6\}$ và:

$\begin{array} {lcl} X: \Omega & \rightarrow & \mathbb{R} \\ (a,b) & \mapsto & a+b \end{array}$

Như vậy, sự kiện $X = 3$ sẽ tương đương với tập hợp $\{(1,2), (2,1)\}$ và có xác suất là:

$\mathrm{Pr}[X = 4] = \frac{2}{36} = \frac{1}{18}$

Tương tự như các sự kiện, ở đây chúng ta cũng có khái niệm các biến ngẫu nhiên độc lập.

 
Với ví dụ biến ngẫu nhiên $X$ là tổng của hai con xúc xắc 6 mặt được định nghĩa trong ví dụ trên, kì vọng của $X$:

$E[X] = 2\cdot \frac{1}{36} + 3\cdot \frac{2}{36} + 4\cdot \frac{3}{36} + \ldots + 12\cdot \frac{1}{36} = 7$

Một tính chất vô cùng quan trong đó là tính tuyến tính của kì vọng. Tính chất này chúng ta sẽ sử dụng trong gần như tất cả các phân tích xác suất.

 
Chứng minh: Ta chỉ cần chứng minh trong trường hợp hai biến ngẫu nhiên và sau đó quy nạp để chứng minh định lý. Gọi hai biến ngẫu nhiên là $X$ và $Y$ với kì vọng tương ứng $E[X], E[Y]$. Theo định nghĩa, ta có:

$\begin{array} {lcl} E[X + Y] & =& \sum_{i}\sum_{j}(i+i)\mathrm{Pr}[(X = i) \cap (Y = j)] \\ & = & \sum_i \sum_j i\cdot \mathrm{Pr}[(X = i) \cap (Y = j)] + \sum_i \sum_j j\cdot \mathrm{Pr}[(X = i) \cap (Y = j)] \\ & = & \sum_i i \sum_j \mathrm{Pr}[(X = i) \cap (Y = j)] + \sum_j j \sum_i \mathrm{Pr}[(X = i) \cap (Y = j)] \\ & = & \sum_i i \mathrm{Pr}[X = i] + \sum_j j \mathrm{Pr}[Y = j] \\ & = & E[X] + E[y] \end{array}$

Điểm mạnh của định lý 3 chính là đẳng thức đúng trong cả trường hợp các biến ngẫu nhiên $X_1,X_2,\ldots, X_n$ phụ thuộc. Tương tự như định lý 3, ta có thể chứng minh:

Tương tự như xác suất có điều kiện, ta có thể định nghĩa kì vọng có điều kiện.

 
Dựa vào định nghĩa ta cũng có thể chứng minh được tính tuyến tính của kì vọng:

 
Với mỗi $Z = z$, kì vọng $E[Y | Z = z]$ phụ thuộc vào $z$. Do đó ta có thể coi kì vọng $E[Y | Z = z]$ như là một biến ngẫu nhiên $f(Z)$, $f(Z = z) = E[Y | Z = z]$. Do đó ta có thể định nghĩa kì vọng cho biến ngẫu nhiên đó. Định lý sau có thể được chứng minh trực tiếp dựa vào định nghĩa:

Một hàm $f: \mathbb{R} \rightarrow \mathbb{R}$ được gọi là lồi nếu với mọi $x_1,x_2$ và $0 \leq \lambda \leq 1$, ta có:

$f(\lambda x_1 + (1 - \lambda)x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2)$

Định nghĩa này rộng hơn định nghĩa trong giải tích mà chúng ta đã biết: nếu một hàm $f(x)$ có đạo hàm cấp 2 $f''(x) \geq 0$ với mọi $x$ thì $f(x)$ là hàm lồi. Ta có bất đẳng thức Jensen cho hàm lồi:

 
Trong trường hợp $f(x)$ có đạo hàm cấp 2, bất đẳng thức này có thể được chứng minh bằng khai triển Taylor và áp dụng tính tuyến tính của kì vọng. Mình bỏ qua chứng minh (bạn đọc có thể xem trong [1]).

Một hệ qủa của định lý trên đó là:

Phương sai (covariance) của một biến ngẫu nhiên là một đại lượng đặc trưng cho sự dao động của biến ngẫu nhiên xung quanh giá trị kì vọng và được định nghĩa như sau:

Từ bổ đề 6 có thể thấy $\mathrm{Var}[X] \geq 0$ với mọi biến ngẫu nhiên $X$.

Ứng dụng: bài toán người thu thập coupon

Ta xét một ứng dụng của phân tích xác suất trong bài toán người sưu tập Coupon (Coupon Collector Problem). Bài toán này cũng được giới thiệu ở đây với cái tên Bài toán Mai Siêu Phong.

Gọi $X$ là số lượng coupon cần mua để thu được ít nhất một coupon trong mỗi loại và gọi $X_i$ là số lượng coupon cần phải mua khi bạn đã thu thập được $i-1$ loại coupon khác nhau. Theo tính tuyến tính của kì vọng, ta có:

$E[X] = \sum_{i=1}^n X_i$

Bây giờ ta sẽ tính kì vọng của $X_i$ với mỗi $i$. Do bạn đã thu tập được $i-1$ loại khác nhau, xác suất khi bạn mua một hộp kẹo có coupon loại mới là

$p_i = 1 - \frac{i-1}{n}$

Ở đây ta cần phải hiểu rõ ý nghĩa của $X_i$. Nếu $X_i = k$ có nghĩa là $k-1$ hộp kẹo đầu tiên bạn mua không có coupon nào mới cả và hộp kẹo thứ $k$ có môt coupon loại mới. Do đó,

$\mathrm{Pr}[X_i = k] = (1-p_i)^{k-1}p_i$

Do đó $X_i$ tuân theo phân phối hình học với tham số $p = p_i$. Ta có:

$E[X_i] = \frac{1}{p_i} = \frac{n}{n-i+1}$

Do đó, ta có:

$E[X] = \sum_{i=1}^n \frac{n}{n-i+1} = n \sum_{i=1}^n \frac{1}{n-i+1} = n \sum_{i=1}^n \frac{1}{i} = nH(n) $

Trong đó $H(n) = \sum_{i=1}^n \frac{1}{n}$ là số đồng điều thứ $n$. Về mặt tiệm cận $H(n) = \theta(\log n)$, hay chính xác hơn, $\ln n \leq H(n) \leq \ln(n)+1$.

Biến ngẫu nhiên 0/1

Trong phân tích thuật toán, biến ngẫu nhiên 0/1 (indicator random variable) rất hay được sự dụng như một phương pháp để chuyển đổi giữa kì vọng và xác suất. Như cái tên của nó, biến ngẫu nhiên 0/1 chỉ nhận hai giá trị 0 và 1.

 
Dựa vào định nghĩa, ta dễ dàng chứng minh định lý sau:

Một tính chất quan trọng của biến ngẫu nhiên 0/1 mà ta thường hay sử dụng trong các phân tích xác suất là:

 
Chứng minh: $E[X^2] = 1^2 p + 0^2(1-p) = p = E[X]$, trong đó $p$ là xác suất $X = 1$.

Tham khảo

[1] Mitzenmacher, Michael, and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
[2] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7.