Несколько путей и одна монетка

[Утундрий]

Как, имея всего одну честную монету, разыграть равновероятно аж $n$ альтернатив?

Попытки решения:

$n=1$ - один раз бросаем монетку и безотносительно к результату выбираем первый вариант.

$n=2$ - один раз бросаем монетку и в случае выпадения "орла" выбираем первый вариант.

$n=3$ - ...э-э-э...

[mihaild]

Пусть у нас есть генератор бесконечных двоичных последовательностей, генерирующий последовательность, начинающуюся на даннные $k$ символов с вероятностью $2^{-k}$. Как с его помощью выбрать из трех вариантов?
Понятно, как из монетки сделать такой генератор если есть бесконечное число бросков. Но может быть иногда после нескольких бросков уже станет всё понятно (например если сразу выпало $00$ - то мы уже точно в первой трети, дальше можно не бросать)?

Или вопрос как гарантированно обойтись не больше чем $k$ бросками? Это невозможно, т.к. всегда можно сказать что кидаем ровно $k$ раз, и какой вид в этом случае будет у вероятности какого-то события?

[arseniiv]

Кстати вот предыдущая инкарнация почти того же вопроса: «Равномерные распределения с помощью монеты разными способами»

[TOTAL]

Утундрий в сообщении #1440115 писал(а):

Как, имея всего одну честную монету, разыграть равновероятно аж $n$ альтернатив?

Бросаем несколько раз, договорившись о выигрышной последовательности для каждого.
(Несколько последовательностей считаем ничейными.)

[B@R5uk]

Утундрий в сообщении #1440115 писал(а):

$n=3$ - ...э-э-э...

Кидаем монетку 2 раза. С вероятностями 1/4 получаем следующее:
1) ОО — выдаём 0;
2) ОР — выдаём 1;
3) РО — выдаём 2;
4) РР — необходимо перекинуть монетку ещё два раза.

Подход выше будет работать, но как по мне, так вероятность неудачи из первой серии бросков (1/4) слишком велика. Можно попробовать сделать серию сразу длиной 4. Тогда:
1) ОООО...ОРОО — выдаём 0 (вероятность 5/16)
2) ОРОР...РООР — выдаём 1 (вероятность 5/16)
3) РОРО...РРРО — выдаём 2 (вероятность 5/16)
4) РРРР — нужно сделать ещё заход (вероятность 1/16)
Однако, этот способ неявно включён в предыдущий, поэтому предыдущий будет давать результат в среднем быстрее. Можно даже это проверить цифрами. Поскольку

$$\sum\limits_{k=1}^{\infty}{ka^k}=\frac{a}{\left(1-a\right)^2}$$

$$\sum\limits_{k=1}^{\infty }{k{{\left( 1-a \right)}^{k-1}}{{a}^{k}}}=\frac{1}{1-a}\sum\limits_{k=1}^{\infty }{k{{\left( a-{{a}^{2}} \right)}^{k}}}=\frac{a}{{{\left( 1-a+{{a}^{2}} \right)}^{2}}}$$

то в первом случае имеем среднюю длину

$$2\cdot \sum\limits_{k=1}^{\infty }{k{{\left( \frac{1}{4} \right)}^{k-1}}{{\left( \frac{3}{4} \right)}^{k}}}=\frac{2\cdot 3\cdot {{4}^{3}}}{{{\left( {{4}^{2}}-3\cdot 4+{{3}^{2}} \right)}^{2}}}=\frac{384}{169}\approx 2.2722$$

а во втором:

$$4\cdot \sum\limits_{k=1}^{\infty }{k{{\left( \frac{1}{16} \right)}^{k-1}}{{\left( \frac{15}{16} \right)}^{k}}}=\frac{4\cdot 15\cdot {{16}^{3}}}{{{\left( {{16}^{2}}-15\cdot 16+{{15}^{2}} \right)}^{2}}}=\frac{245760}{58081}\approx 4.2313$$

Гораздо интереснее для n=5. Самый простой подход сделать 3 броска и выдать двоичный код, если он меньше 5. Если же он больше или равен, то перекинуть монетки. Тогда вероятность неудачи в первой серии бросков будет равна 3/8, а среднее число бросаний:

$$3\cdot \sum\limits_{k=1}^{\infty }{k{{\left( \frac{3}{8} \right)}^{k-1}}{{\left( \frac{5}{8} \right)}^{k}}}=\frac{3\cdot 5\cdot {{8}^{3}}}{{{\left( {{8}^{2}}-5\cdot 8+{{5}^{2}} \right)}^{2}}}=\frac{7680}{2401}\approx 3.1987$$

А можно поступить хитрее. Делать четыре броска монеты (как для n=15) и выдавать двоичный код, делённый нацело на 3, если результат меньше 15. Тогда вероятность неудачи при первом заходе будет всего 1/16. Однако среднее количество бросков для такого подхода уже посчитано выше и будет больше, чем при простом походе.

-- 17.02.2020, 08:46 --

arseniiv в сообщении #900453 писал(а):

Матожидание числа бросков для такого способа $2^cc/n$.

Сдаётся мне, что у кого-то из нас неправильные формулы.

[svv]

B@R5uk в сообщении #1440138 писал(а):

Делать четыре броска монеты (как для n=15) и выдавать двоичный код, делённый нацело на 3, если результат меньше 15.

Да, это хороший способ. Делаем $2n$ бросков. Только последовательность всех единиц считаем ничейной. В противном случае возвращаем остаток от деления двоичного кода на $3$.

[B@R5uk]

Уже поправили.

Делаем $2l$ бросков для числа $n=2^l+1$. В качестве ответа выдаём двоичный код, делённый на цело на $2^l-1$, если код не равен $2^{2l}-1$.

Только это не будет рационально с точки зрения среднего числа бросков. Простой подход с $l+1$ броском даёт в среднем меньшее число бросаний.

[Утундрий]

То есть, подход видится только один: выбрасывание избыточного числа равновероятных исходов с переигрыванием в случае не розыгрыша. И все усилия направлены на минимизацию среднего числа бросков до завершения розыгрыша.

[Mihr]

(Оффтоп)

Отчего же, возможны и совершенно другие подходы. Если разрешить "нетрадиционное" использование монетки

[mihaild]

B@R5uk, перепроверьте вычисления. Для выбора при $n=5$ по сериям из трех бросков нам точно понадобится хотя бы одна серия, а с вероятностью $3/8$ - хотя бы еще одна. Т.е. бросков в среднем уж точно не меньше чем $3 \cdot (1 + \frac{3}{8}) = 4.125$.
Ну и собственно тут никакие ряды не нужны, если вероятность успешной серии $p$, а нам в среднем нужно $x$ серий до первой успешной, то $x = 1 + (1 - p) x$, откуда $x = \frac{1}{p}$ (мат. ожидание геометрического распределения).

[B@R5uk]

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

B@R5uk, перепроверьте вычисления.

Вычисления правильные, а вот ряд составил неверно. Надо было так:

$$\sum\limits_{k=1}^{\infty }{k{{\left( 1-a \right)}^{k-1}}a}=\frac{a}{1-a}\sum\limits_{k=1}^{\infty }{k{{\left( 1-a \right)}^{k}}}=\frac{a\left( 1-a \right)}{\left( 1-a \right){{a}^{2}}}=\frac{1}{a}$$

-- 17.02.2020, 13:22 --

Тогда для n = 3 и двух бросаний среднее число бросков будет равно

$$2\cdot\frac{4}{3}=\frac{8}{3}\approx 2.6667$$

а для четырёх бросаний (n = 3 и n = 5):

$$4\cdot\frac{16}{15}=\frac{64}{15}\approx 4.2667$$

Для n = 5 и трёх бросаний:

$$3\cdot\frac{8}{5}=\frac{24}{5}=4.8$$

Выходит, более длинная серия всё-таки иногда бывает выгоднее.

-- 17.02.2020, 14:11 --

Вообще, интересная оптимизационная задача получается. Для $n=2k+1$ минимальное число бросков в серии $l_{min}=\left\lceil\log_2n\right\rceil$ может оказаться неоптимальным. Надо брать различные $l\ge l_{min}$, для которых вероятность удачи в первой серии равна

$$p=1-\frac{2^l\bmod n}{2^l}$$

и смотреть чему равно среднее количество бросаний

$$L=\frac{l}{p}=\frac{l}{1-2^{-l}\left(2^l\bmod n\right)}$$

Но в любом случае, из-за наличия $2^{-l}$ в знаменателе оптимальное $l^*$ должно отличаться от $l_{min}$ не на много.

[B@R5uk]

Удобно ввести величину $\Delta=l^*-l_{min}$ и смотреть на то, как она меняется с ростом n.

Для величин от 3 до 2047 у меня получилась вот такая табличка (надеюсь, нигде не обсчитался):

Используется синтаксис Text

          n   l_min   Δ
          3     2     0
          5     3     1
          7     3     0
          9     4     1
    11...15     4     0
         17     5     1, 2
     19, 21     5     1
    23...31     5     0
     33, 35     6     2
    37...41     6     1
    43...63     6     0
    65...73     7     2
    75...85     7     1
   87...127     7     0
  129...145     8     2
  147...169     8     1
  171...185     8     0, 2, 3
  187...203     8     0, 2
  205...255     8     0
  257...291     9     2
  293...341     9     1
  343...371     9     3
  373...409     9     2
  411...511     9     0
  513...585    10     2
  587...681    10     1
  683...743    10     3
  745...819    10     2
 821...1023    10     0
1025...1169    11     2
1171...1365    11     1
1367...1489    11     3
1491...1637    11     2
1639...2047    11     0
 

Сразу бросаются в глаза закономерные и весьма неожиданные вещи. Закономерно, например, то, что $\Delta=0$ для чисел близких, но меньших $2^l$. Неожиданно на мой взгляд то, что возможно несколько оптимальных значений. Или то, как дельта меняется при росте от $2^l+1$: сначала 2, потом 1, затем 3, снова 2 и после этого 0. Я полагал, что будет что-нибудь типа 3, 2, 1, 0.

-- 17.02.2020, 15:33 --

Кстати, для чисел вида $n=2^l\cdot m$, где m — нечётно, оптимально будет сгенерировать случайное число от 0 до m–1, затем умножить его на $2^l$ и к результату прибавить случайный код, получаемый бросанием монетки l раз.

[arseniiv]

B@R5uk в сообщении #1440161 писал(а):

Выходит, более длинная серия всё-таки иногда бывает выгоднее.

А вы способ от Null (в той теме) смотрели? Мне сначала казалось, что он оптимальный с точки зрения матожидания числа бросков на одно полученное значение (в пределе бросания всей бесконечной серии).

Но если подсчитать всякие информационные величины, чтобы убедиться, что закрутить гайки нельзя, то получается как-то подозрительно. Сколько бросков монетки тратится на генерацию одного символа нового алфавита, в идеале должно быть энтропией такой случайной величины самой по себе. Матожидание находится как $n\sum\limits_{i=1}^{\infty} \alpha_i 2^{-i} i$, где $n = 0{,}\alpha_1\alpha_2\ldots_2$, и что-то оно как-то не похоже на $\log_2 n$ для не степеней 2 (ибо как минимум рационально). Хм.

[B@R5uk]

arseniiv, если честно, я совсем не понимаю, что в той теме происходило. Тут же я что-то насчитал, и даже могу объяснить что. Если я что-то не так посчитал, то можете же привести контрпример?

[mihaild]

arseniiv, вы считаете число бросков чтобы сгенерировать одно число, или среднее число на каждое следующее число при генерации бесконечного потока? Первое будет уж точно не меньше чем $\lceil \log_2 n\rceil$ и соответственно больше чем $\log_2 n$ если $n$ не степень двойки.
Для второго (считаем $n$ нечетным) кажется достаточно побить отрезок на $n$ частей, каждую их них еще на $n$ и т.д., считать что монетка задает точку на отрезке, и выдавать очередное число как только станет понятно, в какой мы части. Чтобы выдать $k$ чисел нам нужно знать в каком из $n^k$ отрезков мы. Если мы сделали $m$ бросков, то мера множества, в котором мы этого не знаем, максимум $(n^k - 1) \cdot 2^{-m}$, т.к. $m$ бросками мы единичный отрезок разбили на $2^m$ отрезков, и "плохие" из них только те, в которые попала хотя бы одна из $n^k - 1$ границ. Соответственно с вероятностью экспоненциально быстро стремящейся к $1$ при $x \to \infty$ мы сможем выдать $k$ чисел, бросив монетку $k\log_2 n + \sqrt{k} + x$ раз - т.е. в среднем нам почти наверное понадобится как раз $\log_2 n$ бросков на каждое число.