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

Question

Известный алгоритм тасования Фишера-Йейтса может использоваться для случайной перестановки массива A длиной N:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

Типичная ошибка, которую мне снова и снова говорили не совершать, заключается в следующем:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

То есть вместо выбора случайного целого числа от k до N, вы выбираете случайное целое число от 1 до N.

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

Answer 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})

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

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

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

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

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

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

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

Answer 2

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

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

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

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

• A _i равно

Тогда

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

В 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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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 ];
    }
}

Answer 10

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

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

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

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