Bất đẳng thức Fano

Trong lý thuyết thông tin, **bất đẳng thức Fano** liên hệ lượng thông tin bị mất trên một kênh nhiễu với xác suất phân loại sai. Nó được tìm ra bởi Robert Fano đầu thập niên 1950 khi đang dạy một semina tiến sĩ về lý thuyết thông tin tại MIT, và sau đó được đưa vào cuốn sách năm 1961 của ông.

Nó được dùng để tìm ra một chặn dưới cho xác suất lỗi của bất kì bộ giải mã nào.

Đặt các biến ngẫu nhiên *X* và *Y* đại diện cho thông điệp vào và ra (trong số *r*+1 thông điệp có thể) với xác suất hợp P(x,y). Bất đẳng thức Fano là
:H(X|Y)\leq H(e)+P(e)\log(r),

trong đó
:H\left(X|Y\right)=-\sum_{i,j} P(x_i,y_j)\log P\left(x_i|y_j\right)

là entropy có điều kiện,
:P(e)=P(X\neq Y)

là xác suất lỗi, và
:H(e)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))

là entropy nhị phân tương ứng.

## Chứng minh

Đặt biến chỉ số ngẫu nhiên E, để chỉ thị ước lượng \tilde{X}=f(Y) có lỗi,

: E :=
\begin{cases}
1 ~&\text{ nếu }~ \tilde{X} \neq X~, \\
0 ~&\text{ nếu }~ \tilde{X} = X~.
\end{cases}


Coi H(E,X|\tilde{X}). Có thể dùng luật chuỗi entropy để mở rộng theo 2 cách khác nhau

:
\begin{align}
H(E,X\mid\tilde{X}) &= H(X\mid\tilde{X}) + \underbrace{H(E\mid X,\tilde{X})}_{=0} \\
&= H(E\mid\tilde{X}) + H(X\mid E,\tilde{X})
\end{align}


Cân bằng
:
H(X\mid\tilde{X}) = H(E\mid\tilde{X}) + H(X\mid E,\tilde{X})


Khai triển số hạng thứ hai, H(X\mid E,\tilde{X})
:
\begin{align}
H(X\mid E,\tilde{X}) &= \underbrace{H(X\mid E=0,\tilde{X})}_{=0}\cdot P(E=0) + H(X\mid E=1,\tilde{X})\cdot\underbrace{P(E=1)}_{=P(e)} \\
                 &= H(X\mid E=1,\tilde{X})\cdot P(e)
\end{align}

Vì E=0 nghĩa là X=\tilde{X}; với giá trị \tilde{X} cho phép chắc chắn biết được giá trị X. Do đó H(X\mid E=0,\tilde{X}) = 0.
Mặt khác, E=1 nghĩa là \tilde{X}\neq X, với giá trị \tilde{X}, ta có thể thu hẹp X về một trong các giá trị khác nhau khoảng |\mathcal{X}|-1, cho phép đặt giới hạn trên cho entropy có điều kiện H(X\mid E=1,\tilde{X}) \leq \log(|\mathcal{X}|-1). Tiếp theo

: H(X\mid E,\tilde{X}) \leq \log(|\mathcal{X}|-1)\cdot P(e). 

Số hạng còn lại H(E\mid\tilde{X}) \leq H(E) vì điều kiện làm giảm entropy. Theo cách định nghĩa E, H(E) = H_b(e), nghĩa là H(E\mid\tilde{X}) \leq H_b(e). Tổng hợp kết quả lại

: H(X\mid\tilde{X}) \leq H_b(e) + P(e)\log(|\mathcal{X}|-1) 

Vì  X \rightarrow Y \rightarrow \tilde{X}  là Xích Markov, ta có I(X;\tilde{X}) \leq I(X;Y) theo bất đẳng thức xử lý dữ liệu, nên  H(X\mid\tilde{X}) \geq H(X\mid Y) , đưa ra

: H(X\mid Y) \leq H_b(e) + P(e)\log(|\mathcal{X}|-1) 

## Tham khảo

* P. Assouad, "Deux remarques sur l'estimation," *Comptes Rendus de L'Academie des Sciences de Paris*, Vol. 296, pp.&nbsp;1021–1024, 1983.
* L. Birge, "Estimating a density under order restrictions: nonasymptotic minimax risk," Technical report, UER de Sciences Economiques, Universite Paris X, Nanterre, France, 1983.
* L. Devroye, *A Course in Density Estimation*. Progress in probability and statistics, Vol 14. Boston, Birkhauser, 1987. ISBN 0-8176-3365-0, ISBN 3-7643-3365-0.
* R. Fano, *Transmission of information; a statistical theory of communications.* Cambridge, Mass., M.I.T. Press, 1961. ISBN 0-262-06001-9
* R. Fano, *[http://www.scholarpedia.org/article/Fano_inequality Fano inequality]* Scholarpedia, 2008.
* I. A. Ibragimov, R. Z. Has′minskii, *Statistical estimation, asymptotic theory*. Applications of Mathematics, vol. 16, Springer-Verlag, New York, 1981. ISBN 0-3879-0523-5