Является ли отбраковка выборки единственным способом получить действительно равномерное распределение случайных чисел?

Question

Предположим, что у нас есть генератор случайных чисел, который выводит числа в диапазоне $ [0 .. R-1] $ с равномерным распределением, и нам нужно сгенерировать случайные числа в диапазоне $ [0.. N-1] $ с равномерным распределением.

Предположим , что $ N < R $ и $ N $ неравномерно делят $ R $;для того, чтобы получить действительно равномерное распределение мы можем использовать отбраковка образцов способ:

• если $ k $ - наибольшее целое число, такое, что $ k N < R$
• выберите случайное число $r$ в $[0..R-1]$
• если $r < k N $ затем выведите $ r \ mod N $, в противном случае продолжайте попытки с другими случайными числами r', r", ...до тех пор, пока не будет выполнено это условие

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

Если ответ "да", то почему?

Примечание:если $ N > R $, то идея та же самая:сгенерируйте случайное число $r'$ в $[0..R^m-1], R^m >= N$, например $r' = R(...R(R r_1 + r_2)...)+r_m$, где $r_i$ - случайное число в диапазоне $[0..R-1]$

Answer 1

Да или нет, в зависимости от того, что вы подразумеваете под “единственным способом”.Да, поскольку нет метода, который гарантированно завершался бы, лучшее, что вы можете сделать (для общих значений $ N $ и $ R $), - это алгоритм, который завершается с вероятностью 1.Нет, в том смысле, что вы можете сделать “отходы” настолько маленькими, насколько вам нравится.

Почему гарантированное расторжение договора вообще невозможно

Предположим, что у вас есть детерминированный вычислительный движок (машина Тьюринга или что-то еще, что управляет вашей лодкой), плюс оракул, который генерирует случайные элементы набора $ R $-элементов $ [0 .. R-1] $.Ваша цель - сгенерировать элемент из набора $N $-элементов $[0,N-1] $.Выходные данные вашего движка зависят только от последовательности значений, возвращаемых oracle;это функция $f $ этой потенциально бесконечной последовательности $(r_0, r_1, r_2, \ldots) $.

Предположим, что ваш движок вызывает oracle не более $ m $ раз.Могут быть трассы, для которых оракул вызывается менее $ m $ раз;если это так, то вызов oracle дополнительные разы, чтобы он всегда вызывался ровно $ m $ раз, не изменит результат.Таким образом, без потери общности мы предполагаем, что оракул вызывается ровно $ m $ раз.Тогда вероятность результата $x$ равна числу последовательностей $(r_0, \ldots, r_{m-1})$ таких, что $f(r_0, \ldots, r_{m-1}) = x$.Поскольку оракул является однородным генератором случайных чисел, каждая последовательность равновероятна и имеет вероятность $ 1 /R ^ m $.Следовательно, вероятность каждого исхода имеет вид $ A / R ^ m $, где $ A $ - целое число от $ 0 $ до $ R ^ m $.

Если $ N $ делит $ R ^ m $ на некоторое $ m $, то вы можете сгенерировать равномерное распределение по $ N $ элементам, вызвав генератор случайных чисел $ m $ раз (это оставлено в качестве упражнения для читателя).В противном случае это невозможно:нет никакого способа получить результат с вероятностью $ 1 / N $.Обратите внимание, что условие эквивалентно утверждению, что все простые множители $ N $ также являются множителями $ R $ (это более допустимо, чем то, что вы написали в своем вопросе;например, вы можете выбрать случайный элемент из 4 с 6-сторонним честным кубиком, даже если 4 не делит 6).

Сокращение количества отходов

В вашей стратегии, когда $ r \ge k \, N $, вам не нужно немедленно переигрывать.Интуитивно понятно, что в $ [k\,N осталось немного энтропии ..R-1] $, который вы можете сохранить в составе.

Предположим на мгновение, что вы на самом деле будете продолжать генерировать случайные числа ниже $ N $ вечно, и вы генерируете $ u $ из них за раз, делая $ d $ розыгрыши.Если вы выполняете простую выборку отбраковки для этого сгруппированного поколения, потери при розыгрыше $ d $ равны $\ dfrac {R ^ d - k \,N ^ u} {d} $, т.е.остаток $ R ^ d \mathbin {\mathrm {mod}} N ^ u $ делится на количество розыгрышей.Это может быть всего лишь $\gcd (R, N) $.Когда $ R $ и $ N $ взаимно просты, вы можете сделать потери сколь угодно малыми, выбрав достаточно большие значения $ d $.Для общих значений $ R $ и $ N $ расчет сложнее, потому что вам нужно учитывать генерацию $ \ gcd (R, N) $ и $ N / \ gcd (R, N) $ по отдельности, но опять же, вы можете сделать отходы сколь угодно малыми с достаточно большими группами.

На практике, даже с относительно неэффективными случайными числами (например,в криптографии), редко стоит делать что-либо, кроме простой выборки отклонения, если только $ N $ не невелико.Например, в криптографии, где $ R $ обычно представляет собой степень 2, а $ N $ обычно составляет сотни или тысячи бит, генерация однородных случайных чисел обычно осуществляется путем прямой выборки с отклонением в желаемом диапазоне.

Answer 2

Теорема исходного кодирования Шеннона показывает, что в некотором смысле вам нужны образцы $ n/ log r $ (в среднем) типа $ [0, ldots, r-1] $, чтобы генерировать случайное число Тип $ [0, ldots, n-1] $. Более того, Shannon дает (неэффективный) алгоритм, который приведены образцы $ M $ первого типа, выводит $ m ( log n/ log r - epsilon) $ образцы второго типа с высокой вероятностью. Он также показывает, что вывода $ m ( log n/ log r + epsilon) $ образцы с высокой вероятностью невозможно.

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

Answer 3

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

Эта теорема является классическим результатом Кнута и Яо (1976), который разработал рамку DDG-деревьев (дискретные деревья, генерирующие распределение).

Методы, подвергшиеся жаленам, - это типичные вещи, которые были сделаны для смягчения отходов, понесенных отказа сохраняются.

Я дал больше информации об этом в следующем CSTheory Post.