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

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

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

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

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

---

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

Множество различных идентифицируемых результатов в независимых бросках матрицы с гранями имеет элементов. Когда кубик справедлив, это означает, что каждый результат одного броска имеет вероятность а независимость означает, что каждый из этих результатов будет иметь вероятность то есть они имеют равномерное распределение$\Omega(d,n)$$n$$d=6$$d^n$$1/d$$(1/d)^n:$$\mathbb{P}_{d,n}.$

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

$$t:\Omega(d,n)\to\Omega(c,m)\cup\{\text{Failure}\}.$$

Пусть $F$ - вероятность $t$ приводящая к провалу, и отметим, что $F$ - некоторое целое кратное $d^{-n},$ скажем

$$F = \Pr(t(\omega)=\text{Failure}) = N_F\, d^{-n}.$$

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

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

$$\frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) \tag{1}$$

где

$$t^{*}\left(\mathcal A\right) = \{\omega\in\Omega\mid t(\omega)\in\mathcal{A}\}$$

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

Рассмотрим атомное событие , которое должно иметь вероятностьПусть (броски костей, связанные с ) имеют элементов. становится$\mathcal A = \{\eta\}\subset\Omega(c,m)$$c^{-m}.$$t^{*}\left(\mathcal A\right)$$\eta$$N_\eta$$(1)$

$$\frac{N_\eta d^{-n}}{1 - N_F d^{-n}} = \frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) = c^{-m}.\tag{2}$$

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

$$\frac{1}{m}\left(1 - F\right).$$

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

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

$$N c^m = d^n - N_F \gt 0.$$

Это делает очевидным, что в данном контексте (определяемом ), делается настолько малым, насколько это возможно, делая равным наибольшему кратному , которое меньше или равно Мы можем написать это в терминах наибольшей целочисленной функции (или «этажа») как$c,d,n,m$$F$$d^n-N_F$$c^m$$d^n.$$\lfloor*\rfloor$

$$N = \lfloor \frac{d^n}{c^m} \rfloor.$$

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

$$N \times \frac{n}{m} \times \frac{1}{1-F}.$$

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

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

$$m = \lfloor \frac{n\log d}{\log c} \rfloor.\tag{3}$$

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

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

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

---

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

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

$$\log_d(c) = \frac{\log(c)}{\log(d)} \approx 2.796489.$$

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

Анализ показывает, как это сделать. Нам не нужно прибегать к теории чисел для ее выполнения: мы можем просто составить таблицу степеней и степеней и сравнить их, чтобы найти, где близко. Этот расчет грубой силы дает пар$d^n=6^n$$c^m=150^m$$c^m \le d^n$$(n,m)$

$$(n,m) \in \{(3,1), (14,5), \ldots\}$$

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

$$(6^n, 150^m) \in \{(216,150), (78364164096,75937500000), \ldots\}.$$

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

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

Простой алгоритм реализации$t$ d 0 , 1 , … , d - 1 c 0 , 1 , … , c - 1. n n d . с . м м т помечает грани кубика sided цифрами а грани кубика sided цифрами В рулоны первого кристалла интерпретируется как -значного числа в базовом Это преобразуется в число в базе Если он имеет не более цифр, последовательность последних цифр является выходной. В противном случае, возвращает Failure, вызывая себя рекурсивно.$d$$0,1,\ldots, d-1$$c$$0,1,\ldots, c-1.$$n$$n$$d.$$c.$$m$$m$$t$

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

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

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

В последнем случае последовательность из 29 036 139 бросков a d6будет производить последовательность из 10 383 070 бросков a d150с частотой отказов менее умножить на для эффективности неотличимой от асимптотического предела.$2\times 10^{-8},$$2.79649$

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

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

• Запишите d6 три раза подряд. Это дает результаты . Результат одинаков, потому что все значения одинаково вероятны (игральные кости справедливы, и мы рассматриваем каждый бросок как отдельный).$a,b,c$$a,b,c$
• Вычтите 1 из каждого.
• Это старшее число: каждая цифра (значение места) изменяется от 0 до 5 6, поэтому вы можете записать число в десятичном виде, используя $$(a-1) \times 6^2 + (b-1) \times 6^1 + (c-1)\times 6^0$$
• Добавьте 1.
• Если результат превышает 150, откажитесь от результата и снова бросьте.

Вероятность сохранения результата равна . Все броски независимы, и мы повторяем процедуру до «успеха» (результат в ), поэтому количество попыток сгенерировать 1 ничью между 1 и 150 распределяется как геометрическая случайная величина, которая имеет ожидание . Следовательно, использование этого метода для генерации 1 розыгрыша требует броска броска костей в среднем (поскольку каждая попытка бросает 3 кубика).$p=\frac{150}{216}=\frac{25}{36}$$1,2,\dots,150$$p^{-1}=\frac{36}{25}$$\frac{36}{25}\times 3 =4.32$

---

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

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

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

• Сделайте три заказанных их как .$R_1, R_2, R_3$
• Если какой-либо из первых двух бросков равен шести, повторяйте его, пока не станет 6.
• Число - это единое число, использующее позиционную запись с радиусом 5-5-6. Таким образом, вы можете вычислить желаемое число следующим образом: $(R_1, R_2, R_3)$ $$X = 30 \cdot (R_1-1) + 6 \cdot (R_2-1) + (R_3-1) + 1.$$

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

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

• После бросков у вас есть возможность, недостаточно, чтобы различить значений$0$$1$$150$
• После броска у вас есть возможностей, которых недостаточно для различения значений.$1$$6$$150$
• После бросков у вас есть возможностей, которых недостаточно, чтобы различить значений$2$$36$$150$
• После бросков у вас есть возможностей, достаточно, чтобы различить значений, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна$3$$216$$150$$66$$\frac{150}{216}$
• Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для различения значений двумя способами, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна$4$$396$$150$$96$$\frac{300}{1296}$
• Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для трех различий между значениями, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна$5$$576$$150$$96$$\frac{450}{7776}$
• Если вы не остановились, то после бросков у вас остается оставшихся возможностей, что достаточно для различения значений пятью способами, но с оставшимися значениями; вероятность того, что вы сейчас остановитесь, равна$6$$756$$150$$6$$\frac{750}{46656}$

Если вы находитесь на одном из оставшихся значений после бросков, то вы находитесь в ситуации, аналогичной позиции после броска. Таким образом, вы можете продолжить таким же образом: вероятность того, что вы остановитесь после бросков, равна , после бросков - и т. Д.$6$$6$$1$$7$$\frac{0}{279936}$$8$$\frac{150}{1679616}$

их, и вы увидите, что ожидаемое количество необходимых бросков составляет около . Он обеспечивает равномерный выбор из , поскольку вы выбираете значение только в тот момент, когда вы можете выбрать каждый из с равной вероятностью.$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 \div 410_6 = 1_6 \text{ remainder } 150_6$$410_6$$1000_6-150_6=410_6$

• Если вы продолжаете, бросьте четвертый кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;$4100_6$$5555_6$$10000_6 \div 410_6 = 12_6 \text{ remainder } 240_6$$410_6$$10000_6-240_6=5320_6$

• Если вы продолжите, бросьте пятый кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;$53200_6$$55555_6$$100000_6 \div 410_6 = 123_6 \text{ remainder } 330_6$$410_6$$100000_6-330_6=55230_6$

• Если вы продолжите, бросьте шестой кубик, чтобы сгенерировать число от до . Поскольку вы берете остаток от сгенерированного значения при делении на если сгенерированное значение строго ниже и останавливаетесь;$552300_6$$555555_6$$1000000_6 \div 410_6 = 1235_6 \text{ remainder } 10_6$$410_6$$1000000_6-10_6=555550_6$

• и т.п.