ball-and-bin

You are currently browsing articles tagged ball-and-bin.

Trong bài này, mình giới thiêu 5 công cụ cơ bản từ lý thuyết xác suất để phân tích các giải thuật ngẫu nhiên. Nếu theo dõi các bài vết về giải thuật ngẫu nhiên trong blog của mình (hashing, randomized quicksort, v.v.) bạn sẽ thấy hầu hết các bài viết chỉ sử dụng 5 công cụ này thôi. Bài này chủ yếu viết lại note của Tim Roughgarden [1]. Mình khuyến khích các bạn đọc bản gốc.

Trước đây mình có viết một bài về xác suất cơ bản đề cập tới một số khái niệm như thế nào là một biến ngẫu nhiên, kì vọng, etc. Mình sẽ không nhắc lại các khái niệm đó tại đây.

Công cụ 1: Tính tuyến tính của kì vọng

Gọi $X_1,X_2,\ldots, X_n$ là $n$ biến ngẫu nhiên trong cùng một không gian xác suất $\Omega$. Gọi $X = \sum_{i=1}^n X_i$, ta có:

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

Điều đặc biệt quan trọng khiến đẳng thức $(1)$ trở thành một cung cụ mạnh đó là nó đúng ngay cả khi các biến ngẫu nhiên $X_1, X_2, \ldots, X_n$ phụ thuộc lẫn nhau. Trong các công cụ sẽ giới thiệu dưới đây, một số công cụ yêu cầu các biến ngẫu nhiên phải có tính độc lập cao.

Ví dụ 1: Ta sẽ minh họa ứng dụng của tính tuyến tính của kì vọng trong bài toán Max-Exact-$3$-Sat.

Max-Exact-$3$-Sat: Cho $n$ biến boolean $\{x_1,x_2,\ldots, x_n\}$ và một tập $m$ các mệnh đề (clause) $\Phi = \{\varphi_1, \ldots, \varphi_m\}$, trong đố mỗi mệnh đề là tuyển của đúng 3 literals. (Mỗi literal là một biến hoặc phủ của biến đó.). Tìm cách gán True/False cho các biến sao cho số mệnh đề có giá trị True trong $\Phi$ là lớn nhất.

 
Ta gọi một mệnh đề có giá trị True là một mệnh đề được thỏa mãn (satisfied). Ví dụ ta có 3 biến boolean và $\Phi = \{ (x_1 \vee x_2 \vee \bar{x}_3), (\bar{x}_1 \vee x_2 \vee \bar{x}_3), $ $ (\bar{x}_1 \vee \bar{x}_2 \vee x_3)\}$, ta có thể gán $(x_1,x_2,x_3) = $ (True, False, False). Khi đó toàn bộ các mệnh đề của $\Phi$ đều được thỏa mãn.

Theorem 1: Tồn tại một cách gán giá trị True/False cho các biến sao cho ít nhất $7/8$ số mệnh đề của $\Phi$ được thỏa mãn.

 

Chứng minh: Gán cho mỗi biến ngẫu nhiên giá trị True/False. Gọi $X_i$ là biến ngẫu nhiên 0/1 cho sự kiện mệnh đề thứ $i$, $\varphi_i$, được thỏa mãn ($X_i = 1$ nếu $\varphi_i$ được thỏa mãn và ngược lại, $X_i= 0$). Số mệnh đề được thỏa mãn của $\Phi$ là:

$X = \sum_{i=1}^m X_i \qquad (2)$

Do $\varphi_i$ có đúng 3 literals, $\varphi_i$ thỏa mãn nếu ít nhất một trong 3 literals có giá trị True. Do đó, ta có:

$\mathrm{Pr}[X_i = 1] = 1 - \frac{1}{8} = 7/8 \qquad (3)$

Vì $X_i$ là biến ngẫu nhiên 0/1, $E[X_i] = \mathrm{Pr}[X_i = 1] = 7/8$. Theo tính tuyến tính của kì vọng, ta có:

$E[X] = \sum_{i=1}^m [X_i] = \frac{7m}{8} \qquad (4)$

Nhận xét thấy, với mọi biến ngẫu nhiên, luôn tồn tại một giá tri của biến lớn hơn hoặc bằng kì vọng. Do đó, luôn tồn tại một cách gán sao cho $X \geq E[X] = \frac{7m}{8}$.


Chứng minh trên cũng cho chúng ta một giải thuật ngẫu nhiên khá đơn giản với thời gian đa thức tìm một cách gán thỏa mãn ít nhất $7/8$ số mệnh đề của $\Phi$. Håstad [4] chứng minh rằng nếu P $\not=$ NP, không có giải thuật nào có thể thực hiện tốt hơn giải thuật ngẫu nhiên trên trong thời gian đa thức.

Trong nhiều trường hợp, kì vọng của một biến ngẫu nhiên cũng không cho chúng ta quá nhiều thông tin. Thông tin quan trọng hơn đó là giá trị của biến ngẫu nhiên thay đổi như thế nào so với kì vọng của chúng. Ba công cụ tiếp theo cho phép chúng ta ước lượng được sự thay đổi này dựa trên những thông tin mà ta có, bên cạnh kì vọng, của các biến ngẫu nhiên.

Công cụ 2: Bất đẳng thức Markov

Markov's Inequality: Cho một biến ngẫu nhiên $X$ không âm, với mọi hằng số $c$ > $1$, ta có:

$\mathrm{Pr}[X \geq c E[X]] \leq \frac{1}{c} \qquad (5)$

 
Chứng minh: Gọi $f(x)$ là hàm mật độ xác suất. Theo định nghĩa của kì vọng, ta có:

$\begin{array} {l} E[X] & = \int_{-\infty}^{+\infty} f(x) x dx\\ & \geq \int_{cE[X]}^{+\infty} f(x) x dx \\ &\geq cE[X]\int_{cE[X]}^{+\infty} f(x) dx \\ &= cE[X] \mathrm{Pr}[X \geq c E[X]] \end{array}$


Ví dụ 2: Trong bài giải thuật Quicksort ngẫu nhiên, ta tính được kì vọng thời gian của Quicksort khi chọn pivot ngẫu nhiên là $E[T(n)] = O(n\log n)$. Theo bất đẳng thức Markov, xác suất để giải thuật này chạy lâu hơn 10 lần $E[T(n)]$ là không quá $10\%$.

Liệu bất đẳng thức Markov đã thực sự chặt? Câu trả lời là có. Nếu không có thông tin gì thêm ngoại trừ kì vọng thì bất đẳng thức Markov là tốt nhất có thể (xem bài tập 1).

Trong hầu hết các trường hợp, bất đẳng thức Markov không cho chúng ta nhiều thông tin giá trị. Tuy nhiên, bất đẳng thức Markov lại là công cụ phổ biến để chứng minh các bất đẳng thức khác khi chúng ta có thêm thông tin về biến ngẫu nhiên.

Công cụ 3: Bất đẳng thức Chebyshev

Giả sử ngoài giá trị kì vong $E[X]$, ta còn có ước lượng của phương sai (variance) $Var[X]$. Gọi $\sigma(X) = \sqrt{Var[X]}$ là độ lệch tiêu chuẩn (standard deviation) của $X$.

Chebyshev's Inequality: Với mọi hằng số $c$ > $1$, ta có:

$\mathrm{Pr}[|X - E[X]| \geq c \cdot \sigma(X)] \leq \frac{1}{c^2} \qquad (6)$

 
Chứng minh: Gọi $Y = (X - E[X])^2$. $Y$ là một biến ngẫu nhiên với kì vọng $E[Y] = E[X^2] - (E[X])^2 = Var[X]$. Do đó, ta có:

$\begin{array} {l} \mathrm{Pr}[|X - E[X]| \geq c \cdot \sigma(X)] & = \mathrm{Pr}[(X - E[X])^2 \geq c^2 Var[X]] \\ &= \mathrm{Pr}[Y \geq c^2 E[Y]] \\ &\leq \frac{1}{c^2} \end{array}$

Bất đẳng thức cuối cùng là do ta sử dụng bất đẳng thức Markov.


Bất đẳng thức Chebyshev cũng là tốt nhất có thể nếu bạn chỉ có ước lượng về kì vọng và phương sai (xem bài tập 2).

Ví dụ 3: Giả sử bạn đang thiết kế lại một trang web bán hàng của bạn. Trang web này có khoảng 1 triệu khách hàng viếng thăm và bạn muốn kiểm tra xem bao nhiêu khách hàng sẽ thích giao diện mới. Tuy nhiên, bạn không thể thay đổi luôn giao diện và đếm thử vì nếu trong trường hợp rất nhiều khách hàng không thích, bạn có thể mất một lượng lớn khách hàng. Các bạn làm là lấy mẫu ra một số lượng khách hàng rất nhỏ $n$ và hỏi họ xem họ thích hay không thích, và từ đó tính được ước lượng số khách hàng thích trong một triệu khách hàng bằng cách chia tỉ lệ. Nếu bạn muốn ước lượng của bạn, với xác suất ít nhất $3/4$, lệch không quá $10\%$ thì bạn cần phải lấy mẫu bao nhiêu người?

Lời giải: Giả sử xác suất một người thích giao diện mới của bạn là $p$ ($10^6*p$ là số người thích giao diện mới trong 1 triệu người). Gọi $X_i$ là sự kiện người thứ $i$ trong tập $n$ người ngẫu nhiên thích giao diện mới. Ta có $E[X_i] = p$ và $Var[X_i] = p(1-p)$. Gọi $X$ là số người trong $n$ người chọn ra thích giao diện mới. Ta có:

$X = \sum_{i=1}^n X_i \qquad (7)$

Theo tính tuyến tính của kì vọng, $E[X] = np$. Do $X_i$ là các biến ngẫu nhiên độc lập, ta có $Var[X] = \sum_{i=1}^n Var[X_i] = np(1-p)$. Theo bất đẳng thức Chebyshev, ta có:

$\begin{array}{l} \mathrm{Pr}[|X - E[X]| \geq 0.01 n] &= \mathrm{Pr}[|X - E[X]|\geq \frac{0.01 n}{\sqrt{np(1-p)}} \sqrt{np(1-p)}] \\ & \leq \frac{np(1-p)}{0.01^2 n^2} \\ &\leq \frac{1}{4\cdot 0.01^2 \cdot n}\end{array} \qquad (8)$

Để xác suất này không quá $1/4$, ta chọn $n = 100^2 = 10000$. Như vậy, nếu bạn lấy mẫu khoảng 10.000 người thì ước lượng của bạn sai lệch khoảng $1\%$ với xác suất ít nhất $75\%$.


Tổng quát hóa ví dụ trên, nếu bạn muốn ước lượng chính xác tới một hằng số $\delta \geq 1/2$ với xác suất ít nhất $1-\epsilon$ ($\epsilon \geq 1/2$), áp dụng bất đẳng thức Chebyshev, bạn nên lấy mẫu khoảng:

$n = \frac{1}{4\epsilon\delta^2} \qquad (9)$

Chi tiết chứng minh coi như bài tập cho bạn đọc (bài tập 3). Áp dụng $(9)$ cho ví dụ ban đầu với $\delta = 0.01$ và $\epsilon = 1/4$, ta được $n = 100^2$.

Công cụ 4: Bất đẳng thức Chernoff

Bất đẳng thức Chernoff cho phép chúng ta ước lượng sự thay đổi giá trị của một biến ngẫu nhiên xung quanh kì vọng của nó khi biết rằng biến đó là tổng của nhiều biến ngẫu nhiên độc lập.

Chernoff Bounds: Giả sử $X = \sum_{i=1}^n X_i$ trong đó $X_1,X_2,\ldots, X_n$ là $n$ biến ngẫu nhiên độc lập có giá trị trong đoạn $[0,1]$. Gọi $\mu = E[X]$. Ta có:

  • Với mọi $\delta $> $0$,

    $\mathrm{Pr}[X \geq (1+\delta) \mu ] \leq \left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\qquad (10)$

  • Với mọi $\delta \in (0,1)$,

    $\mathrm{Pr}[X \geq (1-\delta) \mu ] \leq e^{-\delta^2\mu/2}\qquad (11)$

 
Bất đẳng thức $(10)$ trông không được đẹp. Trong nhiều trường hợp, ta chủ yếu ước lượng cả cận trên và cận dưới của $X$ với $\delta \in (0,1)$. Khi đó, người ta thường sử dụng hệ quả sau của Chernoff bound.

Corollary 1: Với mọi $\delta \in (0,1)$,

$\mathrm{Pr}[|X - \mu| \geq \delta \mu ] \leq 2 e^{-\delta^2\mu/3}\qquad (12)$

 

Khi $\delta \gg 1$, hệ quả sau thường được sử dụng:

Corollary 2: Với mọi $\delta \gg 1$,

$\mathrm{Pr}[X \geq(1+\delta) \mu ] \leq e^{-\delta^2\mu/(2+\delta)}\qquad (13)$

 

Mình sẽ không chứng minh các bất đẳng thức này. Thay vào đó, mình sẽ hướng dẫn chi tiết từng bước trong bài tập 4 để các bạn có thể tự chứng minh. Trường hợp các bạn các bạn cần lời giải thì có thể xem trong note của Goemans [5].

Ví dụ 4: Trở lại ví dụ trong phần 4, để ý thấy $X$ là tổng của các biến ngẫu nhiên độc lập $X_i, i = 1, \ldots, n$ cùng nhận giá trị $\{0,1\}$ và có cùng xác suất $\mathrm{Pr}[X_i = 1] = p$. Theo Chernoff bound (12), ta có:

$\begin{array}{l} \mathrm{Pr}[|X - E[X]| \geq \delta n] &= \mathrm{Pr}[|X - E[X]|\geq \frac{\delta }{p} np] \\ & \leq 2e^{-3\frac{\delta^2 np}{p^2}} \\ &= 2e^{-3\frac{\delta^2 n}{p}} \\ &\leq 2e^{-3\delta^2 n}\end{array} $

Do đó, để xác suất này không quá $\epsilon$, ta chỉ cần chọn $n$ sao cho:

$2e^{-3\delta^2 n} = \epsilon$

Từ đó ta suy ra:

$n = \ln(\frac{2}{\epsilon}) \frac{1}{\delta^2} \qquad (14)$

So với $(9)$ thì phụ thuộc của $n$ vào $\epsilon$ trong (14) tốt hơn theo hàm mũ, còn sự phụ thuộc vào $\delta$ không thay đổi. Do đó, khi ta biết các biến ngẫu nhiên độc lập với nhau thì ta nên sử dụng Chernoff bound.

Ví dụ 5: Xét bài toán sau: ném $n$ quả bóng vào $n$ cái rổ một cách ngẫu nhiên. Hỏi rổ đầy nhất có bao nhiêu quả bóng (với xác suất cao)?

Tất nhiên là rổ đầy nhất có thể có đến $n$ quả bóng, nhưng xác suất xảy ra trường hợp này cực kì nhỏ. Ta đã xét bài toán này trong phần lý thuyết băm. Sau một loạt các câu hỏi thì kết quả cuối cùng là:

Theorem 2: Với xác suất ít nhất $1 - \frac{1}{n}$, rổ đầy nhất có không quá $\frac{3\ln n}{\ln \ln n}$ quả bóng.

 

Trong bài này, ta sẽ chứng minh Theorem 2 sử dụng Chernoff Bound.

Ta sẽ tìm xác suất rổ đầu tiên có nhiều hơn $\frac{3\ln n}{\ln \ln n}$ quả bóng. Gọi $X_i$ là sự kiện quả thứ $i$ được ném vào rổ $1$. $\mathrm{Pr}[X_i] = \frac{1}{n} = E[X_i]$. Gọi $X = \sum_{i=1}^n X_i$. Theo tính tuyến tính của kì vọng $E[X] = 1$. Do các biến $X_i$ là độc lập, theo Chernoff Bound $(10)$, ta có:

$\mathrm{Pr}[X \geq \frac{3\ln n}{\ln \ln n}] \leq (\frac{3\ln\ln n}{ \ln n})^{\frac{e \ln\ln n}{3\ln n}} \leq \frac{1}{n^2} \qquad (15)$

Trong $(15)$, ta sử dụng tính chất $\frac{\ln n}{\ln \ln n}$ xấp xỉ là nghiệm của $x^x = n$.

Theo $(15)$, xác suất để một rổ cố định bất kì có nhiều hơn $\frac{3\ln n}{\ln \ln n}$ quả bóng là không quá $1/n^2$. Do đó, xác suất để tồn tại một rổ nào đó có nhiều hơn $\frac{3\ln n}{\ln \ln n}$ quả bóng là không quá $1/n$. Như vậy, với xác suất $1-\frac{1}{n}$, mọi rổ (do đó, rổ đầy nhất) đều có không quá $\frac{3\ln n}{\ln \ln n}$ quả bóng.


Trong bài tập 5, ta sẽ chứng minh rằng nếu ném ngẫu nhiên $n\log n$ quả bóng vào $n$ rổ thì với xác suấ ít nhất $1 - 1/n$, rổ đầy nhất có không quá $O(\log n)$ quả bóng. Trong trường hợp này, số quả bóng trong trường hợp xấu nhất cũng chỉ lớn hơn kì vọng hằng số lần mà thôi!!!

Công cụ 5: Union Bound

Union Bound: Gọi $E_1,E_2,\ldots E_n$ là tập $n$ sự kiện, ta có:

$\mathrm{Pr}[\mbox{ ít nhất một sự kiện }E_i \mbox{ xảy ra}] \leq \sum_{i=1}^n \mathrm{Pr}[E_i] \qquad (16)$

 

Bạn đọc có thể hỏi: tại sao lại phát biểu $(16)$ thành một công cụ riêng. Chả phải $(16)$ rất hiển nhiên sao, ít nhát là đối với các bạn có kiến thức sơ khai về xác suất? Đúng là $(16)$ rất hiển nhiên, và nó đúng ngay cả khi các sự kiện $E_i$ phụ thuộc vào nhau. Đó cũng chính là sức mạnh của công cụ này.

Thông thường, theo kinh nghiệm của mình, các bài toán mà ta quan tâm đòi hỏi tìm xác suất để một tập các sự kiện $A_1,A_2,\ldots, A_k$ đồng thời xảy ra. Nhưng các sự kiện đó có thể phụ thuộc, nên ta không thể áp dụng công thức nhân xác suất $\mathrm{Pr}[A_i \wedge A_j] = \mathrm{Pr}[A_i] \cdot \mathrm{Pr}[A_j]$. Cách làm là ta sẽ chuyển về sử dụng union bound thông qua luật Demorgan. Để mình minh họa thông qua ví dụ ném bóng vào rổ ở trên.

Gọi $A_i$ là sự kiện rổ thứ $i$ có không quá $\frac{3\ln n}{\ln \ln n}$ quả bóng. Theo $(15)$, $\mathrm{Pr}[\bar{A}_i] \leq 1/n^2$ hay $\mathrm{Pr}[A_i] \geq 1-1/n^2$. Để chứng minh Theorem 2, ta phải chứng minh:

$\mathrm{Pr}[A_1 \wedge A_2 \wedge A_n] \geq 1 - 1/n \qquad (17)$

Đương nhiên là các sự kiện $A_i$ phụ thuộc, ta không thể áp dụng công thức nhân xác suất. Sử dụng luật Demorgan, ta có:

$\begin{array}{l} \mathrm{Pr}[\overline{A_1 \wedge A_2 \wedge \ldots \wedge A_n}] &= \mathrm{Pr}[\bar{A}_1 \vee \bar{A}_2 \vee \ldots \vee \bar{A}_n] \\ & \leq \sum_{i=1}^n\mathrm{Pr}[\bar{A}_i] \\ &\leq \sum_{i=1}^n \frac{1}{n^2} = \frac{1}{n}\end{array} \qquad (18)$

Từ đó ta suy ra $(17)$. Không khó để thấy rằng phương trình gần cuối của $(18)$ ta áp dụng union bound.

Công cụ 6: Áp đặt điều kiện

Tại sao tiêu đề là 5 công cụ mà ở đây lại lòi ra công cụ thứ 6. Bản thân mình thì thấy công cụ thứ 6 này rất hữu dụng trong việc tính xác suất, nhưng lại chưa tìm ra ví dụ đơn giản để minh họa. Các ví dụ mình biết đều quá phức tạp, do đó, mình sẽ bổ sung và thay đổi tiêu đề bài viết khi đã tìm được ví dụ phù hợp.

Ý tưởng của công cụ này là khi ta quan tâm đến sự kiện $X$, nhưng lại rất khó để tính $\mathrm{Pr}[X]$ một cách trực tiếp. Tuy nhiên, tính xác suất $\mathrm{Pr}[X| Y]$ lại rất dễ, trong đó, $Y$ là một sự kiện xảy ra với xác suất cao, i.e, $\mathrm{Pr}[Y] \geq 1-\epsilon$ với $\epsilon$ vô cùng nhỏ. Lúc này, ta có thể tính $\mathrm{Pr}[X]$ một cách tương đối, theo công thức Bayes, như sau:

$\begin{array}{l} \mathrm{Pr}[X] &= \mathrm{Pr}[X |Y]\mathrm{Pr}[Y] + \mathrm{Pr}[X |\bar{Y}]\mathrm{Pr}[\bar{Y}] \\ & \leq \mathrm{Pr}[X |Y] + \mathrm{Pr}[\bar{Y}] \\ &\leq \mathrm{Pr}[X |Y] + \epsilon \end{array} \qquad (19)$

Do đó, ta có thể ước lượng $\mathrm{Pr}[X]$ thông qua tính $\mathrm{Pr}[X |Y]$, mà ta biết là dễ tính hơn nhiều. Ở đây mình chưa có ví dụ minh họa nên có thể mọi thứ chưa có ý nghĩa nhiều. Phần này chủ yế là ghi chú cá nhân để cập nhật sau.

Tham khảo

[1] T. RoughardenTim. Five Essential Tools for the Analysis of Randomized Algorithms. Stanford, 2016.
[2] T. Rougharden and G. Valiant. Sampling and Estimation. Stanford, 2016.
[3] László Kozma. Inequalities Cheat Sheet.
[4] J. Håstad. Some Optimal Inapproximability Results. Journal of the ACM (JACM) 48.4 (2001): 798-859.
[5] M. Goemans. Chernoff Bounds, and Some Applications. MIT, 2015.

Bài tập

Bài tập 1: Gọi $X$ là một biến ngẫu nhiên 0/1 trong đó $\mathrm{Pr}[X = 1] = 1/k$. Chứng minh rằng $\mathrm{Pr}[X \geq cE[X]] \leq 1/c$.

Bài tập 2: Gọi $Z$ là một biến ngẫu nhiên có phân phối:

$Z = \begin{cases} k, & \mbox{with probability } \frac{1}{2k^2} \\ 0, & \mbox{with probability } 1-\frac{1}{k^2} \\ -k, & \mbox{with probability } \frac{1}{2k^2}\end{cases}$

Chứng minh rằng (a) $E[Z] = 0$, (b) $Var[Z] = 1$ và (c) $\mathrm{Pr}[|Z \geq k|] \leq 1/k^2$.

Bài tập 3: Chứng minh công thức $(9)$ cho trường hợp tổng quát của ví dụ 3.

Bài tập 4: Trong bài tập này, mình sẽ hướng dẫn các bạn chứng Chernoff Bound khi các biến $X_i$ chỉ nhận 1 trong 2 giá trị 0/1. Gọi $\mu_i = \mathrm{Pr}[X_i] = E[X_i]$. Ta có $\mu = \sum_{i=1}^n\mu_i$. Gọi $s$ và $a$ là hai số không âm bất kì.

  1. Chứng minh rằng với mọi $i$, $E[e^{sX_i}] \leq e^{(e^s-1)\mu_i}$. Bạn có thể cần phải sử dụng bất đẳng thức $1+y \leq e^{y}$.
  2. Dùng bất đẳng thức Markov, chứng minh rằng $\mathrm{Pr}[X \geq a] \leq \frac{E[e^{sX}]}{e^{sa}}$.
  3. Sử dụng tính độc lập của các biến $X_i$ và câu (a), chứng minh rằng $E[e^{sX}] \leq e^{(e^s-1)\mu}$
  4. Từ câu (b) và (c), chọn $a = (1+\delta)\mu$, $s = \ln(1+\delta)$, chứng minh bất đẳng thức $(10)$.

Bài tập 5: Giả sử ta ném $n \log n$ quả bóng vào $n$ cái rổ, chứng minh rằng với xác suất $1 - \frac{1}{n}$, rổ đầy nhất có không quá $O(\log n)$ quả bóng.

Tags: , , ,

« Older entries