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

[sirvff]

Здравствуйте. у нас есть монетка с(неизвестной) вероятностью выпадения орла О.
Мы хотели бы её поподкидывать и в результате провести эксперимент, выдающий два исхода с вероятностями 1/2, т.е моделировать честную.

Решение: бросаем два раза, если РО - это трактуем как 0, если ОР - как 1, иначе повторяем эксперимент.
Число подбрасываний, которое может потребоваться, правда, не ограничено, хоть матожидание и конечное.

А дальше любопытно.
1. Укажите схему такого эксперимента с минимальным матожиданием числа бросков

2. Предположим, что нам известна вероятность О. Тогда, могут быть более оптимальные "в среднем" схемы. О, для которых есть схема с меньшим мо, назовём "странными".
О, для которых существует схема эксперимента с ГАРАНТИРОВАННО ОГРАНИЧЕННЫМ количеством бросков, назовём "редкими"
Пример:
О = 1/sqrt(2) - это редкая и странная монета, потому что 2 бросков гарантированно хватит: если оба раза выпал орёл, то 1, иначе 0.

Вопросы:
1) докажите, что монеты с O = 1/pi, O = 1/3 не редкие. Странные ли они?

2) Опишите целиком классы странных и классы редких монет. Какие рациональные числа странные, редкие?

3) Назовём монету A-странной(-редкой), (А - число от 0 до 1), если в исходном определении заменить 1/2 на А. Опишите классы A-странных(-редких) монет

[mihaild]

Скорее всего, это предполагалось либо в ПРР, либо в Олимпиадные?

[sirvff]

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

Скорее всего, это предполагалось либо в ПРР, либо в Олимпиадные?

без понятия, о чём вы. задачу я просто придумал.

[Yadryara]

Ну тогда ПРПР.

[sirvff]

Yadryara в сообщении #1679808 писал(а):

Ну тогда ПРПР.

Я не знаю что вы обсуждаете. Но не задачу.

Я знаю решения некоторых пунктов, интересных - нет.

[drzewo]

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

задачу я просто придумал.

Знаете, я думаю, что если Вы выложите решение ,то это увеличит вероятность того, что обсуждение начнется

[Утундрий]

(Оффтоп)

Тема периодически читается мной то как "несчастная монетка", то как "нечётная монетка". К чему бы это?

[sirvff]

drzewo в сообщении #1679828 писал(а):

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

задачу я просто придумал.

Знаете, я думаю, что если Вы выложите решение ,то это увеличит вероятность того, что обсуждение начнется

Я выше написал, что решения интересных подпунктов не знаю. Иначе бы и не выкладывал сюда ничего. То, что я знаю, по сути тривиально и ценности это писать нет (ну, формальное условие на редкость монеты например полиномиальное по О из которого ясно что 1/3 и тем более 1/pi - не редкие)

Что-то я пока на форуме вижу озабоченность исключительно вопросами, в какой раздел что поместить. А ведь когда-то быль июль, а ведь когда-то лето было :)

[sirvff]

Вот смотрите. Не так сложно написать уравнение в общем виде которому должна удовлетворять редкая монета.
Точнее, на листочке просто. Здесь мне тяжело слишком писать формулы, прошу простить.

у нас есть n бросков, 2^n исходов, и из них надо выбрать подмножество такое, чтобы сумма весов была 1/2.

если ограничиться только рациональными числами, т.е дробями P/Q, то несложно установить, что Q - чётное, ну и ещё некоторые моменты.
Тем не менее, я по итогу сейчас даже не знаю список рациональных редких монет.

Что касается первого пункта и линии с "необычными", она представляет самостоятельный интерес.

Очевидное улучшение схемы из 1 поста - это последовательности ООРР и РРОО тоже трактовать как 1 и 0 соответственно, оставляя для "перебрасываний" только ОООО и РРРР. и так дальше можно схлопывать по 4, 8, ... символов. Это видимо тоже не оптимум.

[mihaild]

Да, не оптимум.
Ваш итеративный алгоритм не останавливается за $k$ шагов с вероятностью $\prod\limits_{i > 0:k \& 2^i \neq 0} (o^{2^i} + (1 - o)^{2^i})$. Соответственно ему требуется $\sum\limits_k \prod\limits_{i > 0: k \& 2^i \neq 0} (o^{2^i} + (1 - o)^{2^i}) = 2\prod\limits_{i > 0} (o^{2^i} + (1 - o)^{2^i} + 1)$ бросков в среднем.

Жадный алгоритм (если нам сейчас нужно смоделировать вероятность орла $p$, если $p > o$ и выпал орел, то сразу говорим "орел", если $p \leq o$ и выпала решка, то сразу говорим "решка") дает рекурренту $f(p) = \begin{cases} 1 + (1 - o) \cdot f\left(\frac{p - o}{1 - o}\right), p > 0 \\ 1 + o \cdot f\left(\frac po\right)\end{cases}$, которую непонятно как решать, но численная оценка говорит что он лучше.
Численный эксперимент дает такие значения.

Вложение:

download (2).png

[sirvff]

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

Да, не оптимум.

спасибо, но давайте сверим часы

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

[Null]

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

1. Укажите схему такого эксперимента с минимальным матожиданием числа бросков

Как сравнить 2 алгоритма если при разных $o$ лучше то один, то второй?

[sirvff]

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

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

1. Укажите схему такого эксперимента с минимальным матожиданием числа бросков

Как сравнить 2 алгоритма если при разных $o$ лучше то один, то второй?

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

[Null]

Рассмотрим алгоритм: кидаем группами по $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}$ меняет знак.

[mihaild]

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

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

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