green_fr (green_fr) wrote,
green_fr
green_fr

Category:

Как не нужно перетасовывать карты

Продолжаю читать книжку про игрушки. Рассматривается два алгоритма тасовывания колоды из N карт:

1. Тянем случайное число X1 от 1 до N, меняем местами карты, находящиеся на местах X1 и N. Затем тянем случайное число X2 от 1 до N-1, меняем X2 и N-1. И так далее, пока не вытянем XN (которое несомненно будет равно 1, чтобы поменять первую карту с самой собой).
2. Тянем случайное число X1 от 1 до N, меняем местами карты, находящиеся на местах X1 и N. Затем тянем случайное число X2 от 1 до N, меняем X2 и N-1. И так далее N раз.

Первый алгоритм, очевидно, работает прекрасно. Второй алгоритм, как это ни странно, даёт перекосы. Чтобы в этом убедиться, автор предлагает рассмотреть колоду из 3 карт.
Первый алгоритм тянет 3 случайных числа, всего 6 разных вариантов с одинаковой вероятностью, причём эти варианты соответствуют всем возможным вариантам тасовки колоды из 3 карт.
А второй аглоритм предлагает 27 равновероятных вариантов, и, даже не глядя на них, очевидно, что они не могут сгруппироваться в 6 вариантов перетасовки таким образом, чтобы они стали равновероятными (27 на 6 не делится).

Ещё один удар по интуитивному восприятию. Какое-то время ещё кажется, что проблема в том, что второй алгоритм может ни разу не вытянуть какое-то число, и таким образом у каждой карты больше вероятность остаться на том же месте, чем оказаться на каком-то из других мест в конце перетасовки. Это могло бы решаться многократным повтором тасовки, но простая проверка (перебор тех самых 27 вариантов) показывает, что даже это не так — первоначальная конфигурация ABC чаще даёт варианты ACB, CAB и BAC, чем три других.
Tags: statistiques, программирование
Subscribe

  • Демография Франции 2020 года

    Был вчера на работе, за обедом разговорились о рождаемости: у коллеги летом будет ребёнок, он ищет место в яслях, надеется, что спад рождаемости…

  • Шутка про баян

    Отличная шутка на bash.org, я давно так не хохотал, но только для программистов: V: А ещё мне тут пришла в голову правильная аналогия про Vim V:…

  • Полезная книжка по информатике...

    Слушаю передачу про то, как мы учимся. Гость в студии — когнитивный психолог и нейролог, то есть ну вот никак не программист. В какой-то момент…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments