Страница Википедии на случайной случайности Фишера-Йейтса содержит описание и пример того, что именно произойдет в этом случае.

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

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

Мы можем проанализировать это так же, как цепочку Маркова, описав действия как стохастические матрицы переходов, действующие линейно на вероятностных распределениях. Большинство элементов остаются в покое, диагональ обычно (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

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

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

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

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

Если в массиве есть повторяющиеся записи, то проблема немного в другом. Как бесстыдная заглушка, эта более общая проблема решена мной, Diaconis и Soundararajan в Приложении B « Правила большого пальца» для Riffle Shuffling (2011) .

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

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

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

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

Скажем

• a = 1/N
• b = 1-a
• B _i (k) - матрица вероятностей после iперестановок для kэлемента th. т.е. ответ на вопрос «где 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:

• А _я есть

Затем,

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

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

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

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

• Наиболее вероятное положение концовки для к-го элемента к-1 .
• Наименее вероятная позиция окончания равна к для к , положение 1 в противном случае