Tiếp tục với câu hỏi cực kỳ thú vị lần trước.
Giả sử Bob biết n, và giả sử chuỗi nhị phân C có các bits
c_1 c_2 \dots c_n
. Gọi c là số nguyên có biểu diễn nhị phân là C. Ví dụ, nếu C = 10110 thì c = 22. Chiến lược của Alice như sau: mỗi lần gửi, gửi bit 1 với xác suất
p = \frac{c}{2^n}
, và gửi bit 0 với xác suất 1-p. Với chiến lược này, Alice không cần phải nhớ xem mình đã gửi bit gì. Sau khi đã gửi thật nhiều bits, Bob tính tỉ lệ q của số bits 1 trên tổng số bits mà Bob đã nhận. Tỉ lệ này sẽ tiến đến p khi tổng số bits nhận được tiến đến vô cùng. Ta có thể dùng Chernoff bound để tính cụ thể xác suất mà p và q nằm trong vòng
\epsilon
của nhau là bao nhiêu. Hơn thế nữa, ta có thể ép xác suất
\mbox{Prob}[|p-q| \leq \epsilon]
lớn tùy ý.
Thật ra thì ta không cần
\epsilon
nhỏ lắm, chỉ cần khoảng
1/2^{n+1}
là đủ. Tóm lại, khi tổng số bits Alice gửi tiến đến vô cùng, thì xác suất Bob giải mã được chuỗi C tiến đến 1. Đó là lời giải cho trường hợp Bob biết trước n.
3 Comments
Hình như có typo P(|p-q| > \epsilon).
Thanks. Tôi đã sửa lại thành “lớn” tùy ý, đúng là ý tôi muốn nói p và q gần nhau với xác suất cao.
Thử LaTeX trong phần lời bình. Sau đây là bất đẳng thức Markov:
\[ \mbox{Prob}\left[ X \geq a \right] \leq \frac{E[X]}{a} \]