последовательность равновероятных битов

[zykov]

Дана неограниченная последовательность битов распределенных случайно и независимо друг от друга.
1 выпадает с вероятностью $p$ и 0 выпадает с вероятностью $1-p$. Само $p$ неизвестно и оно не меняется.
Надо сгенерировать другую последовательность нулей и единиц, в которой они распределены случайно и независимо строго с вероятностью 50 на 50.

[alisa-lebovski]

Старый прикол с монетками.

[mihaild]

alisa-lebovski в сообщении #1535652 писал(а):

Старый прикол с монетками

Прикол с монетами это если $p$ известно. Тут нам, видимо, нужно найти функцию $f: \{0, 1\}^\mathbb N \to \{0, 1\}^\mathbb N$ со следующим свойством. Назовем слово $x$ плохим $\exists n \forall N \exists y: x[:N] = y[:N] \wedge f(x)[n] \neq f(y)[n]$. Тогда для любого $p$ мера множества всех плохих последовательностей должна быть равна нулю.
Это эквивалентно нахождению двух множеств конечных слов $A$ и $B$, таких что ни одно из слов из $A \cup B$ не является префиксом другого, и при этом для любого $p$ вероятность получить последовательность с префиксом из $A$ равна $\frac{1}{2}$ и с префиксом из $B$ тоже $\frac{1}{2}$.

Не уверен, что ТС имел в виду именно это; zykov, можете подтвердить или опровергнуть? Впрочем такая задача выглядит небезынтересной в любом случае.
UPD: написано почти верно, но меня совершенно не в ту степь понесло.

[alisa-lebovski]

mihaild в сообщении #1535657 писал(а):

Прикол с монетами это если $p$ известно.

Нет, не известно. Классическая задача, как бросаниями неправильной монеты смоделировать правильную.

[zykov]

mihaild
Боюсь, что не полностью понимаю. Но мне кажется Вы усложняете. Там довольно просто можно сделать (но можно и посложнее сделать).

mihaild в сообщении #1535657 писал(а):

найти функцию $f: \{0, 1\}^\mathbb N \to \{0, 1\}^\mathbb N$

Тут Вы имеете ввиду что из последовательности длины $N$ сделать другую последовательность длины $N$?
Это просто невозможно (возьмите например очень маленький $p$).
Новая последовательность будет короче (поэтому упоминается "неограниченная последовательность"). Это кстати уже большая подсказка.

[mihaild]

(Оффтоп)

alisa-lebovski в сообщении #1535658 писал(а):

Классическая задача, как бросаниями неправильной монеты смоделировать правильную.

Да, это я что-то совсем не в ту сторону думать начал, о какой-то смеси этой задачи и получения неправильной монеты по правильной.

-- 20.10.2021, 23:27 --

zykov в сообщении #1535659 писал(а):

Тут Вы имеете ввиду что из последовательности длины $N$ сделать другую последовательность длины $N$?

Нет, это значит что функция из бесконечных последовательностей делает бесконечные последовательности. Ну и что она рано или поздно определится с любым элементом, а не потребует смотреть бесконечно далеко.
Но в любом случае я действительно зря тот пост написал, задача понятная и классическая.

[ozheredov]

alisa-lebovski в сообщении #1535658 писал(а):

Нет, не известно. Классическая задача, как бросаниями неправильной монеты смоделировать правильную.

Расскажите, please!

[kotenok gav]

ozheredov в сообщении #1535664 писал(а):

Расскажите, please!

Бросаем монету бесконечное число раз по два раза. Каждый раз, когда выпадает сначала орёл, а затем решка, записываем 1, когда сначала решка, а затем орёл - 0. Иначе ничего не делаем.

[ozheredov]

kotenok gav
В смысле, это сгенерирует "равновероятную" и "независимую в совокупности" последовательность битов безотносительно к вероятности выпадения орла?

[alisa-lebovski]

ozheredov в сообщении #1535761 писал(а):

В смысле, это сгенерирует

А какие сомнения?

[zykov]

kotenok gav в сообщении #1535685 писал(а):

Каждый раз, когда выпадает сначала орёл, а затем решка, записываем 1, когда сначала решка, а затем орёл - 0.

Да, верно.
Это самое простое, что можно сделать.
Незавсисмо от $p$ двойки "01" и "10" выпадают с одинаковой вероятностью $p(1-p)$ каждая. Если для одной выдать "0", для другой "1", то в этой выходной последовательности они будут равновероятны. При этом двойки "11" и "00" просто выбрасываются - для них никакой выход не генерируется.
Важно: двойки должны быть (1,2), (3,4), (5,6), ..., а не (1,2), (2,3), (3,4),...

Интересно посмотреть какой КПД такого алгоритма - сколько в среднем новых битов он выдаёт на один входной бит.
Здесь, очевидно, это $\gamma = 2p(1-p)$.
В лучшем случае это $\frac12$, если $p=\frac12$. При других $p$ оно будет меньше, плавно падая до нуля по параболе при $p=0,1$.

Закономерный вопрос, а можно ли сделать КПД получше?
Если вместо двоек брать более длинные подпоследовательности, то КПД в основном будет улучшатся (иногда не меняется, как при пререходе от 2 к 3).
Там тоже надо поотдельности рассмотреть случаи, когда в последовательности какое-то фиксированное количество единиц (например при длине 4 будут случаи - 1 единица/4 варианта, 2 единицы/6 вариантов, 3 единицы/4 варианта). Все эти варианты будут равновероятны внутри одного случая. Количество вариантов - это количество сочетаний $C_n^k$.
Значит для произвольной половины вариантов можно выдать "1", для другой половины "0" (если количество вариантов было нечётное, то какой-то один из них просто выбросить).
Наиболее оптимальными будут длины, когда все биномиальные коэффициенты чётные (кроме единиц на концах). Это например верно для длин равных степеням двойки $n=2^m$.
В таком случае КПД будет $\gamma = 1 - p^n - (1-p)^n$.
Тут КПД будет приближатся к единице. И не только при $p$ около $\frac12$, но и для $p$ очень маленьких или очень близких к 1.
Просто надо взять достаточно длинную подпоследовательность, чтобы вероятность что все нули или все единицы была близка к нулю.

[ozheredov]

alisa-lebovski
Да-да, точно )
zykov
Спасибо за подробное объяснение

[venco]

zykov в сообщении #1535782 писал(а):

В таком случае КПД будет $\gamma = 1 - p^n - (1-p)^n$.
Тут КПД будет приближатся к единице.

А вы не забыли учесть, что использовали больше бит исходой последовательности?

[zykov]

venco в сообщении #1535849 писал(а):

А вы не забыли учесть, что использовали больше бит исходой последовательности?

Точно, забыл.
Тут $\gamma$ - это только вероятность сгенерировать один бит из одной подпоследовательности.
КПД для двойки будет $p(1-p)$, максимум $\frac14$ при $p=\frac12$.
Для более длинной подпоследовательности будет $\gamma = \frac{1-p^n-(1-p)^n}{n}$.
Т.е. КПД будет только ухудшаться.

[venco]

zykov в сообщении #1535850 писал(а):

КПД для двойки будет $p(1-p)$, максимум $\frac14$ при $p=\frac12$.

На самом деле можно повысить КПД до почти $2p(1-p)$ для $p\approx\frac12$.