Почему этот простой алгоритм перетасовки приводит к предвзятым результатам? что является простой причиной?

кажется, что этот простой алгоритм перетасовки приведет к смещенным результатам:

# suppose $arr is filled with 1 to 52

for ($i < 0; $i < 52; $i++) { 
  $j = rand(0, 51);

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

вы можете попробовать... вместо использования 52, используйте 3 (предположим, что используются только 3 карты), и запустите его 10 000 раз и подсчитайте результаты, вы увидите, что результаты искажены по определенным шаблонам..

вопрос... что такое простое объяснение, что это произойдет?

правильное решение - использовать что-то вроде

for ($i < 0; $i < 51; $i++) {  # last card need not swap 
  $j = rand($i, 51);        # don't touch the cards that already "settled"

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

но вопрос в том, почему первый метод, казалось бы, также полностью случайный, сделает результаты предвзятыми?

Обновить 1: спасибо, если люди укажут, что для правильного воспроизведения он должен быть rand ($ i, 51).

Ответ 1

Здесь полное дерево вероятностей для этих замен.

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

Здесь код С#, который исследует случайность для одного из возможных шаблонов:

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

Выводится:

Итак, хотя этот ответ действительно подсчитывает, это не чисто математический ответ, вам просто нужно оценить все возможные способы, по которым может работать случайная функция, и посмотреть на конечные результаты.

Ответ 2

Смотрите это:
Опасность наивного (ужас кодирования)

В качестве примера рассмотрим три колоды карт. Используя 3-карточную колоду, после тасования существует только 6 возможных ордеров: 123, 132, 213, 231, 312, 321.

С вашим 1-м алгоритмом существует 27 возможных путей (исходов) для кода, в зависимости от результатов функции rand() в разных точках. Каждый из этих результатов одинаково вероятен (беспристрастен). Каждый из этих результатов будет отображен в один и тот же результат из списка из 6 возможных "реальных" результатов тасования выше. Теперь у нас есть 27 элементов и 6 ведер. Поскольку 27 не равномерно делится на 6, некоторые из этих 6 комбинаций должны быть чрезмерно представлены.

Во втором алгоритме есть 6 возможных результатов, которые точно соответствуют 6 возможным "реальным" результатам тасования, и все они должны быть представлены одинаково во времени.

Это важно, потому что ведра, которые чрезмерно представлены в первом алгоритме, не являются случайными. Ковши, выбранные для смещения, являются повторяемыми и предсказуемыми. Так что, если вы строите онлайн-покерную игру и используете первый алгоритм, хакер мог бы понять, что вы использовали наивный сорт, и из этого следует, что некоторые механизмы колоды гораздо более вероятны, чем другие. Затем они могут делать ставки соответственно. Они потеряют некоторых, но они выиграют гораздо больше, чем проиграют, и быстро выведут вас из бизнеса.

Ответ 3

Из ваших комментариев к другим ответам кажется, что вы смотрите не только на объяснение того, почему распределение не является равномерным распределением (для которого ответ на делимость является простым), но также "интуитивное" объяснение того, почему оно на самом деле далеко не единообразно.

Вот один из способов взглянуть на него. Предположим, вы начинаете с начального массива [1, 2, ..., n] (где n может быть 3, или 52 или что-то еще) и применять один из двух алгоритмов. Если все перестановки одинаково вероятны, то вероятность того, что 1 останется в первой позиции, должна быть 1/n. И действительно, во втором (правильном) алгоритме это 1/n, поскольку 1 остается на своем месте тогда и только тогда, когда он не заменяется первым, то есть, если начальный вызов rand(0,n-1) возвращает 0.
Однако в первом (неправильном) алгоритме 1 остается нетронутым только в том случае, если он не заменяется ни первым, ни другим временем - то есть, только если первый rand возвращает 0, а ни один из других rand не возвращает 0, вероятность которого равна (1/n) * (1-1/n) ^ (n-1) ≈ 1/(ne) ≈ 0,37/n, а не 1/n.

И это "интуитивное" объяснение: в вашем первом алгоритме более ранние элементы гораздо чаще меняются местами, чем более поздние, поэтому перестановки, которые вы получаете, искажены в отношении шаблонов, в которых ранние элементы не в их первоначальных местах.

(Это немного более тонкое, чем это, например, 1 можно поменять местами в более позднюю позицию и все же в конечном итоге получить замену на место с помощью сложной серии свопов, но эти вероятности относительно менее значительны.)

Ответ 4

Лучшее объяснение, которое я видел для этого эффекта, было от Джеффа Этвуда в его блоге CodingHorror (The Danger of Naïveté).

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

Вам нужно будет использовать Fisher-Yates shuffle для правильной (случайной) перетасовки колоды карт.

Ответ 5

См. сообщение Coding Horror The Danger of Naïveté.

В принципе (по 3 карты):

Наивная тасовка приводит к 33 (27) возможные комбинации колод. Это странно, потому что математика говорит нам что есть действительно только 3! или 6 возможные комбинации 3-х карточек колода. В KFY shuffle мы начинаем с начальным порядком, свопинг с третью позицию с любым из трех карт, а затем поменять местами со второго положение с оставшимися двумя картами.

Ответ 6

Здесь другая интуиция: единый обмен случайным образом не может создать симметрию вероятности занять позицию, если по крайней мере двухсторонняя симметрия уже существует. Вызовите три позиции A, B и C. Теперь пусть a - вероятность того, что карта 2 находится в положении A, b - вероятность того, что карта 2 находится в позиции B, а c - вероятность того, что она находится в положении C, ранее к свопу. Предположим, что две вероятности не совпадают: a!= B, b!= C, c!= A. Теперь вычислите вероятности a ', b' и c 'карты, находящейся в этих трех положениях после свопа. Скажем, что это изменение подкачки состоит из положения С, которое поменялось на одно из трех позиций в случайном порядке. Тогда:

a' = a*2/3 + c*1/3
b' = b*2/3 + c*1/3
c' = 1/3.

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

Ответ 7

Простой ответ заключается в том, что для этого алгоритма существует 52 ^ 52 возможных способа, но их всего 52! Возможные аранжировки 52 карт. Для того чтобы алгоритм был справедливым, он должен обеспечить одинаковое использование каждого из этих устройств. 52 ^ 52 не является целым числом, кратным 52!. Поэтому некоторые меры должны быть более вероятными, чем другие.

Ответ 8

иллюстративный подход может быть следующим:

1) рассмотрим только 3 карты.

2) для того, чтобы алгоритм дал равномерно распределенные результаты, вероятность "1" , заканчивающаяся как [0], должна быть 1/3, а вероятность "2", заканчивающаяся в [1], должна быть равна 1/3 и т.д.

3), так что если мы посмотрим на второй алгоритм:

вероятность того, что "1" окажется на уровне [0]: когда 0 - генерируемое случайное число, поэтому 1 случай из (0,1,2), следовательно, является 1 из 3 = 1/3

вероятность того, что "2" окажется на уровне [1]: когда он не был заменен на [0] первый раз, и он не был заменен к [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 случаев = 27. Это число не делит число перестановок (n!= 3!= 6) равномерно в случае n = 3, поэтому некоторые результаты переопредставляются. они перепредставлены таким образом, что вместо того, чтобы появляться в 4 раза, он появляется в 5 раз, поэтому, если вы перетасовываете карты в миллионы раз от первоначального порядка от 1 до 52, представленный случай будет отображаться на 5 миллионов раз в отличие от 4 миллионов раз, что является довольно большой разницей.

6) Я думаю, что показано над-представление, но "почему" произойдет избыточное представление?

7) окончательный тест на правильность алгоритма заключается в том, что любое число имеет вероятность 1/n в любом слоте.

Ответ 9

Здесь отличный анализ карты перетасовывающей цепи Маркова. Ой, подождите, что все математика. Сожалею.:)

Ответ 10

Алгоритм Naive выбирает значения n так:

n = rand (3)

3 ^ 3 возможных комбинаций n

1,1,1, 1,1,2.... 3,3,2 3,3,3 (27 комбинаций) lassevk answer показывает распределение среди карт этих комбинаций.

лучший алгоритм:

n = rand (3)

n = rand (2)

п! возможные комбинации 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 свопа, а второй своп должен быть только среди первых двух карт, так как 3-я карта уже имела 1/3 вероятность замены. для продолжения обмена картами будет больше шансов, что данная карта будет заменена, и эти шансы будут только равными 1/3, 1/3, 1/3, если ваши общие своп-комбинации будут делиться на 6.

Ответ 11

Не нужен еще один ответ, но я счел целесообразным попытаться точно определить, почему Фишер-Йейтс единообразен.

Если мы говорим о колоде с N элементами, то этот вопрос: как мы можем показать, что

Pr(Item i ends up in slot j) = 1/N?

Разбивая его с условными вероятностями, Pr(item i ends up at slot j) равно

Pr(item i ends up at slot j | item i was not chosen in the first j-1 draws)
* Pr(item i was not chosen in the first j-1 draws).

и оттуда он рекурсивно возвращается к первому рисунку.

Теперь вероятность того, что элемент i не был нарисован на первом рисунке, равен N-1 / N. И вероятность того, что он не был нарисован на втором розыгрыше, обусловлен тем, что он не был нарисован на первом рисунке, равен N-2 / N-1 и т.д.

Итак, мы получаем вероятность того, что элемент i не был нарисован в первом j-1 draw:

(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)

и, конечно же, мы знаем, что вероятность того, что он нарисован в раунде j условным, если не был нарисован ранее, - это просто 1 / N-j.

Обратите внимание, что в первом члене числители все отменяют последующие знаменатели (т.е. N-1 отменяет, N-2 отменяется, вплоть до N-j+1 отменяется, оставляя только N-j / N).

Таким образом, общая вероятность появления элемента i в слоте j равна:

[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N

как ожидалось.

Чтобы получить более общее представление о "простом тасовании", конкретное свойство, которое ему не хватает, называется exchangeability. Из-за "зависимости пути" от способа создания тасования (то есть, какой из 27 путей используется для создания вывода), вы не можете обрабатывать разные случайные переменные, как если бы они могли появляться в любом порядке, На самом деле, это, пожалуй, мотивирующий пример того, почему обменность имеет значение при случайной выборке.