Это продолжение вопроса Stackoverflow о случайном перемешивании массива .
Существуют установленные алгоритмы (такие как Кнут-Фишер-Йейтс Шуффл ), которые следует использовать для перемешивания массива, а не полагаться на «наивные» специальные реализации.
Теперь я заинтересован в том, чтобы доказать (или опровергнуть), что мой наивный алгоритм нарушен (как в: не генерирует все возможные перестановки с равной вероятностью).
Вот алгоритм:
Зациклите пару раз (длина массива должна соответствовать), и в каждой итерации получите два индекса случайных массивов и поменяйте местами два элемента.
Очевидно, что для этого нужно больше случайных чисел, чем KFY (вдвое больше), но кроме этого он работает правильно? И какое будет соответствующее количество итераций (достаточно ли «длины массива»)?
Ответы:
Он сломан, хотя, если вы выполняете достаточно перемешиваний, это может быть отличным приближением (как указывалось в предыдущих ответах).
Просто чтобы понять, что происходит, рассмотрим, как часто ваш алгоритм будет генерировать тасования из массива элементов, в котором фиксирован первый элемент, . Когда перестановки генерируются с равной вероятностью, это должно происходить времени. Пусть будет относительной частотой этого вхождения после перемешиваний с вашим алгоритмом. Давайте также будем щедрыми и предположим, что вы на самом деле выбираете разные пары индексов случайным образом для ваших случайных комбинаций, так что каждая пара выбирается с вероятностью =k ≥ 2 1 / k p n n 1 / ( kk k≥2 1/k pn n 2/(k(k-1))1/(k2) 2 / ( k ( k - 1 ) ) , (Это означает, что «тривиальные» тасования не расходуются впустую. С другой стороны, это полностью нарушает ваш алгоритм для двухэлементного массива, потому что вы чередуетесь между фиксацией двух элементов и их заменой, поэтому, если вы остановитесь после заранее определенного числа шагов, нет никакой случайности с результатом!)
Эта частота удовлетворяет простой повторяемости, потому что первый элемент находится на своем первоначальном месте после тасует двумя непересекающимися способами. Во-первых, это было исправлено после перемешиваний, а следующее перемешивание не перемещает первый элемент. Другое дело, что он был перемещен после перемешиваний, но перемешивает его назад. Вероятность не сдвинуть первый элемент равна = , тогда как вероятность переместить первый элемент назад равна = . Откуда:n n n + 1 s t ( k - 1n + 1 N N n + 1с т (k-2)/k1/ ( k( к-12) / ( к2) ( к - 2 ) / к 2/(k(k-1))1 / ( к2) 2 / ( k ( k - 1 ) )
Решение
Вычитая , мы видим, что частота неверна для . Для больших и хорошим приближением является . Это показывает, что ошибка на этой конкретной частоте будет уменьшаться экспоненциально с числом свопов относительно размера массива ( ), указывая на то, что будет трудно обнаружить большие массивы, если вы сделали относительно большое количество свопов - но ошибка всегда есть.( к - 31 / к knk-1( к - 3к - 1)Nк - 1К К N н/кк - 1Кехр( - 2 нк - 1) н / к
Трудно обеспечить всесторонний анализ ошибок на всех частотах. Вполне вероятно, что они будут вести себя так, как это, что показывает, что как минимум вам нужно, чтобы (количество перестановок) было достаточно большим, чтобы сделать ошибку приемлемо малой. Примерное решениеN
где должен быть очень маленьким по сравнению с . Это означает должно быть в несколько раз для четных грубых приближений ( т.е. , где на порядка раз или так.)1 / k n k ϵ 0,01 1 / kε 1 / к N К ε 0,01 1 / к
Все это порождает вопрос: почему вы решили использовать алгоритм, который не совсем (но только приблизительно) корректен, использует те же методы, что и другой алгоритм, который доказуемо корректен и все же требует больше вычислений?
редактировать
Комментарий Тило уместен (и я надеялся, что никто не будет указывать на это, поэтому я мог бы избавиться от этой дополнительной работы!). Позвольте мне объяснить логику.
Если вы уверены, что генерируете реальные свопы каждый раз, вы совершенно облажались. Проблема, которую я указал для случая распространяется на все массивы. Только половина всех возможных перестановок может быть получена путем применения четного числа перестановок; другая половина получается путем применения нечетного числа свопов. Таким образом, в этой ситуации вы никогда не сможете сгенерировать где-либо около равномерного распределения перестановок (но существует так много возможных, что исследование моделирования для любого значительного не сможет обнаружить проблему). Это действительно плохо.кк = 2 К
Поэтому целесообразно генерировать подстановки случайным образом, независимо генерируя две позиции. Это означает, что есть шанс каждый раз менять элемент на себя; то есть ничего не делать. Этот процесс эффективно замедляет алгоритм немного: после шагов мы ожидаем, что произошло только истинных перестановок.n k - 11 / к N к - 1КN< N
Обратите внимание, что размер ошибки монотонно уменьшается с увеличением числа различных перестановок. Поэтому проведение меньшего количества свопов в среднем также увеличивает ошибку в среднем. Но это цена, которую вы должны быть готовы заплатить, чтобы преодолеть проблему, описанную в первом пункте. Следовательно, моя оценка ошибки консервативно низкая, примерно в .( к - 1 ) / к
Я также хотел бы отметить интересное очевидное исключение: внимательный взгляд на формулу ошибки показывает, что в случае ошибки нет . Это не ошибка: это правильно. Однако здесь я рассмотрел только одну статистику, связанную с равномерным распределением перестановок. Тот факт, что алгоритм может воспроизвести эту статистику, когда (а именно получить правильную частоту перестановок, которые фиксируют любую заданную позицию), не гарантирует, что перестановки действительно были распределены равномерно. Действительно, после фактических перестановок единственные возможные перестановки, которые могут быть сгенерированы: ,k = 3 2 n ( 123 ) ( 321 ) 2 n + 1 ( 12 ) ( 23 ) ( 13 )к = 3 к = 3 2 н ( 123 ) ( 321 ) и личность. Только последний фиксирует любую данную позицию, так что в действительности ровно треть перестановок фиксирует позицию. Но половина перестановок отсутствует! В другом случае после фактических перестановок единственными возможными перестановками являются , и . Опять же, точно один из них будет фиксировать любую данную позицию, поэтому мы снова получаем правильную частоту перестановок, фиксирующих эту позицию, но снова мы получаем только половину возможных перестановок.2 н + 1 ( 12 ) ( 23 ) ( 13 )
Этот небольшой пример помогает раскрыть основные аргументы аргумента: будучи «щедрым», мы консервативно недооцениваем частоту ошибок для одной конкретной статистики. Поскольку эта частота ошибок отлична от нуля для всех , мы видим, что алгоритм не работает. Кроме того, анализируя затухание частоты ошибок для этой статистики, мы устанавливаем нижнюю границу для числа итераций алгоритма, необходимого, чтобы иметь хоть какую-то надежду на аппроксимацию равномерного распределения перестановок.k ≥ 4
источник
Я думаю, что ваш простой алгоритм будет перетасовывать карты правильно, так как число тасовок стремится к бесконечности.
Предположим, у вас есть три карты: {A, B, C}. Предположим, что ваши карты начинаются в следующем порядке: A, B, C. Затем после одного шаффла у вас есть следующие комбинации:
Следовательно, вероятность того, что карточка A окажется в позиции {1,2,3}, равна {5/9, 2/9, 2/9}.
Если мы перетасуем карты во второй раз, то:
Это дает 0,407.
Используя ту же идею, мы можем сформировать рекуррентные отношения, то есть:
Кодирование этого в R (см. Код ниже) дает вероятность того, что карта A окажется в позиции {1,2,3} как {0.33334, 0.33333, 0.33333} после десяти перемешиваний.
Код R
источник
Сколько вам нужно, чтобы хорошо аппроксимировать случайную перестановку? Генерация случайной перестановки путем случайных транспозиций была проанализирована Диаконисом и Шахшахани с использованием теории представлений симметрической группы в
Дьяконис П., Шахшахани М. (1981): «Генерация случайной перестановки со случайными транспозициями». З. Варш. Verw. Geb. 57, 159–179.
источник
Имейте в виду, я не статистик, но я поставлю свои 2цента.
Я сделал небольшой тест в R (осторожно, он очень медленный для высокого уровня
numTrials
, код, вероятно, можно оптимизировать):Это сгенерирует матрицу
swaps
соnumTrials+1
строками (по одной на пробу + оригинал) иnumElements
столбцами (по одной на каждый элемент вектора). Если метод верен, распределение каждого столбца (т. Е. Значений для каждого элемента в ходе испытаний) не должно отличаться от распределения исходных данных.Поскольку наши исходные данные были нормально распределены, мы ожидаем, что все столбцы не отклонятся от этого.
Если мы бежим
Мы получаем:
что выглядит очень многообещающе. Теперь, если мы хотим статистически подтвердить, что распределения не отклоняются от оригинала, я думаю, что мы могли бы использовать тест Колмогорова-Смирнова (пожалуйста, может ли какой-то статистик подтвердить, что это правильно?) И сделать, например,
Что дает нам р = 0,9926
Если мы проверим все столбцы:
И мы бежим
мы получаем:
Таким образом, для подавляющего большинства элементов массива ваш метод обмена дал хороший результат, как вы также можете видеть, глядя на квартили.
Обратите внимание, что, очевидно, с меньшим количеством испытаний ситуация не так хороша:
50 испытаний
100 испытаний
500 испытаний
источник
Вот как я интерпретирую ваш алгоритм в псевдокоде:
источник