Зворотне ставлення до нерівності Фано?

Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:

Хай $ X $ - випадкова величина і нехай $ Y = g (X) $, де $ g (\ cdot) $ - випадковий процес. Припустимо, що існування процедури $ f $, що дана $ y = g (x) $, може реконструювати $ x $ з ймовірністю $ p $. Потім   $ $ I (X; Y) \ ge рН (X) - H (p) $ $

Іншими словами, якщо я можу реконструювати, у системі є багато взаємної інформації.

Чи є "протилежність" нерівності Фано: щось у формі

"Враховуючи канал з достатньою взаємною інформацією, є процедура реконструкції введення з виводу з помилкою, яка залежить від взаємної інформації"

Було б надто багато очікувати, що ця процедура також буде ефективною, але також цікаво було б побачити (природні) приклади, коли реконструкція існує, але вона повинна бути неефективною.

10

2 Відповіді

Розглянемо таку процедуру реконструкції $ 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) $ в термінах взаємної інформації $ I (X: 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) $.

Імовірність того, що процедура вдасться, де $ 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)} $.

Ця процедура є оптимальною: з урахуванням будь-якої процедури довільності $ P $ імовірність успіху є $ \ mathbb {E} _y [\ sum_ (x) \ Pr (X = x \ mid Y = y) \ Pr (P (y) = x)] $, що максимально точним, коли $ P (y) $ детерміновано виводить найбільш імовірні $ x $.

11
додано
Що ви маєте на увазі кількісно? Аргумент, який я дав вище, повинен сказати: «За умови каналу з взаємною інформацією $ I (X: Y) $ існує процедура реконструкції з помилкою не більше $ 1 - 2 ^ (I (X: Y) - H (X)} $. "
додано Автор UberAlex, джерело
Отже, чи існує кількісне твердження, яке є протилежністю нерівності Фано, що випливає з цього аргументу?
додано Автор mobius dumpling, джерело

Красива відповідь і доказ. Отже, відповідь у вашому записі також може бути переписана $ $ 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) $ за визначенням. Це, наскільки мені відомо, з'явилося в IEEE ISIT 1994, в бесіді Баумера.

Подібним же чином можна отримати $ $ p_ {err} \ leq 1 - \ sum_ (y \ in (\ cal Y)} P_Y (y) 2 ^ (- H_2 (X | Y)}, \ quad \ quad (2) $ $ де $$ H_ (\ alpha) (Z) = \ frac (1) {1- \ alpha} \ left (\ sum_ (z \ in (\ cal Z)} P_Z (z) ^ (\ alpha) $ $ - ентропія Рені порядку $ \ alpha \ in (0,1) \ cup (1, \ infty). $ Тут $ \ alpha = 2, $, тому обмеження (2) є жорсткішим за (1).

1
додано