Odwrotność do nierówności Fano?

10

Nierówność Fano można wyrazić w wielu formach, a jedna szczególnie przydatna wynika (z niewielką modyfikacją) Oded Regev :

Niech $X$ będzie zmienną losową, a $Y = g(X)$ gdzie $g(\cdot)$ jest procesem losowym. Załóżmy, że istnieje procedura $f$ która dla $y = g(x)$ może zrekonstruować $x$ z prawdopodobieństwem $p$ . Następnie
$I (X; Y) \geq p H (X) - H (p)$ $I(X; Y) \ge pH(X) − H(p)$

Innymi słowy, jeśli uda mi się zrekonstruować, w systemie jest wiele wzajemnych informacji.

Czy istnieje „rozmowa” z nierównością Fano: coś z formy

„Biorąc pod uwagę kanał z wystarczającą ilością wzajemnych informacji, istnieje procedura rekonstrukcji danych wyjściowych z błędem, który zależy od wzajemnej informacji”

Byłoby zbyt wiele, aby oczekiwać, że ta procedura byłaby również skuteczna, ale byłoby również interesujące zobaczyć (naturalne) przykłady, w których rekonstrukcja istnieje, ale musi być nieefektywna.

it.information-theory randomized-algorithms

— Suresh Venkat
źródło

12

$P(y)$ $y$ $x$ $\Pr[X = x \mid Y = y]$ $\max_x \Pr[x \mid Y = y]$ $2^{-H_\infty(X | Y = y)}$ $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)$ pod względem wzajemnej informacji . $I(X:Y)$

Napisz . Używając wspomnianej wyżej nierówności, lub . $I(X:Y) = H(X) - H(X|Y) = H(X) - \mathbb{E}_y[H(X \mid Y = 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)$

Prawdopodobieństwo, że procedura się powiedzie, gdy i są wybierane losowo, to , co według wklęsłości wynosi co najmniej . Zatem prawdopodobieństwo powodzenia procedury wynosi co najmniej . $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)}$

Ta procedura jest optymalna: biorąc pod uwagę dowolną procedurę losowości , prawdopodobieństwo powodzenia wynosi , który jest zmaksymalizowany punktowo, gdy deterministycznie wyprowadza najbardziej prawdopodobne . $P$ $\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$ $P(y)$ $x$

— Henry Yuen
źródło

1

Czy istnieje więc stwierdzenie ilościowe, które jest odwrotnością nierówności Fano wynikającej z tego argumentu?

— mobius dumpling

Co rozumiesz przez ilościowy? Argument, który podałem powyżej, powinien brzmieć: „Biorąc pod uwagę kanał z wzajemną informacją , istnieje procedura rekonstrukcji z błędem co najwyżej ”.

I (X : Y)

$I(X:Y)$

1 - 2^{I (X : Y) - H (X)}

$1 - 2^{I(X:Y) - H(X)}$

— Henry Yuen,

2

Dobra odpowiedź i dowód. Tak więc granicę w odpowiedzi można również przepisać ponieważ z definicji. Zgodnie z moją najlepszą wiedzą pojawiło się to w IEEE ISIT 1994, w przemówieniu Baumera.

p_{e r r} \leq 1 - 2^{I (X; Y) - H (X)} = 1 - 2^{- H (X | Y)}, (1)

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

$I(X;Y)=H(X)-H(X|Y)$

W podobny sposób można uzyskać gdzie jest entropia Renyi rzęduTutaj więc granica (2) jest ciaśniejsza niż (1).

p_{e r r} \leq 1 - \sum_{y \in Y} P_{Y} (y) 2^{- H_{2} (X | Y)}, (2)

$p_{err} \leq 1 - \sum_{y \in {\cal Y}} P_Y(y) 2^{-H_2(X|Y)},\quad\quad(2)$

H_{α} (Z) = \frac{1}{1 - α} (\sum_{z \in Z} P_{Z} (z)^{α})

$H_{\alpha}(Z)=\frac{1}{1-\alpha}\left( \sum_{z \in {\cal Z}} P_Z(z)^{\alpha}\right)$

α \in (0, 1) \cup (1, \infty) .

$\alpha \in (0,1)\cup(1,\infty).$

α = 2,

$\alpha=2,$

— kodlu
źródło