Xin viết kỹ hơn về phương pháp giải mã của Bob cho bài toán đang xét. Về căn bản, Alice muốn gửi cho Bob con số
p = c/2^n
. Với chiến lược đã nêu, tỉ lệ q của số bit 1 trên tổng số bit nhận được sẽ gần với p nhưng không có gì đảm bảo nó sẽ bằng p. Hơn nữa, làm thế nào ta biết được là q sẽ gần với p?
Trước hết, ta xét vấn đề giải mã. Con số p Alice cần gửi là một bội số của
1/2^n
. Có tất cả
2^n
vị trí từ 0 đến 1 mà p có thể nằm. Các vị trí này cách đều nhau một khoảng bằng
1/2^n
, từ 0 đến
(2^n-1)/(2^n)
. Phương pháp giải mã của Bob rất đơn giản: tính tỉ lệ q như đã nêu, sau đó làm tròn nó về bội số gần nhất của
1/2^n
. Như vậy, miễn là
|p-q| \leq \epsilon \approx 1/2^{n+1}
thì Bob sẽ giải mã đúng.
Cho trước một sai số
\theta
(ví dụ 0.001%), nếu
\mbox{Prob}[|p-q|\leq \epsilon] \geq 1-\theta
thì Bob sẽ giải mã sai với xác suất nhiều nhất là
\theta
. Để ước lượng xác suất này, ta dùng chặn Chernoff. Trong bài giảng ở đây, tôi có ghi lại chặn Chernoff ở một dạng tương đối mạnh. Với bài toán của chúng ta thì ta chỉ cần một dạng đơn giản của chặn này.
Giả sử ta có các biến ngẫu nhiên
X_1, \dots, X_t
trong đó
\mbox{Prob}[X_i = 1] = p
và
\mbox{Prob}[X_i = 0] = 1-p
, với
p
là một xác suất cho trước. Dễ thấy rằng
\[\mbox{E}\left[ \sum_{i=1}^t X_i \right] = tp.\]
Các chặn Chernoff cho ta ước lượng xác suất mà
\sum_{i=1}^tX_i
nằm xa expected value
tp
. Phân bố của tổng này có hai cái “đuôi” mỏng ở hai đầu, còn lại tập trung vào gần expected value (giống như hình ngọn núi), gọi là hiện tượng concentration.
Cho trước
\delta \in (0,1)
, Chernoff’s bound cho đuôi trên (upper tail) có thể viết như sau:
\mbox{Prob}\left[\sum_{i=1}^tX_i \geq (1+\delta)tp\right] \leq e^{-tp\delta^2/3}
và cho lower tail ta có
\mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}
Nói theo ngôn ngữ bình thường: khi
t
tiến ra vô cùng, khả năng mà
\sum_{i=1}^tX_i
nằm xa trung tâm tiến đến 0 theo hàm mũ (exponentially reduced).
Trở lại bài toán của chúng ta. Đặt
X_i
bằng giá trị của bit thứ
i
mà Bob nhận được. Như vậy, sau khi Alice gửi
t
bits, ta có
q = \frac{\sum_{i=1}^tX_i}{t}
. Dùng chặn Chernoff, đặt
\delta = \epsilon/p
(bỏ qua trường hợp tầm thường khi
p=0
), ta có
\mbox{Prob}\left[|q-p| \leq \epsilon\right] \geq 1 - 2e^{-t\epsilon^2/(3p)}
Như vậy, chỉ cần
t \geq 12p \ln(2/\theta) 2^{2n}
là Bob có sai số mong muốn.