Какое распределение вы получите в результате этого разбитого случайного перемешивания?

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

Реализуем ошибочный алгоритм в системе 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})

Изменить

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

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

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

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

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

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

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

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

Скажем

• 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 с единицами в i-м столбце и i-й строке, нули везде, например:

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

• _i - это

Потом,

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

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

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

Шаблон одинаков для всех N> 2:

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

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

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

Как вы, возможно, уже догадались, основываясь на ответе @belisarius, точное распределение сильно зависит от количества элементов, которые нужно перетасовать. Вот сюжет Этвуда для колоды из 6 элементов:

Какой прекрасный вопрос! Хотел бы я получить полный ответ.

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

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

Мы знаем, что элемент на последнем месте с одинаковой вероятностью изначально был где угодно, потому что последний проход меняет местами последнее место с равной вероятностью с любым другим. Точно так же первый элемент с одинаковой вероятностью будет размещен где угодно. Эта симметрия возникает из-за того, что транспонирование меняет порядок умножения матриц на противоположный. Фактически, матрица симметрична в том смысле, что строка i совпадает с столбцом (n + 1 - i). Помимо этого, цифры не показывают явной закономерности. Эти точные решения действительно показывают согласие с моделированием, проведенным Велизарием: в слоте i вероятность получения j уменьшается по мере увеличения j до i, достигая минимального значения в i-1, а затем перепрыгивая до самого высокого значения в i, и убывает, пока 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 - полезный инструмент визуализации.

Редактировать (Велизарий)

Просто подтверждение. Следующий код дает ту же матрицу, что и в ответе @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}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

На странице Википедии о перемешивании Фишера-Йейтса есть описание и пример того, что именно будет случиться в таком случае.

Распределение можно вычислить с помощью стохастических матриц. Пусть матрица A (i, j) описывает вероятность того, что карта, первоначально находившаяся в позиции i, окажется в позиции 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 выше! ой ...

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

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

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

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

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

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

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

Эта матричная диаграмма с использованием неравномерного и очень предвзятого перемешивания создается с использованием наивной замены (мы выбираем от «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 ];
    }
}