8. Con gà của ông Chebyshev
8.1. Khoảng cách giữa tư bản hút máu và xã hội chủ nghĩa
Tiếp theo bài trước, hãy nói về con gà của bác nông dân. Bác nông dân và địa chủ ăn hết một con gà, nhưng địa chủ ăn sạch cả con, bao gồm xương, lông, cánh, và phao câu. Tí và Tèo cũng ăn hết một con gà. Mỗi đứa làm đúng một nửa. Trung bình mỗi người cũng là nửa con. Hai vec-tơ phân phối thịt gà 
và 
đều có trị trung bình là 
, nhưng một đằng là tư bản hút máu, một đằng là xã hội chủ nghĩa. Thế thì giá trị trung bình không cung cấp đủ thông tin để phân biệt giữa TBHM và XHCN. Cần thêm thông tin.
Để phân biệt giữa hai thái cực thì ta định nghĩa một hàm khoảng cách. Cặp XHCN (Tí, Tèo) 
là một điểm trên mặt phẳng. Cặp TBHM (Địa chủ, Nông Dân) 
là điểm khác. Hàm khoảng cách tự nhiên nhất là khoảng cách Euclid. Dễ thấy rằng phân phối thịt gà 
có khoảng cách Euclid đến XHCN càng nhỏ thì 
và 
càng gần bằng nhau, xã hội càng gần công bằng, dân chủ, văn minh, mỗi người ăn càng gần nửa con gà bất kể kích thước bao tử. (Để đo mức độ tư bản hút máu, dĩ nhiên khoảng cách Euclid không phải là chọn lựa duy nhất. Có thể dùng chỉ số GINI hay một trăm tỉ các hệ số khác do bọn tư bản rỗi hơi nghĩ ra.)
Ông Chebyshev bảo rằng, nếu cho ông ấy biết thêm khoảng cách đến XHCN thì ông ấy sẽ cho mình ước lượng tốt hơn số trọc phú, số vô sản, hoặc số trung lưu. Khoảng cách đến CNXH được đo bằng độ lệch chuẩn (standard deviation) 
, có giá trị bằng căn bậc hai của phương sai (variance) 
. Độ lệch chuẩn trong ví dụ trên là chiều dài (Euclid) của con đường quá độ lên CNXH chia cho căn của tổng dân số. (Sở dĩ ta chia cho căn của tổng dân số là để cho số đo này ít bị ảnh hưởng bởi số dân, chi tiết này không quan trọng lắm trong ngữ cảnh của chúng ta.) Cụ thể hơn, gọi 
là một biến ngẫu nhiên trên một phân bố bất kỳ (không nhất thiết là phân bố đều) với trị kỳ vọng ![{\mu = E[X]}](http://s.wordpress.com/latex.php?latex=%7B%5Cmu%20%3D%20E%5BX%5D%7D&bg=ffffff&fg=000000&s=0 "{\mu = E[X]}")
, phương sai ![{\sigma^2 = E[(X - \mu)^2]}](http://s.wordpress.com/latex.php?latex=%7B%5Csigma%5E2%20%3D%20E%5B%28X%20-%20%5Cmu%29%5E2%5D%7D&bg=ffffff&fg=000000&s=0 "{\sigma^2 = E[(X - \mu)^2]}")
thì với mọi 
,
8.2. Ứng dụng trong một bài toán lấy mẫu
Một vấn đề cơ bản ta gặp thường xuyên trong thiết kế các thuật toán cho dòng dữ liệu là: ta phải ước lượng trị kỳ vọng của một biến ngẫu nhiên . Luật số lớn đại khái cho ta biết rằng nếu ta lấy 
mẫu và dùng trị trung bình 
của các mẫu để ước lượng 
thì 
Nghĩa là lấy càng nhiều mẫu (độc lập) thì ước lượng càng chính xác.
Bài toán lấy mẫu: cho trước 
, cần lấy ít nhất bao nhiêu mẫu để cho
![{\text{Prob}[|\bar \mu-\mu| \leq \epsilon \mu] \geq 1- \delta}](http://s.wordpress.com/latex.php?latex=%7B%5Ctext%7BProb%7D%5B%7C%5Cbar%20%5Cmu-%5Cmu%7C%20%5Cleq%20%5Cepsilon%20%5Cmu%5D%20%5Cgeq%201-%20%5Cdelta%7D&bg=ffffff&fg=000000&s=0 "{\text{Prob}[|\bar \mu-\mu| \leq \epsilon \mu] \geq 1- \delta}")
Trong đó 
gọi là độ sai lệch, và 
là độ tin cậy.
Nếu ta biết (hoặc chặn trên được) phương sai của thì có thể trả lời tương đối tốt câu hỏi trên. Giả sử ta lấy mẫu độc lập 
, và gọi 
là tổng của mẫu này. Do ![{E[X_i] = \mu}](http://s.wordpress.com/latex.php?latex=%7BE%5BX_i%5D%20%3D%20%5Cmu%7D&bg=ffffff&fg=000000&s=0 "{E[X_i] = \mu}")
, ![{\text{Var}[X_i] = \sigma^2}](http://s.wordpress.com/latex.php?latex=%7B%5Ctext%7BVar%7D%5BX_i%5D%20%3D%20%5Csigma%5E2%7D&bg=ffffff&fg=000000&s=0 "{\text{Var}[X_i] = \sigma^2}")
và các biến này độc lập, dễ thấy rằng ![{E[Y] = n\mu}](http://s.wordpress.com/latex.php?latex=%7BE%5BY%5D%20%3D%20n%5Cmu%7D&bg=ffffff&fg=000000&s=0 "{E[Y] = n\mu}")
và ![{\text{Var}[Y] = n\sigma^2}](http://s.wordpress.com/latex.php?latex=%7B%5Ctext%7BVar%7D%5BY%5D%20%3D%20n%5Csigma%5E2%7D&bg=ffffff&fg=000000&s=0 "{\text{Var}[Y] = n\sigma^2}")
. Từ đó, bất đẳng thức Chebyshev dẫn đến:
![\displaystyle \text{Prob}[|\bar \mu-\mu| > \epsilon \mu] = \text{Prob}[|Y - n\mu| > n\epsilon \mu] \leq \frac{\sigma^2}{n\mu^2\epsilon^2}.](http://s.wordpress.com/latex.php?latex=%5Cdisplaystyle%20%20%5Ctext%7BProb%7D%5B%7C%5Cbar%20%5Cmu-%5Cmu%7C%20%3E%20%5Cepsilon%20%5Cmu%5D%20%3D%20%5Ctext%7BProb%7D%5B%7CY%20-%20n%5Cmu%7C%20%3E%20n%5Cepsilon%20%5Cmu%5D%20%5Cleq%20%5Cfrac%7B%5Csigma%5E2%7D%7Bn%5Cmu%5E2%5Cepsilon%5E2%7D.%20&bg=ffffff&fg=000000&s=0 "\displaystyle \text{Prob}[|\bar \mu-\mu| > \epsilon \mu] = \text{Prob}[|Y - n\mu| > n\epsilon \mu] \leq \frac{\sigma^2}{n\mu^2\epsilon^2}.")
Do đó, chọn 
mẫu là đủ.
Ta có thể làm tốt hơn thế dùng cái mẹo gọi là mẹo trung vị (median trick). Để mô tả nó thì ta cần dùng các đồng xu của ông Chernoff để mua con gà của ông Chebyshev. Xem hồi sau sẽ rõ.
Chủ đề : Thuật Toán, Xác suất & thống kê and tagged Chặn Chebyshev, xác suất. Bookmark the
permalink. Trackbacks are closed, but you can .
![\displaystyle \text{Prob}[X - \mu \geq k \sigma] \leq \frac{1}{1+k^2}.](http://s.wordpress.com/latex.php?latex=%5Cdisplaystyle%20%20%5Ctext%7BProb%7D%5BX%20-%20%5Cmu%20%5Cgeq%20k%20%5Csigma%5D%20%5Cleq%20%5Cfrac%7B1%7D%7B1%2Bk%5E2%7D.%20&bg=ffffff&fg=000000&s=0 "\displaystyle \text{Prob}[X - \mu \geq k \sigma] \leq \frac{1}{1+k^2}.")
![\displaystyle \text{Prob}[X - \mu \leq - k \sigma] \leq \frac{1}{1+k^2}.](http://s.wordpress.com/latex.php?latex=%5Cdisplaystyle%20%20%5Ctext%7BProb%7D%5BX%20-%20%5Cmu%20%5Cleq%20-%20k%20%5Csigma%5D%20%5Cleq%20%5Cfrac%7B1%7D%7B1%2Bk%5E2%7D.%20&bg=ffffff&fg=000000&s=0 "\displaystyle \text{Prob}[X - \mu \leq - k \sigma] \leq \frac{1}{1+k^2}.")
![\displaystyle \text{Prob}[|X - \mu| \geq k \sigma] \leq \frac{1}{k^2}.](http://s.wordpress.com/latex.php?latex=%5Cdisplaystyle%20%20%5Ctext%7BProb%7D%5B%7CX%20-%20%5Cmu%7C%20%5Cgeq%20k%20%5Csigma%5D%20%5Cleq%20%5Cfrac%7B1%7D%7Bk%5E2%7D.%20&bg=ffffff&fg=000000&s=0 "\displaystyle \text{Prob}[|X - \mu| \geq k \sigma] \leq \frac{1}{k^2}.")
![\displaystyle \text{Prob}[|X - \mu| \leq k \sigma] \geq 1- \frac{1}{k^2}.](http://s.wordpress.com/latex.php?latex=%5Cdisplaystyle%20%20%5Ctext%7BProb%7D%5B%7CX%20-%20%5Cmu%7C%20%5Cleq%20k%20%5Csigma%5D%20%5Cgeq%201-%20%5Cfrac%7B1%7D%7Bk%5E2%7D.%20&bg=ffffff&fg=000000&s=0 "\displaystyle \text{Prob}[|X - \mu| \leq k \sigma] \geq 1- \frac{1}{k^2}.")
10 Comments
“Do đó, chọn {n \geq \frac{\sigma^2}{\delta\mu^2\epsilon^2}} mẫu là đủ. ”
Cảm ơn anh Hưng rất nhiều.
@Anh Hà: không có chi. Anh xem bài sau (GT 9) sẽ thấy kết quả tốt hơn.
cái này sai rồi ông ơi, chắc cái này học nhiều quá nên rồ
NQH wrote: “Khoảng cách đến CNXH được đo bằng độ lệch chuẩn (standard deviation) {\sigma}, có giá trị bằng căn bậc hai của phương sai (variance) ”
CNHX có phải là E[X]? vì (standard deviation) {\sigma}=E[(X-E[X])^2].
Vâng, cái “tâm” (trị kỳ vọng,![E[X]](http://s.wordpress.com/latex.php?latex=E%5BX%5D&bg=ffffff&fg=000000&s=0 "E[X]")
)của phân bố tôi gọi là XHCN. Dĩ nhiên, nếu phân bố không đều thì gọi nó là XHCN cũng không đúng ý nghĩa lắm nữa. Cho nên cái analogy XHCN/TBCN chỉ phiên phiến thôi.
Anh Hưng, tôi định dùng các kết quả trong “Bài toán lấy mẫu” này, anh Hưng có thể cho biết đây là kết quả của anh hay của người khác để tôi trích dẫn
Rất cảm ơn anh!
Anh có thể ghi là “it is well-known that …” vì thật sự đây đã là kiến thức chung rồi. Các kết quả này không phải của tôi, và tôi không biết ai là người đầu tiên nghĩ ra chúng. Nếu cần cite một quyển sách thì anh có thể cite
http://www.amazon.com/Randomized-Algorithms-Rajeev-Motwani/dp/0521474655
http://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402/ref=pd_bxgy_b_img_c
Anh Hưng, trong công thức cuối cùng
P( abs(Y-E[Y]) >= kơ’)<1/(k^2)
trong đó (ơ'^2)=n(ơ^2), nên ơ'=sqrt(n)ơ.
Vậy phải đặt k=(sqrt(n).mu.epsl)/ơ
đúng không ạ?
Mong mãi trả lời của anh Hưng mà chưa thấy.
Chào anh Hà, xin lỗi tôi trả lời muộn. Đúng là
.