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

  • Pour la science №524

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

  • Pour la Science №523

    Заметка о том, что археологи, раскапывая стоянки древних инуитов на Аляске, нашли венецианское стекло. Точнее бусинки, надетые на ниточку. Ниточка…

  • Pour la science №522

    Я наконец-то понял / смог представить себе проекцию 4-мерного куба (то, что получилось на  Большой арке Дефанс) и развёртку 4-мерного куба (то, что…

  • 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