Нечестная монетка

[mihaild]

sirvff в сообщении #1680072 писал(а):

пример приведите плз

Пусть у нас есть какой-то алгоритм $A$.
Рассмотрим его две модификации: $A_h$: кинуть монетку, если выпал орел, то запустить $A$, иначе кинуть монетку еще $100$ раз, после чего запустить $A$. $A_t$: кинуть монетку, если выпала решка, то запустить $A$, иначе кинуть монетку еще $100$ раз, после чего запустить $A$.
Если $o < 1/2$, то первый лучше, если $o > 1/2$, то второй лучше.

Понятно что тут есть алгоритм, лучший их обоих для любой монетки, но в общем случае существование универсального оптимального алгоритма совсем не очевидно.

[sirvff]

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

sirvff в сообщении #1680067 писал(а):

что это за "жадный алгоритм"? он точно работает в условиях п1, когда мы НЕ ЗНАЕМ реальное значение О ?

Нет, не работает, он для варианта с известным $o$.
Делает следующее. Пусть нам надо сгенерировать орла с вероятностью $p$ (изначально $1/2$). Бросаем монетку.
Если $o < p$ и выпал орел, то сразу говорим "орел". Если $o < p$ и выпала решка, то продолжаем бросать, теперь нужно сгенерировать орла с вероятностью $\frac{p - o}{1 - o}$.
Если $o > p$ и выпала решка, то сразу говорим "решка". Если $o > p$ и выпал орел, то продолжаем бросать, теперь нужно сгенерировать орла с вероятностью $\frac{p}{o}$.

ннуууу.... а для известного о он оптимален? тут видимо можно улучшить...

-- 27.03.2025, 14:12 --

Null в сообщении #1680083 писал(а):

Рассмотрим алгоритм: кидаем группами по $2k$ Если в очередной группе количество О и Р одинаково, то останавливаемся. Таких наборов $C^k_{2k}$ четное число - на половину выдаем Р, на вторую О. Назовем его $B_{2k}$
Матожидание $\frac{2k}{C^k_{2k}o^k(1-o)^k}$.
Сравните 10 бросков пропускаем потом $B_2$ и $B_4$. Разность матожиданий $=10+\frac{2}{2o(1-o)}-\frac{4}{6o^2(1-o)^2}$ меняет знак.

1. можно пытаться привести "универсально лучший", вдруг он есть разом для всех. вообще-то наверное можно почти все посл-сти кроме много одинаковых подряд попилить на 0-1, есть смысл привести алгосы, не содержашие очевидных улучшений хотя бы для начала.
2. можно брать интеграл по всему(равномерному) распределению
ну да. хорошее наблюдение. ещё бы связи с какими-то более известными задачами если найти, то можно и покопаться.

[Null]

А если такой жадный алгоритм:
$S_0$- пустое множество строк из "О" и "Р"
$S_{i+1}$ -дописываем к каждому слову из $S_i$ "О" и "Р"(количество слов удвоилось), потом берем пары слов с одинаковым количеством "О" и "Р" и относим их к разным вариантам выходных ответов и выкидываем их из $S_{i+1}$
Осталось не более $i+2$ слов(разные количества букв "Р") и их вероятность не больше $(\max(o;1-o))^{i+2}$ и матожидание алгоритма конечно.

[mihaild]

Null, это вроде тот же самый итеративный алгоритм.

[sirvff]

Null в сообщении #1680121 писал(а):

А если такой жадный алгоритм:
$S_0$- пустое множество строк из "О" и "Р"
$S_{i+1}$ -дописываем к каждому слову из $S_i$ "О" и "Р"(количество слов удвоилось), потом берем пары слов с одинаковым количеством "О" и "Р" и относим их к разным вариантам выходных ответов и выкидываем их из $S_{i+1}$
Осталось не более $i+2$ слов(разные количества букв "Р") и их вероятность не больше $(\max(o;1-o))^{i+2}$ и матожидание алгоритма конечно.

нуу, даа, ну вот чо-нить про оптимальность этой штуки. может быть можно сделать "среднюю длину дерева" ещё меньше как-то по одной дописывая итп, крч B_i d в ваших терминах побыстрее собирать
пока к сожалению не доходят руки норм подумать

[sirvff]

Можно по поводу пункта 2 ещё подоказывать что-то в духе "если Х - редкая, то и sqrt(X) редкая"
на сам деле любопытно, насколько сложен тут в реальности ответ и что он значит

[mihaild]

Пусть $N(x, y)$ - количество строк с $x$ орлами и $y$ решками, на которых алгоритм говорит "орел", $M(x, y)$ - на которых говорит решка.
Для простоты пока предположим, что $N(x + 1, y) \cdot N(x, y + 1) = 0$ и $M(x + 1, y) \cdot M(x, y + 1) = 0$ (пару строк $(x + 1, y)$ и $(x, y + 1)$ можно заменить на $(x, y)$ с сохранением вероятности и уменьшением ожидаемой длины - не факт, что это получится сделать в дереве, но пока проигнорируем).
Тогда вроде бы $\forall x, y: N(x, y) = M(x, y)$. Ожидаемая длина при этом получается $\sum\limits_{x, y} N(x, y) o^x \cdot (1 - o)^y$.
Алгоритм выше соответствует варианту $N(x, y) = 1$ для случая, когда последняя единица в двоичных записях $x$ и $y$ общая, а все остальные не совпадают.
Вопрос - можно ли найти какие-то простые ограничения на $N$, при которых существует соответствующее разбиение дерева?

[Евгений Машеров]

"Фабрика честного жребия"
Пусть имеется монета, выдающая "О" с вероятностью $p\ne \frac 1 2$ и "Р" с вероятностью $q=1-p$ (вероятности известны или оцениваются по выборке)
Тогда, сжав сгенерированное так слово "ОРООРОРРРООРОР..." или подобное алгоритмом арифметического сжатия, получим битовую последовательность. По мере роста сжимаемого текста степень сжатия приближается к теоретически максимальной, а сжатый текст - к последовательности равновероятных и независимых битов (а случайны они в силу случайности исходного текста).
Процент выхода готовой продукции зависит от того, насколько вероятности для исходной монеты отличны от одной второй.