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

algorithm language-agnostic math random shuffle

6009 просмотра

10 ответа

Известный алгоритм тасования Фишера-Йейтса может быть использован для случайной перестановки массива 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.

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

Автор: templatetypedef Источник Размещён: 12.11.2019 09:58

Ответы (10)


55 плюса

Решение

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

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

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

Автор: Dr. belisarius Размещён: 27.02.2011 04:27

28 плюса

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

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

Автор: PengOne Размещён: 16.03.2011 02:35

15 плюса

Скажем

  • a = 1/N
  • b = 1-a
  • B i (k) - матрица вероятностей после iперестановок для kэлемента th. т.е. ответ на вопрос «где kпосле iсвопов?». Например, B 0 (3) = (0 0 1 0 ... 0)и B 1 (3) = (a 0 b 0 ... 0). То, что вы хотите, это B N (k) для каждого k.
  • K i представляет собой матрицу NxN с единицами в i-м столбце и i-й строке, нулями везде, например:

kappa_2

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

I_2

  • А я есть

Ai = bIi + aKi

Затем,

B_n

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

матрица решений

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

B_4

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

B_500

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

  • Наиболее вероятное положение концовки для к-го элемента к-1 .
  • Наименее вероятная позиция окончания равна к для к , положение 1 в противном случае
Автор: Eelvex Размещён: 22.03.2011 12:07

13 плюса

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

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

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

введите описание изображения здесь

Автор: oosterwal Размещён: 15.03.2011 10:32

8 плюса

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

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

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

3 плюса

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

Автор: Jeremiah Willcock Размещён: 27.02.2011 03:55

3 плюса

Вы можете вычислить распределение, используя стохастические матрицы . Пусть матрица 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 выше! упс ...

Автор: daoudc Размещён: 18.03.2011 09:25

3 плюса

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

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

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

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

Автор: PengOne Размещён: 23.09.2011 01:39

2 плюса

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

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 ];
    }
}
Автор: Mac Размещён: 21.10.2015 12:30

1 плюс

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

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

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

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

Автор: Matt Размещён: 09.03.2015 07:22
Вопросы из категории :
32x32