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

[INGELRII]

Физический способ: смастерить центрально-симметричную пирамиду с $n$ гранями, пронумеровать грани, монету аккуратно ставить центром на вершину. Куда она уползет, то число и выпало.

[Утундрий]

Ну хорошо. А если попытаться достичь почти равномерного распределения, ограничившись конечным числом бросков?

[B@R5uk]

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

...достичь почти равномерного распределения...

Зачем делать хорошо, когда можно сделать идеально?

[Утундрий]

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

Зачем делать хорошо, когда можно сделать идеально?

Для того чтобы удовлетворить условию задачи.

[mihaild]

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

Для того чтобы удовлетворить условию задачи.

А какое полностью условие?
Описанные выше способы дадут ответ за конечное число бросков с вероятностью $1$, этого недостаточно?

[Утундрий]

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

Описанные выше способы дадут ответ за конечное число бросков с вероятностью $1$

Это для меня новость. Можно подробнее?

[arseniiv]

Вероятность того, что вам придётся бросать и бросать и не получать ответ, равна нулю.

-- Вт фев 18, 2020 00:52:18 --

mihaild
Спасибо! Правда я пока половину не осмыслил, голова под вечер сегодня не работает, но потом постараюсь ответить, что я имел в виду.

-- Вт фев 18, 2020 00:55:03 --

Точнее, я уже понял способ с делением отрезка, но сопоставить его с исходным способом отметания альтернатив в дереве я пока не… а, кажется уже немного ясно, почему дерево такое невыгодное — те альтернативы, которые мы отметём, выдав ответ сразу же, больше не помогают нам ниже по течению, если не реализовались, а с отрезком мы помним больше. Хмм…

[Утундрий]

Но количество возможных бросков при этом, разумеется, не ограниченно.

Я тут представил такую картину. Подходит, значит, к посылальному каменю ансамбль витязей и начинают эту вашу стратегию реализовывать. Проходит три дня и три ночи, все уже давно разбрелись по своим альтернативам и только сильномогучие богатыри Розенкранц с Гильденстерном упорно продолжают подбрасывать.

[mihaild]

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

Проходит три дня и три ночи, все уже давно разбрелись по своим альтернативам и только сильномогучие богатыри Розенкранц с Гильденстерном упорно продолжают подбрасывать

Вероятность этого очень мала. Скажем если всё население Земли выбирает из трех вариантов методом "бросить 2 раза, если два орла то перебросить", то больше 32 раз бросать придется скорее всего 1-2 людям.

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

Можно подробнее?

А что подробнее? Если бросать монетку, то рано или поздно (и скорее рано, чем поздно) решка выпадет, но нельзя дать гарантий, что она выпадет в первые $10^{100}$ бросков. Точно так же и тут - можно гарантировать, что вариант мы рано или поздно выберем, но нельзя гарантировать, что мы уложимся в $10^{100}$ бросков. Хотя скорее всего уложимся.

Если хочется считать приблизительно но с гарантией на максимальное число бросков - то просто кинуть монетку $n$ раз, сгенерировав число от $0$ до $2^n - 1$, и взять по модулю $k$. При этом первые $2^n \pmod k$ вариантов окажутся на $2^{-n}$ вероятнее остальных.

[Утундрий]

mihaild
Эту задачу уже, можно сказать, решили. Оптимизация здесь не так интересна. Пусть число бросков фиксировано. Как близко можно подойти к равномерности?

[arseniiv]

Так отсюда

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

Если хочется считать приблизительно но с гарантией на максимальное число бросков - то просто кинуть монетку $n$ раз, сгенерировав число от $0$ до $2^n - 1$, и взять по модулю $k$. При этом первые $2^n \pmod k$ вариантов окажутся на $2^{-n}$ вероятнее остальных.

можно выяснить, насколько, ну а сами вероятности будут $\lfloor k/2^n\rfloor$ и $\lceil k/2^n\rceil$. Распределение выходит заданным, можно считать какие угодно меры различия его и равномерного, ту же энтропию сравнить с $\log k$ — а то, что лучше этого распределения не получить $n$ бросками, вроде более-менее очевидно — мы можем только перекладывать кирпичики размера $2^{-n}$, и ровнее их сложить, чем в кучки по $\lfloor 2^n/k\rfloor$ и $\lceil 2^n/k\rceil$, не получится.

-- Вт фев 18, 2020 02:29:52 --

По сути, в данном случае броски монеты можно спокойно заменить произвольным числом исходов $N$, все полы-потолки останутся теми же, и способ со взятием по модулю тоже, обычная проблема расположения $N$ объектов в $k$ ровных колонок, разве что без внимания к порядку.

[Утундрий]

Ну, ок, линия опуса ясна. Ежели крепка вера в великий корейский рэндом, то гоняем по кругу до просветления. А ежели ресурс пробований жёстко ограничен - раскладываем степень двойки по кучкам по-равномернее.

[arseniiv]

Кстати способ с кучками используется для быстрой генерации дискретных случайных величин (когда не жалко немного места на гистограмму, возможно аккуратно разложенную), притом несколько элементов кучки могут вызывать какую-то долгую процедуру, которая подправит вероятности, но из-за редкости попадания не будет портить время. Алгоритм зиккурата, использующийся для непрерывных распределений, вроде достаточно похожим образом устроен.

[B@R5uk]

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

для быстрой генерации дискретных случайных величин

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

[arseniiv]

(А, ну я отвлёкся от равномерного распределения, интересующего в этой теме, и говорил это уже о произвольных. А какой-нибудь ГПСЧ для равномерного всегда в конечном итоге нужен, даже если есть настоящий ГСЧ, ведь обычно он не так уж быстро набирает энтропию.)