![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Как не нужно перетасовывать карты
Aug. 25th, 2017 10:22 amПродолжаю читать книжку про игрушки. Рассматривается два алгоритма тасовывания колоды из 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, чем три других.
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, чем три других.
