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

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

18 голосов
/ 13 мая 2009

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

# 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), чтобы он правильно перемешал.

Ответы [ 12 ]

0 голосов
/ 18 мая 2009

Наивный алгоритм выбирает значения 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 комбинаций) Ответ Лассевка показывает распределение по картам этих комбинаций.

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

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.

0 голосов
/ 14 мая 2009

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

Страница:
...