Почему корректор фон Неймана работает только тогда, когда входные биты независимы друг от друга и имеют одинаковое смещение?
Базовый дибиазер фон Неймана работает следующим образом: вы генерируете два бита X, Y, а затем выводите бит (или не выводите бит) с помощью следующей логики:
X=0 Y=0 -> Нет вывода
X=0 Y=1 -> Вывести 0
X=1 Y=0 -> Вывести 1
X=1 Y=1 -> Нет вывода
Если X и Y не коррелированы и имеют одно и то же смещение (то есть вероятность того, что они равны 0, равна $р$ а вероятность 1 равна $(1-п)$), то сразу следует, что вероятность того, что описанная выше процедура выдаст 0, равна $р(1-р)$ а вероятность 1 равна $р(1-р)$, что тождественно (и есть вероятность $p^2 + (1-p)^2$ ничего не выводить - мы просто запустим его снова с еще двумя входными битами). Кроме того, поскольку мы предполагаем, что входные биты независимы, многократный запуск модуля устранения смещения на независимых входных битах будет генерировать независимые выходные данные.
Однако вы задаетесь вопросом: «Что, если биты не являются независимыми или не имеют одинакового смещения»).
В этом случае приведенная выше логика не работает.
Если биты содержат разные смещения, то есть если первый бит равен 0 с вероятностью $р$, а второй бит равен 0 с вероятностью $q \ne p$), то вероятность 0 равна $p(1-q) = p - pq$ а вероятность 1 равна $q(1-p) = q - pq$, так как мы предполагали, что $p\ne q$, они явно разные, и поэтому вывод дибиазера смещен.
Если биты имеют одно и то же среднее смещение, но коррелированы, может случиться так, что биты последовательности от модуля устранения смещения могут быть коррелированы. Например, если 01 за последовательностью следует другая 01 последовательность 90% времени (и аналогично для 10 последовательность), то соседние выходные данные дебиазера сами будут сильно коррелированы, то есть дебиазеру не удалось превратить необработанную входную строку во что-то «случайное».
Предыдущий ответ (который только что привел контрпримеры):
Рассмотрим случай, когда четные входные биты равны 0 в 90% случаев, а нечетные входные биты равны 1 в 90% случаев.
В этом случае выход корректора фон Неймана смещен еще сильнее, чем вход.
Упражнение для вас: придумайте аналогичный контрпример, в котором биты не независимы друг от друга...
Пол жаловался, что мой пример был «слишком экстремальным» (что бы это ни значило — я думал, что подойдет любой контрпример). В любом случае отвечу другим, еще более экстремальным примером.
Рассмотрим необработанный источник, который сгенерировал пары битов с таким распределением вероятностей:
- 00 с вероятностью 1/3
- 01 с вероятностью 1/3
- 11 с вероятностью 1/3
(при этом каждая пара не коррелирует ни с какой другой парой).
Простое вычисление показывает, что каждая пара имеет энтропию Шеннона $log_2(3) \приблизительно 1,5850$ биты (или около $0.7925$ бит энтропии на бит).
Однако, если мы пропустим это через корректор фон Неймана, мы получим поток, который имеет, ну, 0 немного энтропии...
