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

« Почему этот простой алгоритм случайного выбора приводит к искаженным результатам? В чем простая причина? » содержит много хороших ответов, особенно ссылку на блог Джеффа Этвуда о 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/Nif 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 ];
    }
}

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

Алгоритм перемешивания Кнута-Фишера-Йейтса выбирает 1 из n элементов, затем 1 из n-1 оставшихся элементов и т. Д.

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

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