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

[zykov]

Да, можно КПД улучшить.
Если там больше трёх вариантов, то можно вместо одного бита сразу несколько сгенерировать.
Например при длине 4 можно для 1, 2 и 3 единиц для каждого из этих вариантов по 2 бита вместо одного делать.
Для 2 единиц можно либо два бита, либо один делать, т.к. там 6 вариантов - 4 варианта дают 2 бита, другие 2 варианта дают 1 бит.

При таком подходе длина 4 даёт пиковый КПД $\frac{13}{32}$ вместо $\frac{8}{32}$ для длины 2.
При длине 8 вышло что пиковый КПД $\frac{565}{1024} > \frac12$, т.е. он больше $2p(1-p)$.

[venco]

Да, именно так. Я сначала думал про другой способ - сохранять отбрасываемые биты в новую последовательность и получать биты и оттуда, и далее рекурсия. Так для $p\approx\frac12$ в пределе получается $2p(1-p)$, но для малых $p$ базовая вероятность вторичной последовательности порядка $p^2$ и эффективность резко падает. В общем оказалось, что лучше обрабатывать весь блок целиком.
Вот графики сохранения энтропии в зависимости от $p$ для разных длин блоков - 2 (нижний), 4, 8, 16, 32, 64, 128, 256 (верхний):

[zykov]

В пределе очень длинной подпоследовательности КПД будет приближатся к $\gamma = -p\log_2(p)-(1-p)\log_2(1-p)$.
К 1 он приближается только при $p=\frac12$. Для других $p$ предельное значение менее 1.

[venco]

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

$\gamma = -p\log_2(p)-(1-p)\log_2(1-p)$

Графики выше как раз к этому нормированы.

[dimkadimon]

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

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

 У меня была задача на эту тему: https://puzzling.stackexchange.com/ques ... biased-one