Home

Пятница 2 декабря, 18-00, ауд. 106

Пятница, 2 декабря, ауд. 106. Начало в 18:00.

Докладчик: Илья Разенштейн (МГУ).

Тема: Общая информация случайной пары строк.

Abstract

В докладе будет изучаться общая информация пары строк, которые сгенерированы по некоторому распределению. Рассмотрим такой модельный пример. Генерируются две случайные двоичные строки $ (x, y) $ длины $ n $, расстояние Хемминга между которыми равно $ \varepsilon n $. Мы хотим закодировать $ (x, y) $ в тройку строк $ (a, b, c) $ так, чтобы $ x $ восстанавливался по $ (a, c) $, а $ y $ - по $ (b, c) $. Очевидно, что должно выполняться неравенство $ |a| + |c| \geq n $, чтобы $ x $ в принципе можно было восстановить по $ (a, c) $. Мы усилим это неравенство до $ |a| + (1 - \varepsilon) |c| \geq n $. Это утверждение легко следует из количественной версии теоремы Гача-Кернера, которую мы докажем. В доказательстве используется оценка на норму оператора шума, который действует на произведении вероятностных пространств.