почему этот простой алгоритм перестановки приводит к смещенным результатам? что такое простая причина?
Песочница вашего скрипта - это только страница, на которой он выполняется. Как только вы будете перенаправлены на google.com, ваш скрипт станет недействительным. Единственный вариант - получить страницу через AJAX и запустить функцию обратного вызова, которая будет выполняться при загрузке контента.
10 ответов
Вот полное дерево вероятностей для этих замен.
Предположим, вы начнете с последовательности 123, а затем мы перечислим все различные способы получения случайных результатов с помощью кода в вопрос.
123
+- 123 - swap 1 and 1 (these are positions,
| +- 213 - swap 2 and 1 not numbers)
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 123 - swap 2 and 2
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 132 - swap 2 and 3
| +- 231 - swap 3 and 1
| +- 123 - swap 3 and 2
| +- 132 - swap 3 and 3
+- 213 - swap 1 and 2
| +- 123 - swap 2 and 1
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 213 - swap 2 and 2
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 231 - swap 2 and 3
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 1 and 3
+- 231 - swap 2 and 1
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 2 and 2
| +- 123 - swap 3 and 1
| +- 312 - swap 3 and 2
| +- 321 - swap 3 and 3
+- 312 - swap 2 and 3
+- 213 - swap 3 and 1
+- 321 - swap 3 and 2
+- 312 - swap 3 and 3
Теперь четвертый столбец чисел, предшествующий информации обмена, содержит окончательный результат с 27 возможными результатами.
Давайте посчитаем, сколько раз встречается каждый шаблон:
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
27 times total
Если вы запустите код которые меняются случайным образом бесконечное количество раз, шаблоны 132, 213 и 231 будут встречаться чаще, чем шаблоны 123, 312 и 321, просто потому, что способ замены кода делает это более вероятным.
Теперь конечно, вы можете сказать, что если вы запустите код 30 раз (27 + 3), вы можете получить все шаблоны, встречающиеся 5 раз,но при работе со статистикой вы должны смотреть на долгосрочную тенденцию.
Вот код C #, который исследует случайность для каждого из возможных шаблонов:
class Program
{
static void Main(string[] args)
{
Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
{
{ "123", 0 },
{ "132", 0 },
{ "213", 0 },
{ "231", 0 },
{ "312", 0 },
{ "321", 0 }
};
Char[] digits = new[] { '1', '2', '3' };
Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
{
Char[] result = new Char[] { input[0], input[1], input[2] };
Char temp = result[pos1];
result[pos1] = result[pos2];
result[pos2] = temp;
return result;
};
for (Int32 index1 = 0; index1 < 3; index1++)
{
Char[] level1 = swap(digits, 0, index1);
for (Int32 index2 = 0; index2 < 3; index2++)
{
Char[] level2 = swap(level1, 1, index2);
for (Int32 index3 = 0; index3 < 3; index3++)
{
Char[] level3 = swap(level2, 2, index3);
String output = new String(level3);
occurances[output]++;
}
}
}
foreach (var kvp in occurances)
{
Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
}
}
}
Это выводит:
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
Итак, хотя этот ответ действительно учитывается, это не чисто математический ответ, вам просто нужно оценить все возможные пути случайной функции и посмотреть на окончательные результаты.
Из ваших комментариев к другим ответам кажется, что вы ищете не только объяснение того, почему распределение не является равномерным распределением (для которого ответ делимости является простым), но также дает «интуитивное» объяснение того, почему он на самом деле далек от единообразия .
Вот один из способов взглянуть на это. Предположим, вы начинаете с исходного массива [1, 2, ..., n] (где n может быть 3, 52 или что-то еще) и применяете один из двух алгоритмов. Если все перестановки равномерно вероятны, то вероятность того, что 1 останется на первой позиции, должна быть 1 / n . И действительно, во втором (правильном) алгоритме оно равно 1 / n , так как 1 остается на своем месте тогда и только тогда, когда он не заменяется в первый раз, т.е.
Однако в первом (неправильном) алгоритме 1 остается нетронутым, только если он ни не поменялся местами в первый раз , ни в любой другой раз, то есть только если первый rand возвращает 0, а none из других rand возвращает 0, вероятность которого равна (1 / n) * (1-1 / n) ^ (n-1) ≈ 1 / (ne) ≈ 0,37 / n, а не 1 / n.
И это «интуитивное» объяснение: в вашем первом алгоритме более ранние элементы с гораздо большей вероятностью будут заменены не на своем месте, чем более поздние элементы, поэтому перестановки, которые вы получаете, смещены в сторону паттернов, в которых ранние элементы находятся , а не на своих исходных местах.
(Это немного более тонко, чем это, например, 1 может быть заменен на более позднюю позицию и все равно окажется возвращение на место с помощью сложной серии обменов,но эти вероятности относительно менее значительны.)
См. Это:
Опасность наивности (кодирование ужаса)
Давайте в качестве примера рассмотрим вашу колоду из трех карт. При использовании колоды из трех карт после перемешивания имеется только 6 возможных порядков для колоды: 123, 132, 213, 231, 312, 321.
В вашем 1-м алгоритме существует 27 возможных путей (исходов) для код в зависимости от результатов выполнения функции rand () в разных точках. Каждый из этих исходов одинаково вероятен (беспристрастен). Каждый из этих результатов будет соответствовать одному и тому же результату из приведенного выше списка из 6 возможных «реальных» результатов перемешивания. Теперь у нас есть 27 предметов и 6 ведер, в которые их нужно положить. Поскольку 27 не делится на 6 без остатка, некоторые из этих 6 комбинаций должны быть перепредставлены.
Во втором алгоритме есть 6 возможных результатов, которые точно соответствуют 6 возможным «реальным» результатам перемешивания, и все они должны быть представлены в равной степени. времени.
Это важно, потому что сегменты, которые перепредставлены в первом алгоритме, не случайны. Наборы, выбранные для смещения, являются повторяемыми и предсказуемыми. Итак, если вы создаете онлайн-игру в покер и используете 1-й алгоритм, хакер может выяснить, что вы использовали наивную сортировку, и, исходя из этого, сделать вывод, что определенные расстановки колод гораздо более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.
У второго алгоритма есть 6 возможных результатов, которые точно соответствуют 6 возможным «реальным» результатам перемешивания, и все они должны быть представлены одинаково с течением времени.
Это важно, потому что сегменты, которые чрезмерно представлены в Первый алгоритм не случайный. Наборы, выбранные для смещения, являются повторяемыми и предсказуемыми. Итак, если вы создаете онлайн-игру в покер и используете 1-й алгоритм, хакер может выяснить, что вы использовали наивную сортировку, и, исходя из этого, сделать вывод, что определенные расстановки колод гораздо более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.
У второго алгоритма есть 6 возможных результатов, которые точно соответствуют 6 возможным «реальным» результатам перемешивания, и все они должны быть представлены одинаково с течением времени.
Это важно, потому что сегменты, которые чрезмерно представлены в Первый алгоритм не случайный. Наборы, выбранные для смещения, являются повторяемыми и предсказуемыми. Итак, если вы создаете онлайн-игру в покер и используете 1-й алгоритм, хакер может выяснить, что вы использовали наивную сортировку, и, исходя из этого, сделать вывод, что определенные расстановки колод гораздо более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.
и все они должны быть представлены одинаково во времени.Это важно, потому что сегменты, которые перепредставлены в первом алгоритме, не являются случайными. Наборы, выбранные для смещения, являются повторяемыми и предсказуемыми. Итак, если вы создаете онлайн-игру в покер и используете 1-й алгоритм, хакер может выяснить, что вы использовали наивную сортировку, и, исходя из этого, сделать вывод, что определенные расстановки колод гораздо более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.
и все они должны быть представлены одинаково во времени.Это важно, потому что сегменты, которые перепредставлены в первом алгоритме, не являются случайными. Наборы, выбранные для смещения, являются повторяемыми и предсказуемыми. Итак, если вы создаете онлайн-игру в покер и используете 1-й алгоритм, хакер может выяснить, что вы использовали наивную сортировку, и, исходя из этого, сделать вывод, что определенные расстановки колод гораздо более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.
воссоздавая онлайн-покер и используя первый алгоритм, хакер мог бы выяснить, что вы использовали наивный вид, и из этого выяснил, что определенные расстановки колоды более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса. воссоздавая онлайн-покер и используя первый алгоритм, хакер мог бы выяснить, что вы использовали наивный вид, и из этого выяснил, что определенные расстановки колоды более вероятны, чем другие. Затем они могут делать соответствующие ставки. Некоторые они проиграют, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.Лучшее объяснение, которое я видел для этого эффекта, было от Джеффа Этвуда в его блоге CodingHorror ( Опасность Наивет ).
Используя этот код для имитации случайного перемешивания с 3 картами ...
for (int i = 0; i < cards.Length; i++)
{
int n = rand.Next(cards.Length);
Swap(ref cards[i], ref cards[n]);
}
... вы получите это распределение.
Код перемешивания (выше) дает 3 ^ 3 (27) возможных комбинаций колод. Но математика говорит нам, что на самом деле их всего 3! или 6 возможных комбинаций колоды из 3 карт. Таким образом, некоторые комбинации представлены чрезмерно.
Вам нужно будет использовать тасование Фишера-Йейтса , чтобы правильно (случайным образом) перемешать колоду карт.
Вот еще одна интуиция: единичный случайный обмен не может создать симметрия в вероятности занятия позиции, если уже не существует хотя бы двухсторонняя симметрия. Назовите три позиции A, B и C. Теперь пусть a будет вероятностью того, что карта 2 окажется в позиции A, b будет вероятностью того, что карта 2 окажется в позиции B, и c будет вероятностью того, что она окажется в позиции C, до к своп-ходу. Предположим, что нет двух одинаковых вероятностей: a! = B, b! = C, c! = A. Теперь вычислите вероятности a ', b' и c 'того, что карта окажется в этих трех положениях после обмена. Предположим, что этот ход состоит из случайной замены позиции C одной из трех позиций. Тогда:
a' = a*2/3 + c*1/3
b' = b*2/3 + c*1/3
c' = 1/3.
То есть, вероятность того, что карта окажется в позиции A, - это вероятность, что она уже была там, умноженная на 2/3 времени, когда позиция A не участвует в обмене, плюс вероятность того, что она была в позиции C, умноженная на вероятность 1/3 что C поменял местами с A и т. д. Теперь вычитая первые два уравнения, мы получаем:
a' - b' = (a - b)*2/3
, что означает, что, поскольку мы предположили, что a! = b, тогда a '! = b' (хотя разница со временем приблизится к 0, учитывая достаточно свопов). Но поскольку a '+ b' + c '= 1, если a'! = B ', то ни один из них не может быть равен c', что равно 1/3. Таким образом, если все три вероятности начинаются по-разному до обмена, они также будут разными после обмена. И это будет сохраняться независимо от того, какая позиция была поменяна местами - мы просто меняем ролями переменных в приведенном выше.
Теперь самый первый обмен начался с обмена карты 1 в позиции A с одной из других. В этом случае перед обменом существовала двухсторонняя симметрия, потому что вероятность того, что карта 1 окажется в позиции B = вероятность того, что карта 1 окажется в позиции C = 0. Фактически, карта 1 может закончиться с симметричными вероятностями, и она действительно закончится. в каждой из трех позиций с равной вероятностью. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), и аналогично карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3). , Таким образом, независимо от того, сколько последующих обменов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занятия всех трех позиций.
потому что вероятность того, что карта 1 окажется в позиции B = вероятность того, что карта 1 окажется в позиции C = 0. Фактически, карта 1 может закончиться с симметричными вероятностями, и она действительно окажется в каждой из трех позиций с равной вероятностью. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), и аналогично карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3). , Таким образом, независимо от того, сколько последующих обменов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занятия всех трех позиций. потому что вероятность того, что карта 1 окажется в позиции B = вероятность того, что карта 1 окажется в позиции C = 0. Фактически, карта 1 может закончиться с симметричными вероятностями, и она действительно окажется в каждой из трех позиций с равной вероятностью. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), и аналогично карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3). , Таким образом, независимо от того, сколько последующих обменов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занятия всех трех позиций. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), и аналогично карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3). , Таким образом, независимо от того, сколько последующих обменов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занятия всех трех позиций. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), и аналогично карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3). , Таким образом, независимо от того, сколько последующих обменов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занятия всех трех позиций.Простой ответ заключается в том, что существует 52 ^ 52 возможных способа выполнения этого алгоритма, но их всего 52! возможные аранжировки 52 карт. Чтобы алгоритм был справедливым, он должен обеспечивать одинаковую вероятность каждой из этих схем. 52 ^ 52 не является целым числом, кратным 52 !. Следовательно, одни договоренности должны быть более вероятными, чем другие.
См. Сообщение Coding Horror Опасность наивности .
В основном (накладывая 3 карты):
Наивное перемешивание приводит к 33 (27) возможные комбинации колод. Это странно, потому что математика говорит нам что реально всего 3! или 6 возможные комбинации из 3 карт колода. В случайном порядке KFY мы начинаем с первоначальным заказом, своп с третья позиция с любым из трех карты, затем снова поменяйте местами со второй положение с оставшимися двумя картами.
иллюстративный подход может быть следующим:
1) рассматривать только 3 карты.
2) чтобы алгоритм давал равномерно распределенные результаты, вероятность того, что «1» закончится как a [0] должно быть 1/3, и вероятность того, что «2» попадет в [1], также должна быть 1/3 и т. д.
3) поэтому, если мы посмотрим на второй алгоритм:
вероятность того, что «1» окажется на [0]: когда 0 - сгенерированное случайное число, так что 1 случай из (0,1,2), следовательно, это 1 из 3 = 1/3
вероятности того, что «2» окажется в [1]: когда он не был заменен на [0] первый раз, и его не поменяли местами to a [2] второй раз: 2/3 * 1/2 = 1/3
вероятности того, что "3" окажется на [2]: когда он не был заменен на [0] первый раз, и его не поменяли местами к [1] второй раз: 2/3 * 1/2 = 1/3
они все идеально 1/3, и мы не вижу здесь никаких ошибок.
4) если мы попытаемся вычислить вероятность того, что «1» закончится как [0] в первом алгоритме, расчет будет немного длинным, но, как показано на иллюстрации в Ответ lassevk показывает, что это 9/27 = 1/3, но у «2», заканчивающегося как [1], есть шанс 8/27, а у «3», заканчивающегося как [2], есть шанс 9 / 27 = 1/3.
в результате, «2», заканчивающееся как [1], не равно 1/3, и поэтому алгоритм выдаст довольно искаженный результат (ошибка около 3,7%, в отличие от любого незначительного случая, такого как как 3/10000000000000 = 0,00000000003%)
5) доказательство, которое есть у Джоэла Кохорна, на самом деле может доказать, что некоторые случаи будут перепредставлены. Я думаю, что объяснение того, почему это n ^ n, таково: на каждой итерации существует n вероятность того, что случайное число может быть, поэтому после n итераций может быть n ^ n случаев = 27. Это число не делит количество перестановок (n! = 3! = 6) поровну в случае n = 3, поэтому некоторые результаты представлены чрезмерно. они перепредставлены таким образом, что вместо того, чтобы показываться 4 раза, они появляются 5 раз, поэтому, если вы перетасовываете карты миллионы раз от начального порядка от 1 до 52, перепредставленный случай покажет 5 миллионов раз по сравнению с 4 миллионами раз, что довольно большая разница.
6) Я думаю, что избыточное представление показано, но «почему» произойдет избыточное представление?
7) окончательный тест на правильность алгоритма состоит в том, что любое число имеет вероятность 1 / n в конечном итоге в любом месте.
они перепредставлены таким образом, что вместо того, чтобы показываться 4 раза, они появляются 5 раз, поэтому, если вы перетасовываете карты миллионы раз от начального порядка от 1 до 52, перепредставленный случай покажет 5 миллионов раз по сравнению с 4 миллионами раз, что довольно большая разница.6) Я думаю, что избыточное представление показано, но «почему» произойдет избыточное представление?
7) окончательный тест на правильность алгоритма состоит в том, что любое число имеет вероятность 1 / n в конечном итоге в любом месте.
они перепредставлены таким образом, что вместо того, чтобы показываться 4 раза, они появляются 5 раз, поэтому, если вы перетасовываете карты миллионы раз от начального порядка от 1 до 52, перепредставленный случай покажет 5 миллионов раз по сравнению с 4 миллионами раз, что довольно большая разница.6) Я думаю, что избыточное представление показано, но «почему» произойдет избыточное представление?
7) окончательный тест на правильность алгоритма состоит в том, что любое число имеет вероятность 1 / n в конечном итоге в любом месте.
Вот отличный анализ карты тасования цепей Маркова . Ой, подождите, это все математика. Сожалею. :)
Наивный алгоритм выбирает значения n следующим образом:
n = rand (3)
n = rand (3)
n = rand (3)
3 ^ 3 возможных комбинации n
1,1,1, 1,1,2 .... 3,3,2 3,3,3 (27 комбинаций) Ответ lassevk показывает распределение между картами этих комбинации.
лучший алгоритм делает:
n = rand (3)
n = rand (2)
n! возможные комбинации n
1,1, 1,2, 2,1 2,2 3,1 3,2 (6 комбинаций, все из которых дают разный результат)
Как упоминалось в других ответах, если вы делаете 27 попыток, чтобы получить 6 результатов, вы не можете достичь 6 результатов при равном распределении, поскольку 27 не делятся на 6. Положите 27 шариков в 6 ведер, и независимо от того, что вы делаете, в одних ведрах будет больше шариков, чем в других, Лучшее, что вы можете сделать, это 4,4,4,5,5,5 шарика для ведер с 1 по 6.
фундаментальная проблема с наивным перемешиванием заключается в том, что слишком много мест меняются местами, чтобы полностью перемешать 3 карты, вам нужно сделать только 2 обмена, а второй обмен должен быть только среди первых двух карт, так как третья карта уже имела 1/3 шанс быть замененным. Продолжение обмена картами даст больше шансов на то, что данная карта будет заменена, и эти шансы сравняются только до 1/3, 1/3, 1/3, если ваши общие комбинации обмена делятся на 6.