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 ${\displaystyle P(x,y)}$. Bất đẳng thức Fano là

${\displaystyle H(X|Y)\leq H(e)+P(e)\log(r),}$

trong đó

${\displaystyle 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,

${\displaystyle P(e)=P(X\neq Y)}$

là xác suất lỗi, và

${\displaystyle H(e)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))}$

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

Tham khảo

• P. Assouad, "Deux remarques sur l'estimation," Comptes Rendus de L'Academie des Sciences de Paris, Vol. 296, pp. 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, 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