Что не так с этим «наивным» алгоритмом тасования?

23

Это продолжение вопроса Stackoverflow о случайном перемешивании массива .

Существуют установленные алгоритмы (такие как Кнут-Фишер-Йейтс Шуффл ), которые следует использовать для перемешивания массива, а не полагаться на «наивные» специальные реализации.

Теперь я заинтересован в том, чтобы доказать (или опровергнуть), что мой наивный алгоритм нарушен (как в: не генерирует все возможные перестановки с равной вероятностью).

Вот алгоритм:

Зациклите пару раз (длина массива должна соответствовать), и в каждой итерации получите два индекса случайных массивов и поменяйте местами два элемента.

Очевидно, что для этого нужно больше случайных чисел, чем KFY (вдвое больше), но кроме этого он работает правильно? И какое будет соответствующее количество итераций (достаточно ли «длины массива»)?

Тило
источник
4
Я просто не могу понять, почему люди думают, что этот обмен «проще» или «более наивен», чем FY ... Когда я впервые решил эту проблему, я только что реализовал FY (не зная, что у него даже есть имя) Просто потому, что мне показалось, что это самый простой способ сделать это.
1
@mbq: лично я нахожу их одинаково легкими, хотя я согласен, что FY кажется мне более "естественным".
Нико
3
Когда я исследовал алгоритмы тасования после того, как написал свой собственный (практика, от которой я отказался), я был полностью «святым дерьмом, это было сделано, и у него есть имя !!»
JM не является статистиком

Ответы:

12

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

Просто чтобы понять, что происходит, рассмотрим, как часто ваш алгоритм будет генерировать тасования из массива элементов, в котором фиксирован первый элемент, . Когда перестановки генерируются с равной вероятностью, это должно происходить времени. Пусть будет относительной частотой этого вхождения после перемешиваний с вашим алгоритмом. Давайте также будем щедрыми и предположим, что вы на самом деле выбираете разные пары индексов случайным образом для ваших случайных комбинаций, так что каждая пара выбирается с вероятностью =k 2 1 / k p n n 1 / ( kkk21/kpnn 2/(k(k-1))1/(k2)2/(k(k1)), (Это означает, что «тривиальные» тасования не расходуются впустую. С другой стороны, это полностью нарушает ваш алгоритм для двухэлементного массива, потому что вы чередуетесь между фиксацией двух элементов и их заменой, поэтому, если вы остановитесь после заранее определенного числа шагов, нет никакой случайности с результатом!)

Эта частота удовлетворяет простой повторяемости, потому что первый элемент находится на своем первоначальном месте после тасует двумя непересекающимися способами. Во-первых, это было исправлено после перемешиваний, а следующее перемешивание не перемещает первый элемент. Другое дело, что он был перемещен после перемешиваний, но перемешивает его назад. Вероятность не сдвинуть первый элемент равна = , тогда как вероятность переместить первый элемент назад равна = . Откуда:n n n + 1 s t ( k - 1n+1nnn+1st (k-2)/k1/ ( k(k12)/(k2)(k2)/k 2/(k(k-1))1/(k2)2/(k(k1))

p0=1
потому что первый элемент начинается на своем законном месте;

pn+1=k2kpn+2k(k1)(1pn).

Решение

pn=1/k+(k3k1)nk1k.

Вычитая , мы видим, что частота неверна для . Для больших и хорошим приближением является . Это показывает, что ошибка на этой конкретной частоте будет уменьшаться экспоненциально с числом свопов относительно размера массива ( ), указывая на то, что будет трудно обнаружить большие массивы, если вы сделали относительно большое количество свопов - но ошибка всегда есть.( к - 31/k knk-1(k3k1)nk1kknн/кk1kexp(2nk1)n/k

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

n>12(1(k1)log(ϵ))

где должен быть очень маленьким по сравнению с . Это означает должно быть в несколько раз для четных грубых приближений ( т.е. , где на порядка раз или так.)1 / k n k ϵ 0,01 1 / kϵ1/knkϵ0.011/k

Все это порождает вопрос: почему вы решили использовать алгоритм, который не совсем (но только приблизительно) корректен, использует те же методы, что и другой алгоритм, который доказуемо корректен и все же требует больше вычислений?

редактировать

Комментарий Тило уместен (и я надеялся, что никто не будет указывать на это, поэтому я мог бы избавиться от этой дополнительной работы!). Позвольте мне объяснить логику.

  • Если вы уверены, что генерируете реальные свопы каждый раз, вы совершенно облажались. Проблема, которую я указал для случая распространяется на все массивы. Только половина всех возможных перестановок может быть получена путем применения четного числа перестановок; другая половина получается путем применения нечетного числа свопов. Таким образом, в этой ситуации вы никогда не сможете сгенерировать где-либо около равномерного распределения перестановок (но существует так много возможных, что исследование моделирования для любого значительного не сможет обнаружить проблему). Это действительно плохо.кk=2k

  • Поэтому целесообразно генерировать подстановки случайным образом, независимо генерируя две позиции. Это означает, что есть шанс каждый раз менять элемент на себя; то есть ничего не делать. Этот процесс эффективно замедляет алгоритм немного: после шагов мы ожидаем, что произошло только истинных перестановок.n k - 11/knk1kN<N

  • Обратите внимание, что размер ошибки монотонно уменьшается с увеличением числа различных перестановок. Поэтому проведение меньшего количества свопов в среднем также увеличивает ошибку в среднем. Но это цена, которую вы должны быть готовы заплатить, чтобы преодолеть проблему, описанную в первом пункте. Следовательно, моя оценка ошибки консервативно низкая, примерно в .(k1)/k

Я также хотел бы отметить интересное очевидное исключение: внимательный взгляд на формулу ошибки показывает, что в случае ошибки нет . Это не ошибка: это правильно. Однако здесь я рассмотрел только одну статистику, связанную с равномерным распределением перестановок. Тот факт, что алгоритм может воспроизвести эту статистику, когда (а именно получить правильную частоту перестановок, которые фиксируют любую заданную позицию), не гарантирует, что перестановки действительно были распределены равномерно. Действительно, после фактических перестановок единственные возможные перестановки, которые могут быть сгенерированы: ,k = 3 2 n ( 123 ) ( 321 ) 2 n + 1 ( 12 ) ( 23 ) ( 13 )k=3k=32n(123)(321)и личность. Только последний фиксирует любую данную позицию, так что в действительности ровно треть перестановок фиксирует позицию. Но половина перестановок отсутствует! В другом случае после фактических перестановок единственными возможными перестановками являются , и . Опять же, точно один из них будет фиксировать любую данную позицию, поэтому мы снова получаем правильную частоту перестановок, фиксирующих эту позицию, но снова мы получаем только половину возможных перестановок.2n+1(12)(23)(13)

Этот небольшой пример помогает раскрыть основные аргументы аргумента: будучи «щедрым», мы консервативно недооцениваем частоту ошибок для одной конкретной статистики. Поскольку эта частота ошибок отлична от нуля для всех , мы видим, что алгоритм не работает. Кроме того, анализируя затухание частоты ошибок для этой статистики, мы устанавливаем нижнюю границу для числа итераций алгоритма, необходимого, чтобы иметь хоть какую-то надежду на аппроксимацию равномерного распределения перестановок.k4

Whuber
источник
1
«Давайте тоже будем щедрыми и предположим, что вы фактически выбираете разные пары индексов для случайных случайных чисел». Я не понимаю, почему такое предположение можно сделать и как оно щедрое. Кажется, он отбрасывает возможные перестановки, что приводит к еще меньшему случайному распределению.
Тило
1
@Thilo: Спасибо. Ваш комментарий заслуживает расширенного ответа, поэтому я разместил его в самом ответе. Позвольте мне указать здесь, что «щедрый» на самом деле не отбрасывает никаких перестановок: он просто исключает шаги в алгоритме, которые в противном случае ничего бы не делали.
whuber
2
Эта проблема может быть полностью проанализирована как цепь Маркова на графе Кэли группы перестановок. Численные расчеты для k = 1–7 (матрица 5040 на 5040!) Подтверждают, что наибольшие собственные значения в размерах (после 1 и -1) точно . Это означает, что, как только вы справитесь с проблемой чередования знака перестановки (соответствующей собственному значению -1), ошибки во всех вероятностях затухают со скоростью или Быстрее. Я подозреваю, что это продолжается для всех больших . ( 1 - 2 / ( k - 1 ) ) n k(k3)/(k1)=12/(k1)(12/(k1))nk
whuber
1
Вы можете сделать намного лучше, чем так как вероятности являются инвариантными для классов сопряженности, и существует только секций из поэтому вы можете вместо этого проанализировать матрицу . 15 7 15 × 155040×504015715×15
Дуглас Заре
8

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

Предположим, у вас есть три карты: {A, B, C}. Предположим, что ваши карты начинаются в следующем порядке: A, B, C. Затем после одного шаффла у вас есть следующие комбинации:

{A,B,C}, {A,B,C}, {A,B,C} #You get this if choose the same RN twice.
{A,C,B}, {A,C,B}
{C,B,A}, {C,B,A}
{B,A,C}, {B,A,C}

Следовательно, вероятность того, что карточка A окажется в позиции {1,2,3}, равна {5/9, 2/9, 2/9}.

Если мы перетасуем карты во второй раз, то:

Pr(A in position 1 after 2 shuffles) = 5/9*Pr(A in position 1 after 1 shuffle) 
                                     + 2/9*Pr(A in position 2 after 1 shuffle) 
                                     + 2/9*Pr(A in position 3 after 1 shuffle) 

Это дает 0,407.

Используя ту же идею, мы можем сформировать рекуррентные отношения, то есть:

Pr(A in position 1 after n shuffles) = 5/9*Pr(A in position 1 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 2 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 3 after (n-1) shuffles).

Кодирование этого в R (см. Код ниже) дает вероятность того, что карта A окажется в позиции {1,2,3} как {0.33334, 0.33333, 0.33333} после десяти перемешиваний.

Код R

## m is the probability matrix of card position
## Row is position
## Col is card A, B, C
m = matrix(0, nrow=3, ncol=3)
m[1,1] = 1; m[2,2] = 1; m[3,3] = 1

## Transition matrix
m_trans = matrix(2/9, nrow=3, ncol=3)
m_trans[1,1] = 5/9; m_trans[2,2] = 5/9; m_trans[3,3] = 5/9

for(i in 1:10){
  old_m = m
  m[1,1] = sum(m_trans[,1]*old_m[,1])
  m[2,1] = sum(m_trans[,2]*old_m[,1])
  m[3,1] = sum(m_trans[,3]*old_m[,1])

  m[1,2] = sum(m_trans[,1]*old_m[,2])
  m[2,2] = sum(m_trans[,2]*old_m[,2])
  m[3,2] = sum(m_trans[,3]*old_m[,2])

  m[1,3] = sum(m_trans[,1]*old_m[,3])
  m[2,3] = sum(m_trans[,2]*old_m[,3])
  m[3,3] = sum(m_trans[,3]*old_m[,3])
}  
m
csgillespie
источник
1
+1. Это показывает, что вероятность того, что данная карта окажется в данной позиции, приблизительно равна ожидаемому соотношению при увеличении количества перемешиваний. Однако то же самое можно сказать и об алгоритме, который просто поворачивает массив один раз на случайную величину: все карты имеют одинаковую вероятность оказаться на всех позициях, но случайности по-прежнему нет (массив остается отсортированным).
Тило
@Thilo: Извините, я не слежу за вашим комментарием. «Алгоритм вращается на случайную величину», но все еще «нет случайности»? Не могли бы вы объяснить дальше?
csgillespie
Если вы «перемешаете» массив из N элементов, вращая его между 0 и N-1 позициями (случайным образом), то каждая карта имеет одинаковую вероятность оказаться в любой из N позиций, но 2 по-прежнему всегда находится между 1 и 3.
Тило
1
@Thio: Ах, я понял твою точку зрения. Итак, вы можете определить вероятность (используя ту же идею, что и выше) для Pr (A в положении 2) и Pr (A в положении 3) - dito для карт B и C. Вы увидите, что все вероятности имеют тенденцию 1/3. Примечание: мой ответ дает только конкретный случай, тогда как @whuber хороший ответ дает общий случай.
csgillespie
4

1/n!t A 1 / n ! = A / n 2 t n 2 t / n ! = A n 3 n n 2 t / n !A/n2tA1/n!=A/n2tn2t/n!=An3nn2t/n!не является целым числом, и нет способа равномерно разделить транспонирования наn!n=521/52!3,5,7,...,471/522tA/522t1/52!

Сколько вам нужно, чтобы хорошо аппроксимировать случайную перестановку? Генерация случайной перестановки путем случайных транспозиций была проанализирована Диаконисом и Шахшахани с использованием теории представлений симметрической группы в

Дьяконис П., Шахшахани М. (1981): «Генерация случайной перестановки со случайными транспозициями». З. Варш. Verw. Geb. 57, 159–179.

12nlogn(1ϵ)12nlogn(1+ϵ)12nlognL27

Дуглас Заре
источник
2

Имейте в виду, я не статистик, но я поставлю свои 2цента.

Я сделал небольшой тест в R (осторожно, он очень медленный для высокого уровня numTrials, код, вероятно, можно оптимизировать):

numElements <- 1000
numTrials <- 5000

swapVec <- function()
    {
    vec.swp <- vec

    for (i in 1:numElements)
        {
        i <- sample(1:numElements)
        j <- sample(1:numElements)

        tmp <- vec.swp[i]
        vec.swp[i] <- vec.swp[j]
        vec.swp[j] <- tmp
        }

    return (vec.swp)
    }

# Create a normally distributed array of numElements length
vec <- rnorm(numElements)

# Do several "swapping trials" so we can make some stats on them
swaps <- vec
prog <- txtProgressBar(0, numTrials, style=3)

for (t in 1:numTrials)
    {
    swaps <- rbind(swaps, swapVec())
    setTxtProgressBar(prog, t)
    }

Это сгенерирует матрицу swapsсо numTrials+1строками (по одной на пробу + оригинал) и numElementsстолбцами (по одной на каждый элемент вектора). Если метод верен, распределение каждого столбца (т. Е. Значений для каждого элемента в ходе испытаний) не должно отличаться от распределения исходных данных.

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

Если мы бежим

par(mfrow= c(2,2))
# Our original data
hist(swaps[1,], 100, col="black", freq=FALSE, main="Original")
# Three "randomly" chosen columns
hist(swaps[,1], 100, col="black", freq=FALSE, main="Trial # 1") 
hist(swaps[,257], 100, col="black", freq=FALSE, main="Trial # 257")
hist(swaps[,844], 100, col="black", freq=FALSE, main="Trial # 844")

Мы получаем:

Гистограммы случайных испытаний

что выглядит очень многообещающе. Теперь, если мы хотим статистически подтвердить, что распределения не отклоняются от оригинала, я думаю, что мы могли бы использовать тест Колмогорова-Смирнова (пожалуйста, может ли какой-то статистик подтвердить, что это правильно?) И сделать, например,

ks.test(swaps[1, ], swaps[, 234])

Что дает нам р = 0,9926

Если мы проверим все столбцы:

ks.results <- apply(swaps, 2, function(col){ks.test(swaps[1,], col)})
p.values <- unlist(lapply(ks.results, function(x){x$p.value})

И мы бежим

hist(p.values, 100, col="black")

мы получаем:

Гистограмма критерия р Колмогорова-Смирнова

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

1> quantile(p.values)
       0%       25%       50%       75%      100% 
0.6819832 0.9963731 0.9999188 0.9999996 1.0000000

Обратите внимание, что, очевидно, с меньшим количеством испытаний ситуация не так хороша:

50 испытаний

1> quantile(p.values)
          0%          25%          50%          75%         100% 
0.0003399635 0.2920976389 0.5583204486 0.8103852744 0.9999165730

100 испытаний

          0%         25%         50%         75%        100% 
 0.001434198 0.327553996 0.596603804 0.828037097 0.999999591 

500 испытаний

         0%         25%         50%         75%        100% 
0.007834701 0.504698404 0.764231550 0.934223503 0.999995887 
Nico
источник
0

Вот как я интерпретирую ваш алгоритм в псевдокоде:

void shuffle(array, length, num_passes)
  for (pass = 0; pass < num_passes; ++pass) 
    for (n = 0; n < length; ++)
      i = random_in(0, length-1)
      j = random_in(0, lenght-1)
      swap(array[i], array[j]

2×length×num_passes[0,length1]length

length2×length×num_passes

length!length!<length2×length×num_passes

length!|length2×length×num_passes

pp<lengthplengthlength>2p|length!length2×length×num_passeslength!length2×length×num_passeslength>2

lengthp<lengthlength1length1length

lengthlength1length!length!|length!, Нетрудно показать, что каждая трасса приводит к разной перестановке, и отсюда легко увидеть, что Фишер-Йейтс генерирует каждую перестановку с равной вероятностью.

TZS
источник