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

Question

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

# 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 карты), и запустить его 10000 раз и подсчитать результаты, вы увидите, что результаты искажены к определенным шаблонам .. .

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

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

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: спасибо всем, кто указал, что он должен быть рандомным ($ i, 51), чтобы он правильно перемешал.

Answer 1

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

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

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

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

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

Answer 2

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

Предположим, что вы начинаете с последовательности 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

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

Answer 3

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

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

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

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

Answer 4

Лучшее объяснение этому эффекту было от Джеффа Этвуда в его блоге CodingHorror ( Опасность наивности ).

Использование этого кода для симуляции случайного перемешивания из трех карт ...

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 возможных комбинаций из трех карточных колод. Таким образом, некоторые комбинации перепредставлены.

Для правильной (случайной) перетасовки колоды карт вам понадобится перетасовка Фишера-Йейтса .

Answer 5

Вот еще одна интуиция: один случайный обмен не может создать симметрию в вероятности занять позицию, если не существует хотя бы двухсторонней симметрии. Назовите три позиции 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 в положении А на одну из остальных. В этом случае перед свопом существовала двухсторонняя симметрия, потому что вероятность карты 1 в позиции B = вероятность карты 1 в позиции C = 0. Таким образом, на самом деле, карта 1 может оказаться с симметричными вероятностями, и это в конечном итоге в каждой из трех позиций с равной вероятностью. Это остается верным для всех последующих свопов. Но карта 2 оказывается в трех позициях после первого обмена с вероятностью (1/3, 2/3, 0), а также карта 3 оказывается в трех позициях с вероятностью (1/3, 0, 2/3) , Поэтому независимо от того, сколько последующих свопов мы сделаем, мы никогда не получим карту 2 или 3 с одинаковой вероятностью занять все три позиции.

Answer 6

См. Сообщение Код ужасов Опасность наивности .

В основном (с учетом 3 карт):

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

Answer 7

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

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

Answer 8

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

Answer 9

Самый ясный ответ, показывающий, что первый алгоритм не работает, состоит в том, чтобы рассматривать рассматриваемый алгоритм как марковскую цепочку из n шагов на графе n! вершины всех перестановок из n натуральных чисел. Алгоритм переходит от одной вершины к другой с вероятностью перехода. Первый алгоритм дает вероятность перехода 1/n для каждого прыжка. Существует n ^ n путей, вероятность каждого из которых составляет 1/n^n. Предположим, что окончательная вероятность посадки в каждой вершине равна 1/n!, что является уменьшенной дробью. Для этого должно быть m путей с одинаковой конечной вершиной, такой что m/n^n=1/n! или n^n = mn! для некоторого натурального числа m или что n^n делится на n!. Но это невозможно. В противном случае n должно делиться на n-1, что возможно только при n=2. У нас есть противоречие.

Answer 10

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

Если мы говорим о колоде с 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 розыгрышах:

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