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

  • Cité de l'Économie

    Лариса как-то напомнила мне об открывшемся в Париже Музее Экономики, и мы с Анютой сходили туда. Наверное,…

  • Линьяно 2021

    Этим летом устроили себе «День сурка» второго порядка: после года, проведённого как один нескончаемый день, решили провести летний отпуск в точности…

  • Collection Pinault в Bourse de Commerce

    В Париже открылся ещё один музей современного искусства, я его давно ждал, Коллекция Пино в том красивом круглом здании на Châtelet. Теперь…

  • 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