Нарисуйте целые числа независимо и равномерно в случайном порядке от 1 до используя справедливое d6?

18

Я хотел бы нарисовать целые числа от 1 до некоторого определенного , бросая некоторое количество справедливых шестигранных кубика (d6). Хороший ответ объяснит, почему его метод производит однородные и независимые целые числа.NN

В качестве иллюстративного примера было бы полезно объяснить, как работает решение для случая .N = 150N=150

Кроме того, я хочу, чтобы процедура была максимально эффективной: бросьте наименьшее количество d6 в среднем для каждого сгенерированного числа.

Преобразование из старшего в десятичное допустимы.


Этот вопрос был вдохновлен этой мета-веткой .

Sycorax говорит восстановить Монику
источник

Ответы:

12

Множество различных идентифицируемых результатов в независимых бросках матрицы с гранями имеет элементов. Когда кубик справедлив, это означает, что каждый результат одного броска имеет вероятность а независимость означает, что каждый из этих результатов будет иметь вероятность то есть они имеют равномерное распределениеΩ ( d , n ) Ω(d,n)n nd = 6 d=6d ndn 1 / d 1/d( 1 / d ) n : (1/d)n:P d , n .Pd,n.

Предположим, что вы разработали некоторую процедуру которая либо определяет результатов кубика c ( = 150 ), то есть элемента Ω ( c , m ), либо сообщает об ошибке (что означает, что вам придется повторить это для того, чтобы получить результат). То есть,т tмmc(=150)Ω(c,m)

t : Ω ( d , n ) Ω ( c , m ) { Отказ } .

t:Ω(d,n)Ω(c,m){Failure}.

Пусть FF - вероятность t,t приводящая к провалу, и отметим, что FF - некоторое целое кратное d - n ,dn, скажем

F = Pr ( t ( ω ) = отказ ) = N Fд - н .

F=Pr(t(ω)=Failure)=NFdn.

(Для справки в будущем, обратите внимание, что ожидаемое количество раз должно быть вызвано, прежде чем не произойдет сбой, равно )t t1 / ( 1 - F ) .1/(1F).

Требование , чтобы эти результаты в быть однородными и не зависит условный от не сообщают средства отказа , что сохраняет вероятность того, в том смысле , что для каждого событияΩ ( с , м ) Ω(c,m)t t AΩ ( с , м ) ,ttAΩ(c,m),

P d , n ( t A )1 - F =Pc,м(А)

Pd,n(tA)1F=Pc,m(A)(1)

где

t ( A ) = { ω Ω t ( ω ) A }

t(A)={ωΩt(ω)A}

набор бросков кубика, который процедура назначает событиют tа .A.

Рассмотрим атомное событие , которое должно иметь вероятностьПусть (броски костей, связанные с ) имеют элементов. становитсяA = { η } Ω ( c , m ) A={η}Ω(c,m)c - m . cm.t ( A )t(A) η ηN ηNη ( 1 )(1)

N η d - n1 - N F d - n = P d , n ( t A )1 - F =Pc,m(A)=c-m.

Nηdn1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.(2)

Непосредственно все равны некоторому целому числуN пNη N . N.т. с Осталось только найти наиболее эффективные процедуры Ожидаемое число не-отказов в рулон односторонней штамповой ISt.c

1м (1-F).

1m(1F).

Есть два непосредственных и очевидных значения. Одна из них заключается в том, что если мы можем сохранить маленьким при увеличении , то эффект сообщения об ошибке асимптотически равен нулю. Другое состоит в том, что для любого заданного (количество бросков симулятора sided для моделирования) мы хотим сделать как можно меньшим.F Fm mm mc cFF

Давайте внимательнее посмотрим на , очистив знаменатели:( 2 )(2)

N c m = d n - N F > 0.

Ncm=dnNF>0.

Это делает очевидным, что в данном контексте (определяемом ), делается настолько малым, насколько это возможно, делая равным наибольшему кратному , которое меньше или равно Мы можем написать это в терминах наибольшей целочисленной функции (или «этажа») какc , d , n , m c,d,n,mF Fd n - N F dnNFc m cmd n . dn.

N = d nс м.

N=dncm.

Наконец, ясно, что должно быть как можно меньше для достижения максимальной эффективности, потому что он измеряет избыточность по . В частности, ожидаемое число рулонов односторонняя умирают необходимо произвести один рулон односторонняя штампаN Nт д сtdc

N × nм ×11 - ф .

N×nm×11F.

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

Анализ заканчивается, показывая, что для данных и существует последовательность, кратная для которой этот подход приближается к идеальной эффективности. Это равносильно нахождению для которого приближается к в пределе (автоматически гарантируя ). Одна такая последовательность получается путем взятия и определенияd dc , c,( n , m ) (n,m)( n , m ) (n,m)d n / c m1 dn/cm1N = 1 N=1F 0 F0n = 1 , 2 , 3 , n=1,2,3,

m = n log dlog c.

m=nlogdlogc.(3)

Доказательство простое.

Все это означает , что , когда мы готовы свернуть оригинальный односторонняя умирают достаточно большое число раз мы можем ожидать , чтобы имитировать почти результата односторонняя умирают за рулон , Эквивалентноеd dn , n,log d / log c = log c d logd/logc=logcdcc

Можно смоделировать большое количество независимых бросков кубика sided, используя кубик sided, используя среднее значение катится по результатам», где « можно сделать сколь угодно малым, выбрав « достаточно большим.m mc cd dlog ( c ) / log ( d ) + ϵ = log d ( c ) + ϵ log(c)/log(d)+ϵ=logd(c)+ϵϵ ϵmm


Примеры и алгоритмы

В вопросе и откудад = 6 d=6с = 150 ,c=150,

log d ( c ) = log ( c )log ( d )2.796489.

logd(c)=log(c)log(d)2.796489.

Таким образом, наилучшая возможная процедура потребует в среднем не менее бросков a для имитации каждого результата.2.7964892.796489d6d150

Анализ показывает, как это сделать. Нам не нужно прибегать к теории чисел для ее выполнения: мы можем просто составить таблицу степеней и степеней и сравнить их, чтобы найти, где близко. Этот расчет грубой силы дает парd n = 6 n dn=6nc m = 150 м cm=150mc md ncmdn ( n , м )(n,m)

( n , m ) { ( 3 , 1 ) , ( 14 , 5 ) , }

(n,m){(3,1),(14,5),}

например, соответствующий номерам

( 6 n , 150 м ) { ( 216 , 150 ) , ( 78364164096 , 75937500000 ) , } .

(6n,150m){(216,150),(78364164096,75937500000),}.

В первом случае связывает результатов трех бросков a до отказа, а остальные результатов будут связаны с одним результатом a . t t216 - 150 = 66 216150=66d6150150d150

Во втором случае связал бы из результатов 14 бросков a до отказа - около 3,1% от всех - и в противном случае бы последовательность из 5 результатов a .т t78364164096 - 759375000007836416409675937500000d6d150

Простой алгоритм реализацииtt d 0 , 1 , , d - 1 c 0 , 1 , , c - 1. n n d . с . м м т помечает грани кубика sided цифрами а грани кубика sided цифрами В рулоны первого кристалла интерпретируется как -значного числа в базовом Это преобразуется в число в базе Если он имеет не более цифр, последовательность последних цифр является выходной. В противном случае, возвращает Failure, вызывая себя рекурсивно.d0,1,,d1c0,1,,c1.nnd.c.mmt

Для гораздо более длинных последовательностей вы можете найти подходящие пары , рассматривая все остальные сходящиеся продолжающегося расширения дроби Теория непрерывных дробей показывает, что эти конвергенты чередуются между меньшим, чем и большим, чем оно (при условии, что еще не рационально). Выберите те, которые меньше, чем( n , m ) (n,m)n / m n/mx = log ( c ) / log ( d ) . x=log(c)/log(d).х xх xх .x.

В вопросе, первые несколько таких конвергентов

3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070.

3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070.

В последнем случае последовательность из 29 036 139 бросков a d6будет производить последовательность из 10 383 070 бросков a d150с частотой отказов менее умножить на для эффективности неотличимой от асимптотического предела.2×108,2×108,2.796492.79649

Whuber
источник
2
Удивительно, как всегда, похоже, что этот ответ был отформатирован и подготовлен еще до того, как был задан вопрос!
Лукаш Град,
1
Спасибо, @ ŁukaszGrad. Однако я не виновен ни в каких подобных махинациях, и я уверен, что проницательные читатели найдут доказательства спешки, с которой я это написал, за что я заранее извиняюсь.
whuber
Не следует ли также учитывать, что когда не простое, пробное пространство можно разбить на подмножества с равной вероятностью? Например, вы можете использовать d6 в качестве d2 или d3, и пробное пространство с 162 элементами - ближе к 150, чем 216 - тогда может быть достигнуто с 4 бросками, 1d6 + 3d3. (Это дает те же ожидаемые броски № как решение 3d6, но меньшую дисперсию.)ddΩ(d,1)Ω(d,1)
Scortchi - Восстановить Монику
@Scortchi Вы описываете несколько иную настройку, в которой у вас есть выбор игральных костей, чтобы использовать их для симуляции розыгрышей из равномерного распределения. Аналогичный анализ применим - вам может показаться забавным проводить его.
whuber
7

Для случая , бросание d6 трижды отчетливо создает результатов.N=150N=15063=21663=216

Желаемый результат может быть сведен в таблицу следующим образом:

  • Запишите d6 три раза подряд. Это дает результаты . Результат одинаков, потому что все значения одинаково вероятны (игральные кости справедливы, и мы рассматриваем каждый бросок как отдельный).a,b,ca,b,ca,b,ca,b,c
  • Вычтите 1 из каждого.
  • Это старшее число: каждая цифра (значение места) изменяется от 0 до 5 6, поэтому вы можете записать число в десятичном виде, используя(a1)×62+(b1)×61+(c1)×60
    (a1)×62+(b1)×61+(c1)×60
  • Добавьте 1.
  • Если результат превышает 150, откажитесь от результата и снова бросьте.

Вероятность сохранения результата равна . Все броски независимы, и мы повторяем процедуру до «успеха» (результат в ), поэтому количество попыток сгенерировать 1 ничью между 1 и 150 распределяется как геометрическая случайная величина, которая имеет ожидание . Следовательно, использование этого метода для генерации 1 розыгрыша требует броска броска костей в среднем (поскольку каждая попытка бросает 3 кубика).p=150216=2536p=150216=25361,2,,1501,2,,150p1=3625p1=36253625×3=4.323625×3=4.32


Благодарим @whuber, чтобы он предложил это в чате.

Sycorax говорит восстановить Монику
источник
Я считаю, что метод Генри не дает равномерного распределения. Это потому, что переработка приведет к тому, что некоторые цифры будут отдаваться предпочтению. Я не совсем уверен в этом, потому что я не совсем понимаю, как должна выполняться рециркуляция.
whuber
1
@ Whuber АХ! Теперь я понимаю вашу озабоченность. Я просто попытался объяснить сам процесс и понял, почему моя интуиция была ошибочной: вероятность броска дополнительного кубика может изменить распределение вероятностей десятичным числам и сделать его неравномерным, потому что мы заранее не знаем, как много костей мы катимся.
Sycorax говорит восстановить Monica
4

Вот еще более простая альтернатива ответу Sycorax для случая, когда . Поскольку вы можете выполнить следующую процедуру:N=150N=150150=5×5×6150=5×5×6

Генерация равномерного случайного числа от 1 до 150:

  • Сделайте три заказанных их как .R1,R2,R3R1,R2,R3
  • Если какой-либо из первых двух бросков равен шести, повторяйте его, пока не станет 6.
  • Число - это единое число, использующее позиционную запись с радиусом 5-5-6. Таким образом, вы можете вычислить желаемое число следующим образом: (R1,R2,R3)(R1,R2,R3)X=30(R11)+6(R21)+(R31)+1.
    X=30(R11)+6(R21)+(R31)+1.

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

Восстановить Монику
источник
1
Можете ли вы указать эффективность этого метода с точки зрения ожидаемого количества выпавших бросков за раздачу и уточнить, почему результат одинаков на 1,2, ...., 150?
Sycorax говорит восстановить Монику
Вероятность получения результата, который не требует повторного , равна , что совпадает с вашим ответом. Чтобы понять, почему оно одинаково, обратите внимание, что вы фактически просто генерируете единообразное число, используя позиционную запись с основанием 5-5-6 (т. Е. Последняя цифра - это единицы, вторая-последняя цифра - это «шестерки», а третья - третья). последняя цифра это "тридцатые"). 25/3625/36
Восстановите Монику
1
Метод, по сути, является лишь незначительной вариацией метода в вашем ответе. В своем ответе вы создаете единое число по шкале 6-6-6, а затем отбрасываете недопустимые значения, тогда как в моем ответе вы сначала отбрасываете недопустимые значения, чтобы сгенерировать число по шкале 5-5-6.
Восстановите Монику
3
+1 На практике это привлекательный алгоритм. Интересно и, возможно, наводит на мысль о более широком анализе, что он реализует автомат конечного состояния, управляемый роликами. Он имеет четыре состояния: {Пуск, A, B, Принять}. Начать переходы к А при прокатке 1..5; А переходы на В при прокатке 1..5; и B переходит в Accept при броске чего-либо. Каждый переход сохраняет значение броска, который его вызвал, поэтому при достижении Accept вы выводите эту последовательность из трех сохраненных бросков и автоматически возвращаетесь к началу.
whuber
4
Вы отклоняете так же часто, как @Sycorax, но в среднем делаете меньше бросков. Ожидаемое нет. бросок на переменную равен . 65 +65 +1=3,465+65+1=3.4
Scortchi - Восстановить Монику
2

В качестве иллюстрации алгоритма для равномерного выбора между значениями с использованием шестигранных кубиков, попробуйте это, в котором каждый бросок умножает доступные значения на и делает равным вероятность каждого из новых значений:150 15066

  • После бросков у вас есть возможность, недостаточно, чтобы различить значений0 01 1150150
  • После броска у вас есть возможностей, которых недостаточно для различения значений.1 16 6150150
  • После бросков у вас есть возможностей, которых недостаточно, чтобы различить значений2 236 36150150
  • После бросков у вас есть возможностей, достаточно, чтобы различить значений, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна3 3216 216150 15066 66150216150216
  • Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для различения значений двумя способами, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна4 4396 396150 15096 9630012963001296
  • Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для трех различий между значениями, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна5 5576 576150 15096 9645077764507776
  • Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для различения значений пятью способами, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна6 6756 756150 1506 67504665675046656

Если вы находитесь на одном из оставшихся значений после бросков, то вы находитесь в ситуации, аналогичной позиции после броска. Таким образом, вы можете продолжить таким же образом: вероятность того, что вы остановитесь после бросков, равна , после бросков - и т. Д.6 66 1 7 0279936 81501679616

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


Sycorax попросил в комментариях более явный алгоритм

  • Во-первых, я буду работать в базе с6 150 10 = 410 6
  • Во-вторых, вместо целевых значений от до я одно, поэтому целевые значения составляют от до1 6 410 6 0 6 409 6
  • В-третьих, каждый кубик должен иметь значения от до , и кубика включает добавление цифры основания к правой стороне существующего сгенерированного числа. Сгенерированные числа могут иметь начальные нули, а число цифр - это число бросков на данный момент.0 6 5 6 6

Алгоритм последовательных бросков костей:

  • первые три кубика, чтобы получить число от до . Поскольку вы берете сгенерированное значение (которое также является его остатком от деления на ), если сгенерированное значение строго ниже и остановитесь;000 6 555 6 1000 6 ÷ 410 6 = 1 6  остаток  150 6 410 6 1000 6 - 150 6 = 410 6

  • Если вы продолжаете, бросьте четвертый кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;4100 6 5555 6 10000 6 ÷ 410 6 = 12 6  остаток  240 6 410 6 10000 6 - 240 6 = 5320 6

  • Если вы продолжите, бросьте пятый кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;5320065555561000006÷4106=1236 remainder 3306410610000063306=552306

  • Если вы продолжите, бросьте шестой кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;5523006555555610000006÷4106=12356 remainder 106410610000006106=5555506

  • и т.п.

Генри
источник
(+1) Этот ответ был бы более понятным, если бы вы объяснили, каким образом вы сопоставляете результаты, скажем, 4d6 или 5d6 с 1,2, ..., 150.
Sycorax говорит, что восстановите Монику
@Sycorax - я теперь предоставил основание карт6
Генри
1
Соображения энтропии показывают, что вы можете добиться значительно большего успеха, чем этот алгоритм. Осталось также показать, что ваш алгоритм фактически выдает независимо распределенные значения с равномерным распределением.
whuber
@whuber - Мой алгоритм выдает ровно одно целое число из возможных и делает это равномерно, при условии, что броски костей единообразны и независимы. На каждом шаге, если он достигнут, вероятно, будет выбрано каждое из значений. Он не 150 150
Генри
1
Я неправильно понял, что вы имели в виду, когда писал: «алгоритм - это последовательные броски костей». (Я должен был прочитать более внимательно.) При этом, мне кажется, ваш алгоритм не дает равномерного распределения, но я не уверен, потому что я не смог выяснить, для чего предназначен общий алгоритм быть. Было бы хорошо увидеть демонстрацию того, что она дает одинаковые значения.
whuber