Какое распределение вы получаете от этой случайной случайной перетасовки?

Ответ 1

Эмпирический подход.

Пусть реализуется ошибочный алгоритм в Mathematica:

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

Теперь получите количество раз, когда каждое целое число находится в каждой позиции:

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

Возьмем три позиции в результирующих массивах и построим распределение частот для каждого целого в этой позиции:

Для позиции 1 распределение частоты:

Для позиции 5 (средний)

И для позиции 10 (последняя):

и здесь у вас есть распределение для всех позиций, построенных вместе:

Здесь у вас есть лучшая статистика по 8 позициям:

Некоторые наблюдения:

• Для всех позиций вероятность "1" - то же самое (1/n).
• Матрица вероятности симметрична относительно большой антидиагональной
• Итак, вероятность для любого числа в последнем положение равномерно (1/n)

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

Второе свойство можно увидеть из следующего примера матричного представления, где строки представляют собой позиции, столбцы - это номер пассажира, а цвет представляет экспериментальную вероятность:

Для матрицы 100x100:

Изменить

Просто для удовольствия я вычислил точную формулу для второго диагонального элемента (первый - 1/n). Остальное можно сделать, но это большая работа.

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

Величины, проверенные от n = 3 до 6 ({8/27, 57/256, 564/3125, 7105/46656})

Edit

Разработав немного общий явный расчет в ответе @wnoise, мы можем получить немного больше информации.

Заменяя 1/n на p [n], поэтому вычисления не оцениваются, мы получаем, например, для первой части матрицы с n = 7 (щелкните, чтобы увидеть большее изображение):

который, сравнив результаты с другими значениями n, определим некоторые известные целые последовательности в матрице:

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

Вы можете найти эти последовательности (в некоторых случаях с разными знаками) в замечательном http://oeis.org/

Решение общей проблемы сложнее, но я надеюсь, что это начало

Ответ 2

"Общая ошибка", которую вы упомянули, - это перетасовка случайными транспозициями. Эта проблема была подробно изучена Диаконисом и Шахшахани в Генерация случайной перестановки со случайными транспозициями (1981). Они проводят полный анализ времени остановки и сближения с однородностью. Если вы не можете получить ссылку на бумагу, пожалуйста, пришлите мне электронное письмо, и я могу отправить вам копию. Это действительно забавное чтение (как и большинство работ Перси Дьякони).

Если массив имеет повторяющиеся записи, проблема немного отличается. Как бесстыдный плагин, эта более общая проблема решается мной, Диаконисом и Санарараджаном в Приложении B Правило большого пальца для перетасовки риффле (2011).

Ответ 3

Скажем,

• a = 1/N
• b = 1-a
• B _i (k) - матрица вероятности после i свопов для k -го элемента. т.е. ответ на вопрос "где k после i свопов?". Например, B ₀ (3) = (0 0 1 0 ... 0) и B ₁ (3) = (a 0 b 0 ... 0). Вы хотите, чтобы B _N (k) для каждого k.
• K _i - это матрица NxN с 1s в i-м столбце и i-й строке, нуль всюду, например:

• я _i - это единичная матрица, но с нулевым элементом x = y = i. Например, для я = 2:

• A _i is

Тогда

Но поскольку B _N (k = 1..N) образует единичную матрицу, вероятность того, что любой заданный элемент я будет в конце быть в положении j, задается матричным элементом (i, j) матрицы:

Например, для N = 4:

Как диаграмма для N = 500 (уровни цвета имеют вероятность 100 *):

Рисунок одинаковый для всех N > 2:

• наиболее вероятная конечная позиция для k-го элемента - k-1.
• наименее вероятная конечная позиция равна k для k < N * ln (2), позиция 1 в противном случае

Ответ 4

Я знал, что видел этот вопрос раньше...

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

Как вы, возможно, уже догадались, на основе ответа @belisarius точное распределение сильно зависит от количества элементов, которые нужно перетасовать. Здесь график Атвуда для 6-элементной колоды:

Ответ 5

Какой прекрасный вопрос! Мне жаль, что у меня не было полного ответа.

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

Мы можем анализировать это так же, как и цепь Маркова, описывая действия как стохастические матрицы перехода, действующие линейно на распределения вероятностей. Большинство элементов остаются в покое, диагональ обычно (n-1)/n. На проходе k, когда они не остаются в одиночестве, они обмениваются элементами k (или случайным элементом, если они являются элементом k). Это 1/(n-1) в строке или столбце k. Элемент как в строке, так и в столбце k также равен 1/(n-1). Достаточно легко умножить эти матрицы вместе для k, идущих от 1 до n.

Мы знаем, что элемент в последнем месте будет в равной степени вероятен изначально, потому что последний проход заменяет последнее место одинаково вероятным с любым другим. Аналогично, первый элемент будет в равной степени размещен в любом месте. Эта симметрия заключается в том, что транспонирование меняет порядок матричного умножения. На самом деле матрица симметрична в том смысле, что строка я совпадает с столбцом (n + 1 - i). Кроме того, цифры не показывают много очевидной картины. Эти точные решения согласуются с симуляциями, выполняемыми belisarius: In slot i. Вероятность получения j уменьшается с ростом j до i, достигая самого низкого значения при i-1, а затем прыгает до самого высокого значения в я и уменьшается до тех пор, пока j не достигнет n.

В Mathematica я сгенерировал каждый шаг с помощью

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

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

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot - полезный инструмент визуализации.

Изменить (по belisarius)

Просто подтверждение. Следующий код дает ту же матрицу, что и в ответе @Eelvex:

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
[email protected][r[4, i], {i, 1, 4}] // MatrixForm

Ответ 6

На странице Wikipedia в Shuffle Fisher-Yates есть описание и пример того, что произойдет в этом случае.

Ответ 7

Вы можете вычислить распределение, используя стохастические матрицы. Пусть матрица A (i, j) описывает вероятность того, что карта первоначально в позиции я заканчивается в позиции j. Тогда k-я свопинг имеет матрицу Ak, заданную Ak(i,j) = 1/N, если i == k или j == k, (карта в позиции k может закончиться где угодно, и любая карта может оказаться в положении k с равной вероятностью), Ak(i,i) = (N - 1)/N для все i != k (каждая другая карта останется в одном месте с вероятностью (N-1)/N), а все остальные элементы равны нулю.

Результат полной перетасовки затем задается произведением матриц AN ... A1.

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

ОБНОВЛЕНИЕ: я просто заметил ответ wnoise, эквивалентный выше! упс...

Ответ 8

Я изучил это дальше, и выясняется, что это распределение изучено подробно. Причина, по которой это представляет интерес, состоит в том, что этот "сломанный" алгоритм используется (или использовался) в чип-системе RSA.

В Перемешивая полувариантные транспозиции, Эльчанан Моссел, Ювал Перес и Алистер Синклер изучают это и более общий класс тасований. Результатом этой статьи является то, что для достижения почти случайного распределения требуется log(n) сломанные перетасовки.

В смещении трех псевдослучайных тасований (Aequationses Mathematicae, 22, 1981, 268-292) Итан Болкер и Дэвид Роббинс анализируют этот случайный случай и определяют, что общее расстояние вариации до однородности после одного прохода равно 1, что указывает на то, что это не совсем случайна. Они также дают асимптотические анализы.

Наконец, Лоран Салофф-Кост и Джессика Зунига нашли хорошую верхнюю границу в изучении неоднородных цепей Маркова.

Ответ 9

Этот вопрос попросит интерактивную визуальную матричную диаграмму анализ сломанного тасования. Такой инструмент находится на странице Будет ли он перемещаться? - Почему случайные компараторы плохи Майком Бостоком.

Bostock собрал отличный инструмент, который анализирует случайные компараторы. В раскрывающемся списке на этой странице выберите наивный swap (случайный ↦ случайный), чтобы увидеть сломанный алгоритм и шаблон, который он создает.

Его страница информативна, так как позволяет видеть непосредственные эффекты, которые имеет изменение в логике при перетасованных данных. Например:

Эта матричная диаграмма с использованием неравномерного и очень смещенного тасования создается с использованием наивного свопа (мы выбираем от "1 до N" ) с таким кодом:

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

Но если мы реализуем не-смещенную перетасовку, где мы выбираем от "k до N", мы должны увидеть такую ​​диаграмму:

где распределение равномерное и создается из кода, такого как:

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

Ответ 10

Отличные ответы, которые даны до сих пор, сосредоточены на распределении, но вы также спросили "Что произойдет, если вы допустили эту ошибку?" - это то, что я еще не видел, Я объясню это:

Алгоритм Shuffle Knuth-Fisher-Yates выбирает 1 из n элементов, затем 1 из n-1 оставшихся элементов и так далее.

Вы можете реализовать его с двумя массивами a1 и a2, где вы удаляете один элемент из a1 и вставляете его в a2, но алгоритм делает это на месте (что означает, что ему нужен только один массив), как объясняется здесь (Google: "Shuffling Algorithms Fisher-Yates DataGenetics" ) очень хорошо.

Если вы не удалите элементы, они могут быть выбраны случайным образом, что приводит к необъективной случайности. Это именно то, что делает второй пример, который вы описываете. В первом примере, алгоритме Кнута-Фишера-Йейса, используется переменная курсора, работающая от k до N, которая запоминает, какие элементы уже были взяты, следовательно, избегая выбора элементов более одного раза.