Kebalikan dari ketidaksamaan Fano?

Ketidaksamaan Fano dapat dinyatakan dalam banyak bentuk, dan satu yang sangat berguna adalah karena (dengan sedikit modifikasi) kepada Oded Regev :

Misalkan $X$ adalah variabel acak, dan misalkan $Y = g(X)$ mana $g(\cdot)$ adalah proses acak. Asumsikan adanya prosedur $f$ yang diberikan $y = g(x)$ dapat merekonstruksi $x$ dengan probabilitas $p$ . Maka

$$I(X; Y) \ge pH(X) − H(p)$$

Dengan kata lain, jika saya dapat merekonstruksi, ada banyak informasi timbal balik dalam sistem.

Apakah ada "kebalikan" dari ketidaksetaraan Fano: sesuatu dalam bentuk

"Diberikan saluran dengan informasi timbal balik yang cukup, ada prosedur untuk merekonstruksi input dari output dengan kesalahan yang tergantung pada informasi timbal balik"

Terlalu berlebihan untuk berharap bahwa prosedur ini juga akan efisien, tetapi juga akan menarik untuk melihat contoh (alami) di mana rekonstruksi ada tetapi harus tidak efisien.

Pertimbangkan prosedur rekonstruksi berikut : mengingat y , output x sedemikian sehingga Pr [ X = x ∣ Y = y ] dimaksimalkan. Probabilitas bahwa prosedur ini berhasil adalah maks x Pr [ x ∣ Y = y ] . Ini juga 2 - H ∞ ( X | Y = y ) , di mana H ∞ ( X ∣ $P(y)$$y$$x$$\Pr[X = x \mid Y = y]$$\max_x \Pr[x \mid Y = y]$$2^{-H_\infty(X | Y = y)}$ adalahmin-entropidari variabel acak X yang dikondisikan pada Y = y . Kita tahu bahwa H ∞ ( X ) ≤ H 1 ( X ) , di mana H 1 ( X ) adalah standar Shannon entropi dari variabel acak X . Sekarang kita hanya perlu batas atas H ∞ ( X | Y = y ) dalam hal informasi bersama I ( X : $H_\infty(X \mid Y = y)$$X$$Y = y$$H_\infty(X) \leq H_1(X)$$H_1(X)$$X$$H_\infty(X|Y = y)$ .$I(X:Y)$

Tulis . Menggunakan ketidaksetaraan yang disebutkan di atas, I ( X : Y ) ≤ H ( X ) - E y [ H ∞ ( X $I(X:Y) = H(X) - H(X|Y) = H(X) - \mathbb{E}_y[H(X \mid Y = y)]$ , atau E y [ H ∞ ( X ∣ Y = y ) ] ≤ H ( X ) - I ( X : Y ) .$I(X:Y) \leq H(X) - \mathbb{E}_y[H_\infty(X \mid Y = y)]$$\mathbb{E}_y[H_\infty(X \mid Y = y)] \leq H(X) - I(X:Y)$

Probabilitas bahwa prosedur berhasil di mana dan Y dipilih secara acak adalah E y [ 2 - H ∞ ( X ∣ Y = y ) ] , yang oleh concavity setidaknya 2 - E y [ H ∞ ( X ∣ Y = y ) ] . Dengan demikian probabilitas prosedur berhasil setidaknya 2 I ( X : Y ) - H ( X $X$$Y$$\mathbb{E}_y [2^{-H_\infty(X\mid Y = y)}]$$2^{-\mathbb{E}_y[H_\infty(X \mid Y = y)]}$$2^{I(X:Y) - H(X)}$.

Prosedur ini adalah optimal: diberikan prosedur keacakan , probabilitas keberhasilan adalah E y [ Σ x Pr ( X = x | Y = y ) Pr ( P ( y ) = x ) ] , yang dimaksimalkan titik-bijaksana ketika P ( Y ) secara pasti menghasilkan x yang paling mungkin .$P$$\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$$P(y)$$x$

Jawaban dan bukti yang bagus. Jadi, terikat dalam jawaban Anda juga dapat menjadi ditulis ulang karena I ( X ; Y ) = H ( X ) - H ( X | Y ) menurut definisi. Ini muncul dalam IEEE ISIT 1994, dalam sebuah pembicaraan oleh Baumer, sejauh yang saya ketahui.

$$p_{err} \leq 1-2^{I(X;Y)-H(X)}=1-2^{-H(X|Y)},\quad\quad(1)$$ $I(X;Y)=H(X)-H(X|Y)$

Dalam nada yang sama, seseorang bisa mendapatkan mana H α ( Z ) =

$$p_{err} \leq 1 - \sum_{y \in {\cal Y}} P_Y(y) 2^{-H_2(X|Y)},\quad\quad(2)$$ adalah entropi Renyi dari urutanα∈(0,1)∪(1,∞). Di sini,α=2,jadi terikat (2) lebih ketat dari (1). $$H_{\alpha}(Z)=\frac{1}{1-\alpha}\left( \sum_{z \in {\cal Z}} P_Z(z)^{\alpha}\right)$$ $\alpha \in (0,1)\cup(1,\infty).$$\alpha=2,$