Почти в каждой карточной игре после партии нужно перетасовать карты. Пока я тасую карты, передо мной всегда возникает вопрос: "Уже хватит?" Вопрос серьезный — лишнее время тратить не хочется, а играть на заряженной колоде тоже не в кайф.
В статье разберемся с ситуацией.
Способ тасовки
Есть крутые способы тасовать карты, riffle shuffle, например.
Я так не умею, да и картонные карты так не получится шафлить, поэтому я тасую простым способом, выглядит примерно так:
Сначала я отделяю от колоды часть, потом долю этой части закидываю на другую сторону, а после докладываю оставшуюся долю. По моим наблюдениям люди тасуют карты именно так или близко к этому. В целом, можно разделять и на большее количество частей, но это уже детали. В статье будем анализировать этот метод тасовки.
Что такое случайная раскладка карт?
Первое что пришло мне в голову — хорошая раскладка та, на i-м месте может равновероятно оказаться любая карта.
Но этого недостаточно. Например, если колоду "срезать" — разделить в случайном месте на две и поменять их местами — то первой картой равновероятно может оказаться любая. Но при этом, это, очевидно, плохая раскладка: после каждой карты, кроме нескольких, будет идти та же карта, которая лежала после нее до "среза". То есть, игрокам будут приходить "скоррелированные" карты. В случае игры в дурака одному придет та, которой били, а другому — та, которую били, и это будет совсем не случайно.
Другой подход к определению хорошей раскладки — на i+1-м месте лежит карта независимая от карты на i-м месте. Представить это можно так: если смотришь верхнюю карту колоды, то не можешь предположить какая карта будет следующей.
У этого подхода тоже могут быть проблемы, которые решаются рассмотрением больших совместных распределений, но для текущего анализа она нам полностью подойдет.
Как измерять "хорошесть" раскладки
Мы взяли колоду, оставшуюся после предыдущей игры. Занумеруем все карты по порядку. Плохая ситуация — когда после перетасовки в каком-то месте после карты с номером i идет карта с номером i+1. Поэтому будем измерять долю карт, которые лежат по порядку после перетасовки.
Понятно, что даже в хорошо потасованной колоде некоторые карты случайно лягут по порядку. Их доля будет в среднем 1/(n-1), где n — количество карт в колоде.
Пруф
E(sum($ai = a{i+1}$ for i = 0..(n-1)) / (n-1)) = sum(E($ai = a{i+1}$) for i = 0..(n-1)) / (n-1) — из-за линейности мат. ожидания.
И так как E($ai = a{i+1}$) = 1/(n-1) то это выражение = (n-1) * 1/(n-1) / (n-1) = 1/(n-1)
Результаты
Посчитаем вероятность подряд идущих карт для колоды из 52 карт в зависимости от количества итераций перемешивания.
Из графика видно, что даже после сотни итераций вероятность подряд идущих карт примерно в два раза выше, чем идеальная вероятность.
Код для построения графика
В целом, можно считать, что 60 итераций — оптимальное количество, меньше точно плохо. Я за 30 секунд делаю примерно 16-17 итераций. Это значит, что для нормальной перетасовки понадобится почти две минуты.
Мы с друзьями никогда столько не тасуем карты. А это значит, что у нас на игру очень сильно влияет расклад прошлой партии.
Будьте аккуратны :)
Оригинал статьи на Хабре (2019 год)
К лучшим публикациям на Хабре за сутки