GT 7: Con gà của ông Markov

7. Con gà của ông Markov

7.1. Việt Nam có bao nhiêu trọc phú?

Tí và Tèo ăn hết một con gà. Ông Markov bảo rằng không thể nào cả Tí lẫn Tèo đều ăn hơn nửa con gà được. Nếu 10 người ăn hết một con gà, thì không thể có hơn 4 anh ăn tham mỗi anh ăn hết hơn 1/5 con gà. Đơn giản thế, chỉ là nguyên lý chuồng bồ câu (có người gọi là nguyên lý Dirichlet), mà cũng cần đến ông Markov à? Ừ, đúng là chỉ có thế, nhưng “đơn giản” thì không hẳn. Lý thuyết Ramsey cũng “đơn giản” chỉ là nguyên lý chuồng bồ câu, mà đến Paul Erdös phải than rằng:

Giả sử người ngoài hành tinh chiếm địa cầu, yêu sách rằng trong vòng một năm chúng ta phải xác định được số Ramsey cho 5 màu đỏ và 5 màu xanh. Tập hợp hết những người thông minh nhất thế giới và các máy tính mạnh nhất hành tinh, may ra chúng ta có thể tính giá trị này được. Còn nếu quân địch đòi 6 đỏ và 6 xanh thì chúng ta không còn cách nào khác là đưa đầu cho chúng nướng.

Thu nhập bình quân đầu người của VN năm 2009 là 1200usd một năm. Theo phó thủ tướng thì sẽ lên 20 nghìn một năm vào 2050, mừng quá. Chúng ta có 85 triệu dân. Nếu không còn thông tin nào khác về phân bố thu nhập, nhiều nhất là bao nhiêu người có thu nhập hơn 20 nghìn năm 2009? Cũng là mấy con bồ câu thôi — thật sự giống bữa tối của Tí và Tèo — nhưng không trả lời trong một tích tắc được nữa. Cần hai tích tắc.

Trước hết, ta có thể tự giải lấy, đếch thèm ông Markov. Thu nhập bình quân 1200usd thì tổng thu nhập là 85 triệu nhân 1200 bằng 102 tỉ. Vì thế không thể có nhiều hơn ${\frac{102 \cdot 10^9}{20 \cdot 10^3} = 5.1}$ triệu trọc phú.

Còn nếu dùng con gà của ông Markov thì làm thế nào? Ông ấy bảo, nếu ${X}$ là biến ngẫu nhiên bất kỳ trên miền giá trị không âm thì ${\text{Prob}[X > a] < \frac{E[X]}{a}}$ . (Bạn có toàn quyền tự do tư tưởng, quy định bởi hiến pháp, để đánh đồng ${E[X]}$ và ${a}$ với nửa con gà, để so sánh với ví dụ đầu tiên trong bài.) Cái hay của con gà Markov là nó đúng bất kể phân bố của ${X}$ là như thế nào. Nhưng ông ấy nói về xác suất, còn các câu hỏi kiểu tổng số trọc phú ở trên lại mang tính tổ hợp. Không sao. Trong miền hữu hạn thì xác suất và tổ hợp là anh em cột chèo!

Thế này nhé. Túm đầu ngẫu nhiên một anh Mít (với xác xuất một phần 85 triệu). Gọi ${X}$ là thu nhập của hắn. Đề bài cho biết ${E[X]}$ là 1200usd. Xác xuất mà ${X}$ lớn hơn 20 nghìn sẽ bé hơn ${\frac{1200}{20000} = 0.06}$ , theo ông Markov. Nhưng do ta chọn phân bố đều (1 phần 85 triệu), xác suất ${X}$ lớn hơn 20 nghìn bằng tổng số trọc phú chia cho 85 triệu. Vì thế, tổng số trọc phú sẽ ít hơn ${0.06 \cdot 85 \cdot 10^6 = 5.1}$ triệu.

Cho tập ${S}$ các số không âm với tổng bằng ${T}$ , thì tỉ lệ các thành viên của ${S}$ có giá trị lớn hơn ${\alpha \frac{T}{|S|}}$ sẽ ít hơn ${1/\alpha}$ , và tỉ lệ các thành viên của ${S}$ có giá trị nhỏ hơn ${\alpha \frac{T}{|S|}}$ phải nhiều hơn ${1 - 1/\alpha}$ . Phát biểu này dùng khá nhiều trong các chứng minhtổ hơp mà chúng ta sẽ gặp. Nó chẳng qua là cái cẳng gà của Markov.

Hai năm trước báo TT đăng tin:

TT – Vừa qua, trong một đợt thị sát đời sống xã hội ở tỉnh Trà Vinh, một vị lãnh đạo có gặp gỡ người dân và ông cũng nói lên niềm vui khi thấy con số thu nhập bình quân trên đầu người của tỉnh đạt 800 USD/năm.

Nói xong, vị lãnh đạo muốn nghe ý kiến của người dân. Một nông dân nói: “Một người ăn nguyên một con gà, một người chỉ đứng nhìn, tính bình quân mỗi người ăn được… nửa con gà.”

Vì thế, con gà của ông Markov cho chúng ta rất ít thông tin, tại vì chúng ta cho nó rất ít thông tin. Chỉ cho nó mỗi trị kỳ vọng thì nó chỉ cho biết đến thế. Trị kỳ vọng là “first moment”. Nếu có thêm “second moment” thì ta ăn con gà to hơn, con gà Chebyshev. Khi đó chúng ta sẽ giải quyết phần nào bức xúc của bác nông dân, và sẽ ước định được số trọc phú ở VN chính xác hơn.

Một chi tiết lịch sử thú vị là con gà của Markov lý ra phải là gà Chebyshev, và gà Chebyshev lý ra phải là gà Bienaymé.

7.2. Túm đầu trọc phú trên Internet

Các công ty cung ứng dịch vụ mạng thường phải lưu trữ nhiều thống kê về lưu thông trên mạng. Thống kê cơ bản là có bao nhiêu gói dữ liệu từ một nguồn IP nào đó đi qua một router. Cách thô thiển là router giữ ${n = 2^{32}}$ biến đếm và tăng một biến lên khi nhận được một gói dữ liệu mới. Lưu trữ hơn 4 tỉ biến thì chẳng hay ho gì, tốn quá nhiều bộ nhớ. Câu hỏi là làm sao thiết kế một cấu trúc dữ liệu dùng ít bộ nhớ hơn (poly ${(\log n)}$ là tốt) mà vẫn ước lượng được số gói dữ liệu từ một IP bất kỳ. Dĩ nhiên, khi ta dùng ít bộ nhớ hơn thì ta phải chấp nhận ước lượng của mình có sai số nhỏ (với xác suất cao). Một câu hỏi liên quan là làm sao chỉ ra các địa chỉ IPs là nguồn của một lượng lớn các gói dữ liệu đi qua router này. Bài toán này gọi là bài toán tính Heavy-Hitter, nôm na là bài “túm đầu trọc phú”.

Cormode và Muthukrishnan thiết kế một cấu trúc dữ liệu gọi là Count-Min Sketch như sau. Gọi ${d}$ và ${w}$ là các số nguyên dương sẽ định nghĩa sau. Chọn độc lập ${d}$ hàm số ngẫu nhiên ${h_i: [n] \rightarrow [w]}$ , ${i \in [d]}$ từ một họ các hàm độc lập từng đôi (pairwise-independent). (Ta biết cách xây dựng họ hàm băm độc lập từng đôi dùng ít bộ nhớ và tính toán nhanh được.) Cấu trúc dữ liệu của ta là một bảng ${A}$ gồm ${dw}$ biến đếm. Bảng có ${d}$ hàng và ${w}$ cột. Mỗi hàng tương ứng với một hàm ${h_i}$ . Ban đầu thì tất cả các biến trong bảng đặt bằng ${0}$ .

Khi một gói dữ liệu với địa chỉ IP ${j \in [n]}$ đi qua, ta tăng ${A[i, h_i(j)]}$ lên, với mọi ${i}$ . Nôm na là bảng ${A}$ có ${d}$ hàng, mỗi hàng có ${w}$ cái rọ. Ở mỗi hàng ${i}$ , ném ${j}$ vào rọ của nó và tăng biến đếm trong rọ lên. Tại một thời điểm bất kỳ, gọi ${a_j}$ là số lần xuất hiện thực sự của IP ${j}$ . Ta cần ước lượng ${a_j}$ từ bảng ${A}$ . Ước tính của ta, ký hiệu là ${\hat a_j}$ , sẽ là

$\displaystyle \hat a_j := \min_i A[i, h_i(j)].$

Ước lượng này có sai số cỡ nào? Xét hàng ${i}$ và rọ của ${j}$ : biến đếm trong rọ này — so với ${a_j}$ — sẽ bị “vấy bẩn” bởi tổng tần suất các IP khác ${j}$ mà cũng được ném vào cùng một rọ. Cụ thể hơn,

$\displaystyle A[i, h_i(j)] - a_j = \sum_{j' \neq j, h_i(j') = h_i(j)} a_{j'}.$