GT 9: Tiền xu Chernoff-Bernstein và mẹo trung vị

9. Tiền xu Chernoff-Bernstein và mẹo trung vị

9.1. Tiền xu Chernoff-Bernstein

Thảy ${n}$ lần độc lập một đồng xu mà xác suất ra mặt ngửa là ${p}$ thì trị kỳ vọng của số lần ra mặt ngửa là ${\mu = np}$ . Ông Chernoff bảo rằng xác suất mà tổng số mặt ngửa quấn quít xung quanh $\mu$ sẽ tiến đến ${1}$ theo tốc độ hàm mũ khi ${n}$ tăng. Một bài tập tốt là bạn thử áp dụng bất đẳng thức Markov và bất đẳng thức Chebyshev trong hai bài trước để so sánh với bất đẳng thức Chernoff trong bài này. Bạn sẽ thấy rằng chặn Chernoff tốt hơn hẳn.

Điều kỳ diệu là, ta có thể chứng minh BĐT Chernoff dùng BĐT Markov cộng với cái mẹo dùng hàm sinh mô-măng (moment generating function) của ông Bernstein. Nói đúng ra, ông Berstein đã chứng minh được BĐT kiểu Chernoff từ mấy chục năm trước khi Chernoff chứng minh BĐT Chernoff, chỉ có điều các BĐT Bernstein nằm ở dạng hơi khác thôi. Xem một bài giảng do bác Xuân Long ghi lại. Dùng cái mẹo của Bernstein, chúng ta có thể chứng minh một họ các BĐT loại này. Ta ghi lại đây ba cái chặn căn bản:

Chặn Chernoff: Gọi ${X_1, \dots, X_n \in \{0,1\}}$ là các biến Bernoulli độc lập, trong đó ${\text{Prob}[X_i = 1] = p_i}$ . Đặt ${X = \sum_i X_i}$ thì ${\mu = E[X] = \sum_i p_i}$ . Với ${0 < \delta < 1}$ bất kỳ, ta có

$\displaystyle \text{Prob}[X \geq (1+\delta)\mu] \leq e^{-\mu\delta^2/3}$

$\displaystyle \text{Prob}[X \leq (1-\delta)\mu] \leq e^{-\mu\delta^2/2}$

$\displaystyle \text{Prob}[|X-\mu| \geq \delta\mu] \leq 2e^{-\mu\delta^2/3}$

À, tháng 4 vừa rồi có 2 ông hàng xóm cũ của hòa thượng THT tìm được chứng minh kiểu tổ hợp của các chặn Chernoff. Xem video này và bài này.

9.2. Cái mẹo trung vị

Bây giờ quay lại với bài toán lấy mẫu trong bài GT 8. Chúng ta đã chứng minh được rằng, để đảm bảo ${\text{Prob}[|\bar \mu-\mu| > \epsilon \mu] < \delta}$ thì cần ${\frac{\sigma^2}{\delta\mu^2\epsilon^2}}$ mẫu. Như vậy, nếu ta lấy ${4 \frac{\sigma^2}{\mu^2\epsilon^2}}$ mẫu thì ${\text{Prob}[|\bar \mu-\mu| > \epsilon \mu] < 1/4}$ . Ta gọi ${\bar \mu}$ là một ước lượng yếu. (Yếu vì độ tin cậy là ${1/4}$ thay vì ${\delta}$ tí hin như ta muốn.) Hãy thực hiện độc lập ${m}$ ước lượng yếu ${\bar \mu_1, \dots, \bar \mu_m}$ , và gọi ${\bar \mu_i}$ là ước lượng tốt nếu quả thật ${|\bar \mu_i-\mu| \leq \epsilon \mu}$ . Ta biết xác suất mà ${\bar \mu_i}$ tốt là lớn hơn ${3/4}$ , do đó số ước lượng tốt sẽ giao động xung quanh ${3m/4}$ . Vấn đề là ta không biết ước lượng nào là tốt!

Đến đây thì cái mẹo trung vị xuất hiện. Nếu hơn ${m/2}$ số ước lượng yếu là tốt thì chắc chắn trung vị (median) của đám ${\bar \mu_i}$ sẽ tốt! (Bài tập nhé!)

Do đó nếu thuật toán của ta in ra trung vị ${\mu^*}$ của đám ${\bar \mu_i}$ thì xác suất mà ${\mu^*}$ là ước lượng tốt sẽ lớn hơn xác suất hơn nửa số ước lượng yếu là tốt. Đặt ${X_i = 1}$ nếu ${\bar \mu_i}$ là tốt, và ${X_i=0}$ trong trường hợp còn lại. Thì ${\text{Prob}[X_i=1] > 3/4}$ . Đặt ${X = \sum_i X_i}$ thì ${E[X] > 3m/4}$ . Do đó, theo chặn Chernoff,

$\displaystyle \text{Prob}[X \leq m/2] \leq \text{Prob}[X \leq (1-1/3)E[X]] \leq e^{-(3m/4)(1/3)^2/2} = e^{-m/24}.$

Vì thế, xác suất mà ${\mu^*}$ là tồi sẽ nhỏ hơn ${\delta}$ nếu ${m \geq 24\ln(1/\delta)}$ . Tổng số mẫu chúng ta cần lấy sẽ là

$\displaystyle 24\ln(1/\delta) 4 \frac{\sigma^2}{\mu^2\epsilon^2} = O\left( \frac{\sigma^2}{\mu^2\epsilon^2} \ln(1/\delta) \right)$

nhỏ hơn hẳn số mẫu cần thiết khi dùng chặn Chebyshev.

3 Comments

Phan Dương Hiệu

Posted 23/10/2010 at 5:56 am | Permalink

Chặn Chernoff đúng là rất tốt, để có sai số giảm theo hàm mũ thì chỉ cần poly mẫu và do vậy thực hiện được bởi poly-time machine . Nhưng chặn Chebyshev cũng có những tác dụng rất lớn mà chặn Chernoff không thể cho ta. Một ví dụ rất hay là nó có thể dùng để save randomness. Mấu chốt là muốn dùng chặn Chernoff thì các biến phải độc lạp nhau, trong khi đó chặn Chebyshev không cần điều đó. Chẳng hạn, khi các biến độc lập nhau đôi một (pairwise independent) thì không dùng được chặn Chernoff, trong khi lại dùng được chặn Chebyshev.
Quay lại với vấn đề về saving randomness. Nếu ta có $l$ biến ngẫu nhiên $s_1, \dots,s_l$ thì ta có thể tạo ra $2^l$ biến, mỗi biến $r_I$ ( $I$ là tập con của tập $\{1,2,\dots,l \}$ ) tương ứng với XOR của các biến $s_i$ với $i$ thuộc $I$ . Khi đó các biến $r_I$ và $r_J$ là độc lập với nhau đôi một. Ta có thể sử dụng $2^l$ biến này trong các thí nghiệm của ta và sau đó sử dụng chặn Chebyshev để đánh giá kết quả. Như vậy tóm lại, trong một số trường hợp, thay vì cần $N$ bít ngẫu nhiên thì ta chỉ cần $\log(N)$ bít nữa thôi, tất nhiên phải trả giá là độ sai số không cực tốt. (Đây là kỹ thuật này được Goldreich-Levin sử dụng trong việc xây dựng hard-core predicate từ one-way function)

Hà

Posted 12/08/2011 at 9:27 am | Permalink

NQH wrote: Nếu hơn {m/2} số ước lượng yếu là tốt thì chắc chắn trung vị (median) của đám {\bar \mu_i} sẽ tốt! (Bài tập nhé!)

Thưa anh Hưng, có phải là: nêu TV là trung vị của biến ngẫu nhiên mu, TV là giá trị ngưỡng phân tách trường hợp ước lượng yếu và ước lượng tốt, nên thoả mãn P(mu > TV >= 1/2 và P(mu =1/2. Do vậy, nếu nhiều hơn m/2 số mu là ước lượng yếu là tốt thì chứng tỏ TV đứng lệch về phía số ước lượng yếu là tốt.

- NQH
  
  Posted 13/08/2011 at 12:10 pm | Permalink
  
  Anh Hà, tôi không hiểu câu ” TV đứng lệch về phía số ước lượng yếu là tốt”. Tôi nghĩ anh đã nghĩ sai hướng.
  
  Đại khái, nếu có m ước lượng, mà hơn m/2 trong chúng nằm trong đoạn [a,b] thì chắc chắn trung vị của m ước lượng cũng nằm trong đoạn [a,b]. Khẳng định này không liên quan gì đến xác suất.