Обратное к неравенству Фано?

Неравенство Фано может быть изложено во многих формах, и одна особенно полезная из-за (с незначительной модификацией) Одеда Регева :

Пусть $X$ - случайная величина, и пусть $Y = g(X)$ где $g(\cdot)$ - случайный процесс. Предположим, что существует процедура $f$ которой $y = g(x)$ может восстановить $x$ с вероятностью $p$ . Тогда

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

Другими словами, если я смогу восстановить, в системе много взаимной информации.

Есть ли «обратная связь» с неравенством Фано: что-то вроде

«При наличии канала с достаточной взаимной информацией существует процедура восстановления входных данных из выходных данных с ошибкой, которая зависит от взаимной информации».

Было бы слишком многим ожидать, что эта процедура также будет эффективной, но было бы также интересно увидеть (естественные) примеры, где реконструкция существует, но должна быть неэффективной.

$P(y)$$y$$x$max x Pr [ x ∣ Y = y ] 2 - H ∞ ( X | Y = y ) H ∞ ( X ∣ Y = y ) X Y = y H ∞ ( X ) ≤ H 1 ( X ) H 1 ( 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$I ( X : Y $H_\infty(X|Y = y)$ в терминах взаимной информации .$I(X:Y)$

Напишите . Используя упомянутое выше неравенство, или .I ( X : Y ) ≤ H ( X ) - E y [ H ∞ ( X ∣ Y = y ) $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)$

Вероятность того, что процедура завершится успешно, если и выбраны случайным образом, равна , которая вогнутостью не менее . Таким образом, вероятность того, что процедура пройдет успешно, составляет не менее .Y E y [ 2 - H ∞ ( X ∣ Y = y ) ] 2 - E y [ H ∞ ( X ∣ Y = y ) ] 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)}$

Эта процедура является оптимальной: для любой процедуры случайности вероятность успеха равна , который максимизируется по точкам, когда детерминистически выводит наиболее вероятный .Е у [ Σ х Pr ( Х = х | У = у ) Рг ( Р ( у ) = х ) ] Р ( у ) $P$$\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$$P(y)$$x$

Хороший ответ и доказательство. Таким образом, границу в вашем ответе также можно переписать как так как по определению. Насколько мне известно, это появилось в IEEE ISIT 1994, в докладе Баумера.I ( X ; Y ) = H ( X ) - H ( X | Y

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

Аналогичным образом можно получить , где является энтропия Реньи порядкаЗдесь поэтому оценка (2) теснее, чем (1).H α ( Z ) =

$$p_{err} \leq 1 - \sum_{y \in {\cal Y}} P_Y(y) 2^{-H_2(X|Y)},\quad\quad(2)$$ α∈(0,1)∪(1,∞). α=2 $$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,$