Предположим, что у нас есть генератор случайных чисел, который выводит числа в диапазоне с равномерным распределением, и нам нужно генерировать случайные числа в диапазоне с равномерным распределением.
Предположим, что и не делит равномерно ; чтобы получить действительно равномерное распределение, мы можем использовать метод выборки отклонения :
- если наибольшее целое число такое, что
- выберите случайное число в
- если тогда выведите , в противном случае продолжайте пробовать другие случайные числа r ', r ", ..., пока не будет выполнено условие
Является ли выборка отклонения единственным способом получить действительно равномерное дискретное распределение?
Если ответ да, почему?
Примечание: если идея та же: сгенерировать случайное число в , например, где - случайное число в диапазоне
Ответы:
Да и нет, в зависимости от того, что вы подразумеваете под «единственным способом». Да, в том смысле, что не существует метода, который гарантированно завершает работу, лучшее, что вы можете сделать (для общих значений и ), это алгоритм, который завершается с вероятностью 1. Нет, в том смысле, что вы можете сделать «отходы» малыми. как тебе нравится.RN R
Почему гарантированное прекращение вообще невозможно
Предположим, что у вас есть детерминированный механизм вычислений (машина Тьюринга или что-то еще, что плавает на вашей лодке), а также оракул, который генерирует случайные элементы из набора элементов . Ваша цель состоит в том, чтобы сформировать элемент - элементного множества . Выход вашего движка зависит только от последовательности значений, возвращаемых оракулом; это функция этой потенциально бесконечной последовательности .[ 0 .. R - 1 ] N [ 0 , N - 1 ] f ( r 0 , r 1 , r 2 , … )R [0..R−1] N [0,N−1] f (r0,r1,r2,…)
Предположим, что ваш двигатель вызывает оракула не более раз. Могут быть следы, для которых оракул вызывается менее чем раз; если это так, то вызов дополнительного оракула так, чтобы он всегда вызывался ровно раз, не меняет вывод. Поэтому без ограничения общности мы предполагаем, что оракул вызывается ровно раз. Тогда вероятность результата - это число последовательностей таких что . Поскольку оракул является равномерным генератором случайных чисел, каждая последовательность равновероятна и имеет вероятность . Следовательно, вероятность каждого исхода имеет видm m m x ( r 0 , … , r m - 1 ) f ( r 0 , … , r m - 1 ) = x 1 / R m A / R m A 0 R mm m m m x (r0,…,rm−1) f(r0,…,rm−1)=x 1/Rm A/Rm где - целое число от до .A 0 Rm
Если делит на несколько , то вы можете сгенерировать равномерное распределение по элементам, вызвав случайный генератор раз (это оставлено в качестве упражнения для читателя). В противном случае, это невозможно: нет никакого способа , чтобы получить результат с вероятностью . Обратите внимание, что условие равносильно тому, что все главные факторы также являются факторами (это более допустимо, чем то, что вы написали в своем вопросе; например, вы можете выбрать случайный элемент среди 4 с 6-сторонним справедливым умри, хотя 4 не делит 6).R m m N m 1 / N N RN Rm m N m 1/N N R
Сокращение отходов
В вашей стратегии, когда , вам не нужно сразу перерисовывать. Интуитивно понятно, что в осталось немного энтропии, которую вы можете оставить в миксе.[ кr≥kN [kN..R−1]
Предположим на мгновение, что вы на самом деле будете продолжать генерировать случайные числа ниже навсегда, и вы будете генерировать их из за один раз, делая розыгрыши. Если вы выполняете прямую выборку отклонения для этого сгруппированного поколения, расточительство в течение розыгрышей будет , то есть остаток деленное на количество розыгрышей. Это может быть всего . Когда и взаимно просты, вы можете сделать отходы сколь угодно малыми, выбрав достаточно большие значения . Для общих значений иу d d R D - KN u d d рдмоднужкд(R,N)Rd−kNud RdmodNu gcd(R,N) R N d R N расчет более сложный, потому что вам нужно учитывать генерацию и отдельно, но опять же вы можете сделать отходы сколь угодно малыми с достаточно большими группами.gcd(R,N) N/gcd(R,N)
На практике, даже с относительно неэффективными случайными числами (например, в криптографии), редко стоит делать что-либо, кроме простой выборки отклонения, если не мало. Например, в криптографии, где как правило, представляет собой степень 2, а как правило, составляет сотни или тысячи битов, генерация однородного случайного числа обычно происходит путем выборки с прямым отклонением в желаемом диапазоне.N R N
источник
Теорема Шеннона об исходном кодировании показывает, что в некотором точном смысле вам нужно выборок (в среднем) типа для генерации случайного числа типа . Точнее, Шеннон дает (неэффективный) алгоритм, который дает выборок первого типа, с высокой вероятностью выводит выборок второго типа. Он также показывает, что вывод выборок с высокой вероятностью невозможен.logN/logR [0,…,R−1] [0,…,N−1] m m(logN/logR−ϵ) m(logN/logR+ϵ)
Теорема Шеннона также работает в более общем случае искаженного входного распределения (и, вероятно, также искаженного выходного распределения). В этом случае вам необходимо заменить логарифм на энтропию. Хотя алгоритм, заданный в теореме, определяется случайным образом, в некоторых случаях его можно дерандомизировать (за счет некоторого ухудшения производительности).
источник
На самом деле, нет, отбраковка выборки - далеко не единственный способ продолжить. К сожалению, учитывая, что компьютеры хранят всю информацию в виде битов и, таким образом, могут манипулировать только случайными битами информации, любой алгоритм рисования равномерной случайной величины диапазона будет бесконечным, если двоичное базовое развитие бесконечно.N N
Эта теорема является классическим результатом Кнута и Яо (1976), которые разработали структуру DDG-деревьев (деревьев, генерирующих дискретное распределение).
Методы, раскрытые Жилем, - это типичная вещь, которая была сделана для уменьшения потерь, возникающих при отбраковке, но, конечно, если можно генерировать по деревьям Кнута и Яо, это намного, намного эффективнее - в среднем 96% случайных битов. сохранены
Я дал больше информации об этом в следующем посте CStheory .
источник