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

[Munin]

Mihr в сообщении #1440150 писал(а):

Если разрешить "нетрадиционное" использование монетки :-)

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

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

Отмечаем на ребре монеты точку. Подбрасываем монету, и измеряем угол $\varphi,$ который точка составляет с направлением направо. Разделив всю окружность на $n$ равных частей, получаем равновероятное распределение за один бросок.

-- 19.02.2020 11:25:40 --

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

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

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

Вероятность этого очень мала.

Тем не менее, у Розенкранца с Гильденстерном получалось.
Стоппард. Розенкранц и Гильденстерн мертвы.
Советую почитать, получите удовольствие.

-- 19.02.2020 11:29:53 --

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

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

Кстати, тут есть ещё одна задача.

Допустим, вероятность выпадения орла $p,$ а решки $1-p.$ У нас в запасе $k$ бросков, и $n$ альтернатив, $n<2^k.$ Можно даже считать $n$ степенью двойки. Как назначить результаты бросков альтернативам, чтобы распределение вероятностей было как можно более равномерным?

[ET]

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

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

Лет 20 назад в другом месте доказывал:
Если число бросков конечно и ограничено $N$ то все вероятности, таким образом полученные , обязаны быть кратными $2^{-N}$ А $\frac13$ этому не кратно

[Утундрий]

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

[arseniiv]

Munin в сообщении #1440377 писал(а):

Допустим, вероятность выпадения орла $p,$ а решки $1-p.$ У нас в запасе $k$ бросков, и $n$ альтернатив, $n<2^k.$ Можно даже считать $n$ степенью двойки. Как назначить результаты бросков альтернативам, чтобы распределение вероятностей было как можно более равномерным?

О. Это уже смахивает на дебри оптимизации. Можно предложить один простой жадный алгоритм, но не уверен, что оптимальный: будем раскладывать эти слагаемые $p^m(1-p)^{k-m}$ (кстати зря вы ограничили $n < 2^k$, а вот неположительным ему лучше не быть) по $n$ кучкам так, чтобы каждый раз минимизировать максимум модулей разностей между кучками, и будем выбирать слагаемые по убыванию — начнём с $\max(p^k, (1-p)^k)$ и закончим $\min(p^k, (1-p)^k)$. По крайней мере для $p = \frac12$ это решение даёт лучший возможный ответ, но если $p$ далеко от $\frac12$, я вообще не представляю, что может получиться (надо бы помоделировать…).

-- Ср фев 19, 2020 17:22:35 --

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

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

Можно ещё минимизировать их сумму, например.

[Munin]

Вы же правильно произнесли: энтропия. Её и надо максимизировать.

[arseniiv]

Хм, интересно. Не пришло в голову может быть потому что до самого конца у нас сумма вероятностей меньше единицы.

[arseniiv]

Итак, он всё же неоптимальный даже с энтропией. А именно, для $(k, n, p) = (4, 2, 0{,}7)$ (как-то вы по-моему неудобно назвали $k, n$, я бы сделал наоборот) выдаётся распределение $(0{,}4977, 0{,}5023)$ вместо найденного перебором $(0{,}4998, 0{,}5002)$. Вот так всё-таки жадность до добра не доводит.

[arseniiv]

Мне в другом месте намекают, что задача может оказаться NP-трудной, ибо для весьма похожей это так:

Цитата:

If you have an arbitrary partition of 1 into positive rational numbers, and you try to split them as closely into two [equal] parts as possible, that *is* NP-hard.

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

[venco]

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

Мне в другом месте намекают, что задача может оказаться NP-трудной, ибо для весьма похожей это так:

Это для произвольных чисел, а у нас они имеют формулу.

[arseniiv]

(Да, конечно. Но не сразу (по крайней мере, не всем) очевидно, насколько это скажется. Мне просто до этого не было видно, что мы можем быть тут настолько близко к NP-трудности, я раньше оценивал бы подальше.)

[mihaild]

Для произвольных чисел это же ровно рюкзак. У нас числа не произвольные, и число разных видов чисел гораздо меньше чем всего чисел.
И жадный алгоритм (если отсортировать по убыванию), если $2^k \gg n$, выдает почти равномерное распределение. А если $2^k \approx n$, то вроде решается за полином стандартной динамикой.
Хотя тут может быть логично просить не сгенерировать всё разбиение по кучкам сразу, а спрашивать, куда положить каждую последовательность...

[Munin]

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

Мне в другом месте намекают, что задача может оказаться NP-трудной

Я примерно так же подумал. И тоже из-за сходства с рюкзаком.