Пятница, 2 декабря, ауд. 106. Начало в 18:00.
Докладчик: Илья Разенштейн (МГУ).
Тема: Общая информация случайной пары строк.
Abstract
В докладе будет изучаться общая информация пары строк, которые сгенерированы по некоторому распределению. Рассмотрим такой модельный пример. Генерируются две случайные двоичные строки
![$ (x, y) $](../../../sites/default/files/tex/0337d1de5f3254239284dcd1225a7463f09e51de/index.png)
длины
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
, расстояние Хемминга между которыми равно
![$ \varepsilon n $](../../../sites/default/files/tex/ea56112bc2090d178c97f0d8d7ba253bcf524946/index.png)
. Мы хотим закодировать
![$ (x, y) $](../../../sites/default/files/tex/0337d1de5f3254239284dcd1225a7463f09e51de/index.png)
в тройку строк
![$ (a, b, c) $](../../../sites/default/files/tex/8c96e466e79ffd2e9b0957187c849092356e9233/index.png)
так, чтобы
![$ x $](../../../sites/default/files/tex/33fe5a238412ce3cd054309829bfa5d804965124/index.png)
восстанавливался по
![$ (a, c) $](../../../sites/default/files/tex/41658c9d44e463db5e734fc280c5b2e3033c0d91/index.png)
, а
![$ y $](../../../sites/default/files/tex/e1f809fc799b505bfa534d8f43189893642f58b0/index.png)
- по
![$ (b, c) $](../../../sites/default/files/tex/6a9efe032f1c860dd944dc5dd6961be9a13dd4e0/index.png)
. Очевидно, что должно выполняться неравенство
![$ |a| + |c| \geq n $](../../../sites/default/files/tex/d9c35eb31fd8199bc96e9b21f28d4846e6cbd05f/index.png)
, чтобы
![$ x $](../../../sites/default/files/tex/33fe5a238412ce3cd054309829bfa5d804965124/index.png)
в принципе можно было восстановить по
![$ (a, c) $](../../../sites/default/files/tex/41658c9d44e463db5e734fc280c5b2e3033c0d91/index.png)
. Мы усилим это неравенство до
![$ |a| + (1 - \varepsilon) |c| \geq n $](../../../sites/default/files/tex/0d04ba3bf4010fb3797f3055620d4ce4a94a0645/index.png)
. Это утверждение легко следует из количественной версии теоремы Гача-Кернера, которую мы докажем. В доказательстве используется оценка на норму оператора шума, который действует на произведении вероятностных пространств.