Почему порядок карт в хорошо перемешанной колоде почти наверняка никогда не повторялся
У колоды из 52 карт существует 52!, или около 8 × 10⁶⁷, порядков. Поэтому новый честный расклад почти наверняка ещё никто не видел.
Дальше вы увидите, откуда берётся это число, почему парадокс дней рождения не отменяет вывод и чем математически честное перемешивание отличается от пары ленивых перекладываний.
В статье вы узнаете:
Каждая следующая карта умножает число вариантов
Положим на стол пустую колоду и начнём выбирать карты по одной. На первое место подходит любая из 52 карт. После выбора остаётся 51 вариант для второго места, затем 50 для третьего. Последняя карта уже определяется всеми предыдущими.
Количество полных порядков получается произведением всех целых чисел от 1 до 52. Такое произведение называется факториалом:
Точное значение содержит 68 цифр:
80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000
Здесь важны две оговорки. Все карты считаются различимыми, даже если у двух совпадает достоинство. Пиковая семёрка и бубновая семёрка занимают разные места. Кроме того, порядок читается от верхней карты к нижней. Если поменять местами только две карты, получится новая перестановка.
Можно проверить рост по ступеням в калькуляторе факториала. Для 10 карт существует 3 628 800 порядков, для 20 уже 2,43 × 1018, для 40 около 8,16 × 1047. Последние двенадцать карт добавляют ещё двадцать порядков величины.
Перестановка является способом расположить все различимые элементы в определённом порядке. Для n элементов существует n! перестановок.
Человеческая история занимает ничтожную долю пространства колоды
Большие числа легко превращаются в словесный туман, поэтому возьмём нарочно невозможный эксперимент. Пусть каждый из восьми миллиардов людей перемешивает по одной колоде каждую секунду в течение ста лет и никогда не отдыхает. Получится примерно 2,5 × 1019 перемешиваний.
Это много для рук, складов и мирового производства картона. Для пространства из 52! порядков это почти ничего. Доля просмотренных вариантов составит около 3 × 10−49. Следующая равномерно выбранная перестановка совпадёт с одним из них примерно с такой же вероятностью.
Можно посмотреть на число с другой стороны. Если проверять по миллиарду порядков в секунду, полный перебор 52! занял бы около 2,6 × 1051 лет. Возраст Вселенной измеряется десятками миллиардов лет. Сравнение отличается примерно на сорок порядков величины, и здесь калькулятор уже начинает смотреть на нас с лёгким осуждением.
Фраза «такого порядка никогда не было» остаётся вероятностным выводом, а не историческим фактом. Никто не записывал каждую колоду, разложенную на кухне, в казино и на турнире. Некоторые исходные порядки выпускаются фабрикой одинаковыми, а небрежные тасования сохраняют большие фрагменты. Точный смысл утверждения такой: после достаточно равномерного случайного перемешивания шанс попасть в один конкретный прежний порядок ничтожен.
Для обычной комбинаторной задачи можно отдельно посчитать перестановки всех элементов или размещения части набора. Колода использует режим полной перестановки: участвуют все 52 карты.
Парадокс дней рождения разрешает повторы, но очень нескоро
Сравнивать только следующий порядок со всеми предыдущими недостаточно, если нас интересует хотя бы один повтор внутри большой истории. Каждая новая колода образует пары со всеми старыми, как участники в парадоксе дней рождения. Поэтому первая коллизия становится вероятной задолго до полного перебора.
Для пространства из N равновероятных вариантов вероятность повтора приближается к 50%, когда число испытаний достигает примерно 1,18√N. У колоды квадратный корень из 52! имеет порядок 1034. Значит, для заметного шанса хотя бы одной случайной коллизии понадобилось бы около десяти дециллионов дециллионов перемешиваний.
Наш фантастический век непрерывной работы всего человечества дал лишь 2,5 × 1019 попыток. Вероятность любой пары одинаковых порядков в таком опыте была бы примерно 4 × 10−30. Это уже больше, чем доля просмотренного пространства, потому что сравнений много, но всё ещё практически ноль.
Редкость повторов требует равномерного выбора. Если человек каждый раз снимает верхнюю карту и кладёт вниз, вариантов мало и они быстро зациклятся. Огромное число 52! описывает доступное пространство, но не гарантирует, что конкретный способ тасования исследует его честно.
Хорошее перемешивание стирает информацию о старом порядке
Идеальная математическая модель выдаёт каждую из 52! перестановок с одинаковой вероятностью 1/52!. Реальные руки так не работают. Один способ оставляет рядом соседние карты, другой переносит блоки, третий чаще сохраняет верх и низ. Поэтому качество тасования оценивают не красотой движения, а тем, насколько распределение результата приблизилось к равномерному.
Распространённое рифлёное тасование делит колоду примерно пополам и вплетает две пачки друг в друга. Дэйв Байер и Перси Диаконис построили математическую модель такого процесса и показали резкий переход к случайности примерно после семи рифлёных тасований стандартной колоды. Это вывод для определённой модели и выбранной меры расстояния до равномерного распределения, а не магическая гарантия для любого человека, который семь раз уронил карты друг на друга. [Bayer, Diaconis, 1992]
Надрез колоды, то есть перенос верхнего блока вниз, вообще не меняет циклический порядок карт. Верх становится другим, но каждая карта сохраняет соседей. Перетасовка блоками создаёт больше вариантов, однако далека от независимого выбора всех позиций. Фокусник может использовать эту предсказуемость намеренно, обычный игрок получает её случайно.
Есть простой домашний тест. Возьмите четыре масти, предварительно собранные отдельными блоками, выполните несколько одинаковых тасований и посмотрите, насколько быстро распались длинные одноцветные серии. Это не строгая статистическая проверка, зато хорошо показывает, что движение карт и потеря старой структуры являются разными вещами.
Компьютеру нужен алгоритм Фишера-Йетса, а не случайная сортировка
В программе колоду удобно перемешивать с конца. Для последней позиции выбирают случайный индекс от первой карты до последней и меняют две карты местами. Затем переходят на позицию левее и выбирают индекс только в ещё не закреплённой части. Процесс продолжается до второй карты.
Это алгоритм Фишера-Йетса. При равномерном генераторе индексов каждая перестановка получает одинаковый шанс: на первом шаге 1/52, на втором 1/51 и так далее. Произведение вероятностей равно 1/52!, как и требуется.
Трюк со случайным результатом функции сортировки этого не гарантирует. Сортировщик ожидает последовательное правило сравнения, а случайные ответы могут противоречить друг другу. Конкретный движок делает разное число сравнений для разных исходов, поэтому часть перестановок появляется чаще.
Посмотреть алгоритм на любом наборе можно в инструменте перемешивания строк списка. Возьмите пять элементов и несколько раз сравните результат. Возможных порядков всего 5! = 120, поэтому повторы появятся быстро. Затем добавьте ещё пять строк: уже 10! = 3 628 800, и знакомые расклады станут редкостью.
Что хочется сказать в конце. Уникальность колоды создаёт не загадочная сила карт, а сочетание двух условий: факториально большого пространства и достаточно честного выбора внутри него. 52! делает повтор невероятным, хороший алгоритм действительно даёт этому числу работать, а плохое тасование способно превратить космический масштаб в короткий цикл знакомых раскладов.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.