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

Предположим, что вы получили честную монету и хотели бы смоделировать распределение вероятностей многократного подбрасывания честного (шестигранного) кубика. Моя первоначальная идея состоит в том, что нам нужно выбрать подходящие целые числа , такие что . Таким образом, после подбрасывания монеты раз, мы отображаем число, закодированное цепочкой битов длины k, на выходы матрицы, разделив диапазон на 6 интервалов, каждый из которых имеет длину . Однако это невозможно, так как имеет два в качестве единственного простого множителя, а простые множители в включают три. Должен быть какой-то другой простой способ сделать это, верно?2 k = 6 m k [ 0 , 2 k - 1 ] m 2 k 6 $k,m$$2^k = 6m$$k$$[0,2^k-1]$$m$$2^k$$6m$

Чтобы иметь немного более эффективный метод, чем тот, на который указал @FrankW, но используя ту же идею, вы можете перевернуть свою монету раз, чтобы получить число ниже . Затем интерпретируйте это как пакет из die flips, где - наибольшее число, так что (как уже говорилось, равенство здесь никогда не выполняется). Если вы получите число, большее или равное вы должны отклонить значение и повторить все шагов.2 n m m 6 m < 2 n 6 m$n$$2^n$$m$$m$$6^m < 2^n$$6^m$$n$

Вы можете реализовать функцию, которая возвращает один бросок кристалла, сделав бросков монет, а затем кэшируя результат для следующих запросов броска кристалла.м - $n$$m-1$

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

n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348

получено по формулам: .

Первая строка соответствует ответу @FrankW с процентом брака 25%. Следующие числа хороши: и могут храниться в одной целочисленной статической переменной. В частности, процент брака составляет всего 5%, что является ощутимым улучшением по сравнению с 25% и делает его хорошим кандидатом для возможной реализации.n = 13 n = $n=8$$n=13$$n=13$

Что вы можете сделать, это использовать метод, называемый отбраковкой выборки :

• Переверните монету 3 раза и интерпретируйте каждый бросок как бит (0 или 1).
• Объединить 3 бита, задав двоичное число в .$[0,7]$
• Если число в , возьмите его как бросок кубика.$[1,6]$
• В противном случае, т.е. если результат равен или , повторите сальто.$0$$7$

Поскольку из возможных результатов приводит к завершению в каждом наборе, вероятность того, что для получения броска кубика потребуется более наборов бросков, составляет . Следовательно, этот метод эффективен на практике. л(1-$\frac 68$$l$$(1-\frac 68)^l = \dfrac 1{4^l}$

Улучшения:

Ответ @ Ангела указывает на то, что количество монет в каждом сете, но первый может быть уменьшено с 3 до 2, используя различие между и в качестве первого бита для следующего сета.$0$$7$

@Emanuele Paolini объясняет, как вы можете уменьшить количество повторных бросков, если вам нужно несколько бросков кубика.

Альтернативой выборке отбраковки (как описано в ответе FrankW ) является использование алгоритма масштабирования, который учитывает ответ из [7,8], как если бы это был другой бросок монеты.

На mathforum.org есть очень подробное объяснение , включая алгоритм ( NextBit()он будет подбрасывать вашу честную монету).

Случай для бросания кости с честной монетой (выборка 2 → 6) проще, чем общий алгоритм. Вы просто берете неудачу (7 или 8) как еще один вход для монет и выполняете еще два броска.

Другой подход к моделированию броска dN с использованием dM (в случае конкретного вопроса, задаваемого d6 с использованием d2) состоит в разбиении интервала [0, 1) на N равных интервалов длины 1 / N, [0, 1 / N), [1 / N, 2 / N), ..., [(N-1) / N, N).

Используйте dM для генерирования дроби base-M, 0.bbbb ..., в [0, 1). Если это попадает в [(i-1) / N, i / N), возьмите i в качестве броска dN. Обратите внимание, что вам нужно только сгенерировать достаточное количество базовых M цифр дроби, чтобы определить, в каком интервале он находится.

Возможно более простое объяснение улучшенной выборки отклонения.

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

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

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

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

Знание того, будет ли текущий набор бросков успешным, является единственной вероятностью, которая имеет значение , поскольку интерпретация успешного набора бросков не зависит от вероятности. И это может быть известно до того, как все сальто завершены для этого набора.

Это может быть достигнуто, по меньшей мере, двумя способами или, точнее, в двух разных интерпретациях сальто. Там могут быть другие.

Группировка результатов в парах

Идея состоит в том, чтобы рассмотреть только три значения (1,2), (3,4) и (5,6), представленные любыми тремя конфигурациями с двумя переворотами, скажем, TT, TH, HT. Затем вы можете применить выборку отклонения с двойным переворотом, повторяя каждый раз, когда вы получаете конфигурацию сбоя HH.

Как только вы получите одну из трех успешных конфигураций, вы просто переворачиваете монету еще раз, чтобы решить, следует ли вам брать первое или второе значение соответствующей пары.

Раннее обнаружение отказа от переворота

Идея состоит в том, чтобы использовать немного другое чтение конфигурации с тремя переворотами. Если Head и Tail интерпретируются как 1 и 0, то конфигурация должна соответствовать двоичной интерпретации плюс один. То есть TTT (то есть 000) соответствует 1, HTH (то есть 101) соответствует 6, HHT (то есть 110) и HHH (то есть 111) соответствует 7 и 8, или что-либо вне [1,6].

Затем мы знаем, что сальто успешно или неудачно только с первыми двумя сальто. Если они производят HH, сальто не срабатывает независимо от последнего сальто. Так что это можно пропустить.

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

Например, для игры в кости с 10 гранями вам нужен в принципе набор из 4 флипов, с 6 конфигурациями, соответствующими неудаче. Хитрость заключается в том, чтобы иметь все конфигурации ошибок на верхнем конце последовательности двоичных значений следующим образом:

TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

Успешные конфигурации соответствуют диапазону [1, 10] и сбои в диапазоне [11,16].

Затем вы терпите неудачу, когда первые два броска дают HH, или когда первые три броска дают HTH, без необходимости даже пытаться пропустить броски набора.

Если вы не терпите неудачу, вы просто прекращаете набор сальто.

Есть два известных подхода к этому. Одним из них является "выборка отклонения". Например, используйте три бита, чтобы выбрать одно из шести значений, повторив попытку для двух дополнительных выборок. Или используйте 14 бит (8192 значения), чтобы выбрать 5 значений от 1 до 6 (7776 возможностей), повторив попытку в 13 из 256 случаев.

Другой использует декомпрессионную часть алгоритма сжатия / декомпрессии: при арифметическом кодировании последовательность случайных значений от 1 до 6 может быть сжата практически без избыточности. Произведите сжатую последовательность случайным образом и распакуйте ее. Это намного сложнее, но практически не потребует дополнительных случайных чисел.

Извините заранее, если объяснение лишнее. Я не был уверен в том, как много деталей нужно описать или насколько легко понять концепцию.

Скажем, у вас есть три монеты (справедливые монеты). Если вы постепенно назначаете значение каждой стороне каждой монеты, у вас будет шесть значений.

Вот так: на первой монете головы 1, а хвостов 2. На второй монете головы 3, хвостов 4. На третьей монете головы 5, хвостов 6.

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

Продолжайте делать это, пока один и только один номер не совпадет с вашим текущим набором. Это твой номер.

Так что, если у вас есть [головы, хвосты, головы] для текущего набора, это будет [1, 4, 5]. Теперь вы переворачиваете их снова, и ваш текущий набор равен [2, 4, 5]. Два матча. Не хорошо. Попробуйте снова. Вы получаете [2, 3, 6]. Только один матч. Ваш номер два.

Будет равный шанс, что появится любое заданное число, но оно не особенно экономически выгодно, учитывая, что есть только изменение 3/32, что любая данная пара наборов будет успешной (только одно совпадение). Таким образом, в среднем алгоритм должен был бы повторяться около десяти раз. Кроме того, нелегко обобщить куб с нечетным номером.

По крайней мере, может быть, это пища для размышлений. Очень интересный вопрос

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

Например, пусть головы равны 1, а хвосты равны 0. Если вы перевернули его три раза и получили головы, хвосты, головы, у вас будет двоичный код 101, который равен 5 в десятичной дроби. HHT = 110b = 6. TTT = 000b = 0 и HHH = 111b = 7, оба из которых находятся за пределами диапазона и будут отклонены, и вы должны были бы повторить для всех цифр.

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

$6$$2$

Но это можно сделать с помощью справедливой «тройной монеты» (если можно использовать такой термин). Смысл монеты с 3 исходами. И простая 2-монета, так что совместное пространство этих 2-х монет точно соответствует пространству событий кубика.

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

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