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]}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sCJ9oTF9nzoHHw_F0_9StvrGYnyGHnaRWB70x9ykY1Myeo1kZm9Xgum5YzLX3VRBsa4wB9OGjltbFPSAMoCVBJV6deSL_e1vNeVimBqLakdrQ7bvga7OHN-rhl2moon6uWiziSL-c9enpKKdAofbJB1QSqgQYcyTQf=s0-d "{\mu = E[X]}")
, phương sai ![{\sigma^2 = E[(X - \mu)^2]}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u3nN8jgYVO9ex7iGHhgWFttryqp1gPjx_-TxZ_qdTLMwtr4QRBbrmj7niXIDk0x4e9s1uWU5d6Mh-KXv-HNxWXbvy2M0Sn_R4ETkolNVulQrh9p-iMZSpbAW3hTAxzUv78As6vYeeuqzpGC3MH6zYfcd_Gn6ylqk4bEAkdx999gwW6_-0CcG83T4mSSmcQ=s0-d "{\sigma^2 = E[(X - \mu)^2]}")
thì với mọi 
,- Ta có thể chặn trên số trọc phú:
- Ta có thể chặn trên số vô sản:
- Ta có thể chặn trên tổng số vô sản và trọc phú: Nói cách khác, ta có thể chặn dưới đám trung lưu bằng:
![\displaystyle \text{Prob}[X - \mu \geq k \sigma] \leq \frac{1}{1+k^2}.](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_suySU9pzfFO1y2CWZwBkDCHezJSwVdJd7qXXETK5j-ii5aHTSGBTRJtAROJvXpkwqRbvpTOoB4Vr4mxHEh0iXz2Rfxrn6OkRJwo6SzQm9c-pDOHB5uZb4WZznKM1jKqOUhKNgbFnoSBbABesqXvviYay8s5gj9KKqj5f60wsZQo1E63DjKxgRiXrEV5scLEucmDvv9F3-xLsFt7E39W32eBOWxfN-yrCEkHqtRZG7EkKCzyIb53T3fYze4mDtLDtgdN9ApWaCEp8RXNTl_=s0-d "\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}.](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uIhNHuWL3GdiTx7ocwEvrSCTxzzG4PSpQjf6i3LDlr6uvT5Ijm-P-2jtsMNV1JkXFa37s_yZk_Hih2XUdZR4cbPReZ754YYpVrpQhXZVgCJb5wos_rtRtMdAU5G8o5GIRFhqmOZHTGEqxsllj-SMNfcMsG5NAbwIt1vHRBvClUtsQWUK9ScSVWr5XZRT52x3rp3r6LfSoh4Im3KF6VIJqTvZ967yfgRsB6TGVUeFC0kdr2hmS-PHaoD5GcihQ-lAvwV1aQ4m0Z-N4toa7tKR0=s0-d "\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}.](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_t4QEU0TJER4WY6UipO_eg85n2cdhJwOA295Hi2oBmlG4AGwYLad7ce4pweWJzYHHZwgtUCmMOymeUNX97_59LKgaGoi2G9xTDUVNwZ_taQiCqCKLj0d9QTIXLUrPdu8Zk0WLap9sg6mv8eWSPu_YzwxLLgLnwFvhSZ_D9f7o5kaE9exSnToe04IyR3YRJYJGkk5bw1uz7RgPb3Jin5yW-evQCFvOdcXirWo9AjjGEwIRv22_zTaeL0eiAfsYmpCtlZxaPciRsWqR6cKDbx1I8=s0-d "\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}.](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vu_GxxrFbst6LRrurkgwKN6GULEUL9_iO-c2l_lIvul4sR9oMwkanK9UZBDSSp1FYhhclVyf4V2cGLpV2B6_kxnx4JGOxYJDnmqFcPw--Dw68PUAjOm6Hjoddh1APX0pVmOTvcqXXUC9NIpFsn06zpS-nyLU4Zg6Q0WfLAFahX0T5JwjQIynAeEodJXNFkr7JAijVUSXYCmWcW9FSpxVjYqVmAKgA9o1YCrhVK5nUBk_SsSKkShp4ksMGq-0VJ1oTpnTK9bZ_nqjCwaE3eqBb_dx8=s0-d "\displaystyle \text{Prob}[|X - \mu| \leq k \sigma] \geq 1- \frac{1}{k^2}.")
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ướcNếu ta biết (hoặc chặn trên được) phương sai của, cần lấy ít nhất bao nhiêu mẫu để cho
Trong đó gọi là độ sai lệch, và
là độ tin cậy.
![{\text{Prob}[|\bar \mu-\mu| \leq \epsilon \mu] \geq 1- \delta}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vRmvEsEbmzcGBjaFXsun1Tzv41c8c9UTOpC21KedSwVqTlY36QHKdthrzkIKZ3H6swr_4oN6OY02iDJUKjPOwzNJND80cohR6DmP1oGnYWsOTlrYq_-5GkQF8L2qAddlB54-olzKolhAkt2sr84CO0BUjURKiMUh6cbHdOAxk5HSg9RymkVWiEzImdJ1Q3SJTHsUXyoqxdsppRRoC2LDw1t9hHPOGOdFUAodoyYFVoa6lGEYXgTZIqM7A4fYk1hj4KnV4=s0-d "{\text{Prob}[|\bar \mu-\mu| \leq \epsilon \mu] \geq 1- \delta}")
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}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vMPIRglGyLe8dTKoZhKQhtE9Kz3bUmciQwKXMFiCn29oF4LSzy2ha-c2iGG0etzHkX1HB4jEo2z7gDJZRn1KYeSviC4BnYqEfR8GtQgkuM4wmuN1-kEKqoi6WGNhIrJCOMAoyl9KmCh3s67NXLN1rnzNAfNVye9h3l7uk=s0-d "{E[X_i] = \mu}")
, ![{\text{Var}[X_i] = \sigma^2}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vgQPR9_guGErgD7OQaMtj0H61YIXNYZo-tZU_6MwOQQgcJccYdkNUMZ7iD6io5eyQhzLxtZkaGq1lvSA7fkDyDih6lhy8tEMLW0c7WX00eMMROWUn_adMn22PtBUXf7Oy_OB6RCpxEzb1C4J7fb6M4p77Icxk-61X_L1jdRdXgKOhx1VuPFxHYrotRlscoCDnGeQ=s0-d "{\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}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sK7b_bQLZYjeSdWBkB3gRS_Uj7rEs_I0Hou-4ZrLehp_H7VrX-VaYoyFO2FILttBLsdcl3HU-Y7HbO9Y1Uk8_lNXcgCbhIXQSvdVsvHtLTOGOV-g8XiBCk6rWQOsqFIgHAHtiqSamdhjS2WSgLJckaHtFelKPD1JTvAA=s0-d "{E[Y] = n\mu}")
và ![{\text{Var}[Y] = n\sigma^2}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tPdBZjINVcYfBnvQSbSkumMiSA6sChXAO5WhwmP_cfsWwsSc2yXRKgahYG0o-Ic0M1fDgZm4GNe_puzmWxEJjbbdRzrIQp-B1TJbyJ0RSrIPU9Fx4rrXlp1mGlDRFR6cwcCbKxDLPICYW9tcDsk0Gbc9Dwh648Y_gNx5pJQrh5zZf1O_BJ6CyJAjx3YnsZZpPr=s0-d "{\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}.](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uwgiV4vtmGpjQuSZcqonmUo0I-XOjm5nfVfljxKD0XBkHtOcH2Wa-1gI075jvtDObuLKjVb-kjng8N_Xkm0YvnJHAJppwJLFlg7K3vX3Nsf6-_zedHEmVH5gCNZ2haT9YAEdp-jjCKkErFqLzGJN1lgfy2xLgrTNTuAWsYJDICfSPhmziQwrkq27aW0CMG4R68771SREeQgETIW7WygRO8D1vseX6WevayXPBbHV3rVYgp8-5uO5bZbyqMGMCkAmayuO56TbH1kPxp3zv1am8qK05v-d2kKE21f7c3VK9CVD3COImF57IIC-7VCa7k-nXH62w9tnvrRluTq1HX0RipMfSAZVUgQXoBugacMn3-s5u68oyJkFm9Crbt5J5H6-7KFxbY0drYFs6im3AfPHZnte_f-SAGf4SuI_A=s0-d "\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}.")
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õ.
http://www.procul.org/blog/2010/07/09/gt-8-con-ga-c%E1%BB%A7a-ong-chebyshev/
No comments:
Post a Comment