Уменьшает ли смещение повторяющееся случайное перемешивание?

Question

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

Известно, что тасование Фишера-Йейтса несмещено, пока основной генератор случайных чисел (ГСЧ)является беспристрастным.

To shuffle an array a of n elements:
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Но что, если ГСЧ смещен (но быстрый)?

Предположим, я хочу произвести много случайных перестановок массива из 25 элементов.Если я использую алгоритм Фишера-Йейтса со смещенным ГСЧ, то моя перестановка будет смещенной, но я полагаю, что это предполагает, что массив из 25 элементов начинается с одного и того же состояния перед каждым применением алгоритма тасования.Одна из проблем, например, заключается в том, что если ГСЧ имеет период только 2 ^ 32 ~ 10 ^ 9, мы не можем произвести все возможные перестановки 25 элементов, потому что это 25!~ 10 ^ 25 перестановок.

Мой общий вопрос: если я оставлю перетасованные элементы перемешанными перед началом каждого нового применения тасования Фишера-Йейтса, уменьшит ли это смещение и / или позволит ли алгоритм генерировать каждоеперестановка?

Я предполагаю, что это, как правило, дало бы лучшие результаты, но кажется, что если бы повторно перемешиваемый массив содержал ряд элементов, связанных с базовым ГСЧ, то перестановки могли бы фактически повторяться чаще, чем ожидалось..

Кто-нибудь знает о каких-либо исследованиях, которые касаются этого?

В качестве подвопроса, что если я хочу только повторные перестановки 5 из 25 элементов в массиве, поэтому я используюАлгоритм Фишера-Йейтса для выбора 5 элементов и остановки перед выполнением полной случайной последовательности?(Я использую 5 элементов в конце массива, который был заменен.) Затем я начинаю заново, используя предыдущий частично перемешанный 25-элементный массив, чтобы выбрать другую перестановку 5. Опять же, кажется, что это было бы лучше, чем начинать сисходный массив из 25 элементов, если базовый ГСЧ имел смещение.Есть какие-нибудь мысли по этому поводу?

Я думаю, что было бы легче протестировать случай частичного перемешивания, поскольку существует только 6 375 600 возможных перестановок из 5 из 25 элементов, поэтому есть ли какие-либо простые тесты, которые можно использовать для проверки на смещения?

Answer 1

, если ГСЧ имеет период только 2 ^ 32 ~ 10 ^ 9, мы не можем произвести все возможные перестановки 25 элементов, потому что это 25!~ 10 ^ 25 перестановок

Это верно только в том случае, если семя определяет каждый последующий выбор.Если можно ожидать, что ваш ГСЧ будет обеспечивать точно равномерное распределение в диапазоне, указанном для каждого следующего выбора, он может производить каждую перестановку.Если ваш ГСЧ не может этого сделать, большая база семян не поможет.

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

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

Answer 2

У меня такое чувство, что при смещенном ГСЧ повторные прогоны Кнута будут перемешивать все перестановки, но я не могу доказать это (это зависит от периода ГСЧ и , насколько это смещено ).

Итак, давайте обратимся к вопросу: учитывая алгоритм, который требует случайного ввода и смещенного ГСЧ, легче ли де-перекосить выходные данные алгоритма или де-перекосить выходные данные ГСЧ?

Неудивительно, что последнее намного проще (и представляет более широкий интерес): для этого есть несколько стандартных методов. Простой метод, благодаря фон Нейману, заключается в следующем: учитывая поток битов от смещенного ГСЧ, принимать биты парами, отбрасывать каждую (0,0) и (1,1) пару, возвращать 1 для каждой (1,0) пара и 0 для каждой (0,1) пары. Этот метод предполагает, что биты взяты из потока, где каждый бит имеет такую ​​же вероятность быть 0 или 1, как любой другой бит в потоке, и что биты не коррелированы. Элиас обобщил технику фон Неймана на более эффективную схему (такую, где отбрасывается меньше битов).

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

Другой вариант - передать смещенный вывод ГСЧ в криптографически сильную функцию, например, алгоритм дайджеста сообщения, и использовать его вывод.

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

Моя точка зрения заключается в том, что качество, если выходные данные алгоритма на основе случайных чисел ограничены сверху энтропией, обеспечиваемой ГСЧ: если оно чрезвычайно смещено, выходные данные будут чрезвычайно смещены, независимо от того, что вы делаете. Алгоритм не может сжать больше энтропии, чем тот, который содержится в смещенном случайном битовом потоке. Хуже того: он, вероятно, потеряет несколько случайных битов. Даже если предположить, что алгоритм работает с предвзятым ГСЧ, для получения хорошего результата вам придется приложить вычислительные усилия, по крайней мере, такие же, как усилия, которые потребовались бы для отвода ГСЧ (но, вероятно, для этого потребуется больше усилий, так как вам придется одновременно запускать алгоритм и «победить» смещение).

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

Answer 3

Пара моментов:

1) Любой, кто использует shuffle Фишера Йетса, должен прочитать this и убедиться, что их реализация вдвойне верна.
2) Не повторяетперемешать победить цель использования более быстрого генератора случайных чисел?Конечно, если вам придется повторять каждый случай 5 раз, чтобы получить желаемую энтропию, лучше использовать генератор низкого смещения.
3) Есть ли у вас настройки, где вы можете это проверить?Если так, то начинайте пробовать вещи - графики Джеффса дают понять, что вы можете легко обнаружить довольно много ошибок, используя небольшие колоды и визуально отображая результаты.

Answer 4

Это полностью зависит от предвзятости. В общем, я бы сказал "не рассчитывай".

Смещенный алгоритм, который сходится к несмещенному:

Ничего не делай половину времени, и правильно перетасуй другую половину. Сходится к непредвзятому экспоненциально. После n перемешиваний есть вероятность 1-1 / 2 ^ n, что перемешивание не смещено, и 1/2 ^ n вероятность, что была выбрана входная последовательность.

Смещенный алгоритм, который остается смещенным:

Перемешать все элементы, кроме последнего. Постоянно смещен в сторону не двигать последний элемент.

Более общий пример:

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

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

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

Answer 5

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

Что произойдет, если вы убедитесь, что число случайных чисел, извлекаемых из вашего ГСЧ для каждой итерации Фишера-Йейтса, имеет наименьшее общее кратное с периодом ГСЧ? Это может означать, что вы «тратите» случайное целое число в конце алгоритма. Когда тасуется 25 элементов, вам нужно 24 случайных числа. Если вы вытяните еще одно случайное число в конце, сделав 25 случайных чисел, вы не гарантированно будете иметь повторение намного дольше, чем период ГСЧ. Теперь, случайно, у вас могут быть те же 25 чисел, встречающиеся подряд, прежде чем они достигнут периода, конечно. Но, поскольку 25 не имеет общих факторов, кроме 1 с 2 ^ 32, вы не получите гарантированное повторение до 25 * (2 ^ 32). Теперь, это не большое улучшение, но вы сказали, что этот ГСЧ быстрый. Что, если ценность "отходов" была намного больше? Возможно, все еще непрактично получать каждую перестановку, но вы могли бы по крайней мере увеличить число, которого можете достичь.