Bất đẳng thức Fano

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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.

Bất đẳng thức Fano[sửa | sửa mã nguồn]

Đặt các biến ngẫu nhiên XY đạ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)

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))

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

Tham khảo[sửa | sửa mã nguồn]

  • 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