Какое распределение вы получаете от этой сломанной случайной случайности?
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:2728 плюса
Упоминаемая вами «распространенная ошибка» - это случайное перемещение. Эта проблема была детально изучена Диаконисом и Шахшахани в книге « Генерация случайной перестановки со случайными транспозициями» (1981) . Они делают полный анализ времени остановки и сходимости к однородности. Если вы не можете получить ссылку на газету, пожалуйста, пришлите мне по электронной почте, и я могу переслать вам копию. Это на самом деле весело читать (как и большинство работ Перси Диакониса).
Если в массиве есть повторяющиеся записи, то проблема немного в другом. Как бесстыдная заглушка, эта более общая проблема решена мной, Diaconis и Soundararajan в Приложении B « Правила большого пальца» для Riffle Shuffling (2011) .
Автор: PengOne Размещён: 16.03.2011 02:3515 плюса
Скажем
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-й строке, нулями везде, например:
- 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 в противном случае
13 плюса
Я знал, что видел этот вопрос раньше ...
« Почему этот простой алгоритм случайного выбора приводит к искаженным результатам? В чем простая причина? » содержит много хороших ответов, особенно ссылку на блог Джеффа Этвуда о Coding Horror .
Как вы, возможно, уже догадались, основываясь на ответе @belisarius, точное распределение сильно зависит от количества элементов, которые нужно перетасовать. Вот сюжет Этвуда для колоды из 6 элементов:
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:553 плюса
Вы можете вычислить распределение, используя стохастические матрицы . Пусть матрица A (i, j) описывает вероятность того, что карта изначально находится в положении i и окажется в положении j. Тогда у k-го свопа есть матрица Ak, заданная как Ak(i,j) = 1/N
if 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:253 плюса
Я посмотрел на это дальше, и оказалось, что это распределение было подробно изучено. Причина, по которой он представляет интерес, заключается в том, что этот «сломанный» алгоритм используется (или использовался) в системе микросхем RSA.
В « Перестановке полуслучайными транспозициями» Эльчанан Моссель, Юваль Перес и Алистер Синклер изучают этот и более общий класс перемешиваний. Результат этой статьи, кажется, состоит в том, что log(n)
для получения почти случайного распределения нужны сломанные перемешивания.
В «Смещении трех псевдослучайных перемешиваний» ( Aequationes Mathematicae , 22, 1981, 268-292) Итан Болкер и Дэвид Роббинс анализируют это перемешивание и определяют, что общее расстояние вариации до однородности после одного прохода равно 1, указывая, что оно не очень случайно на всех. Они также дают асимптотические анализы.
Наконец, Лоран Салофф-Кост и Джессика Зунига нашли хорошую верхнюю границу в своих исследованиях неоднородных цепей Маркова.
Автор: PengOne Размещён: 23.09.2011 01:392 плюса
Этот вопрос требует интерактивного анализа визуальной матричной диаграммы упомянутой сломанной случайной последовательности. Такой инструмент есть на странице. Будет ли это случайным образом? - Почему случайные компараторы плохи от Майка Бостока.
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Вопросы из категории :
- algorithm Функция для создания цветовых колес
- algorithm Big O, как вы рассчитываете / приближаете это?
- algorithm Пиковое обнаружение измеренного сигнала
- algorithm Головоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника)
- language-agnostic Окончательное руководство по аутентификации на основе форм
- language-agnostic Передать по ссылке или передать по значению?
- math Как округлить результат целочисленного деления?
- math Алгоритм нахождения наибольшего простого множителя числа
- math Рассчитать расстояние между двумя точками широты и долготы? (Формула Haversine)
- random Случайное целое число в VB.NET
- random Как запросить случайную строку в SQL?
- random Как создать случайный 10-значный номер в рубине?
- random Как сгенерировать случайную буквенно-цифровую строку?
- shuffle Каков наилучший способ перетащить NSMutableArray?
- shuffle Самый эффективный способ случайной «сортировки» (перемешивания) списка целых чисел в C #
- shuffle Перемешать массив с помощью python, упорядочить порядок элементов массива с помощью python
- shuffle Правильно ли использовать метод JavaScript Array.sort () для перемешивания?