КОГДА ТАСОВКА ВНАХЛЁСТ ЗАБЫВАЕТ КОЛОДУ?

Тасование карт — конкретная версия базового вопроса теории вероятностей: сколько времени нужно случайному процессу, чтобы забыть, откуда он начался? Только что распечатанная колода упорядочена. Каждая тасовка перемешивает её чуть сильнее, пока никакой след исходного порядка нельзя будет обнаружить.

Математики различают два уровня ответа. Время перемешивания даёт порядок величины. Каттоф (cutoff, резкий порог) говорит гораздо больше: около одного точного момента колода почти мгновенно переходит из состояния «явно не перемешана» в состояние «тщательно перемешана». Тасуйте чуть меньше — и это ещё можно заметить; чуть дольше — уже нельзя.

Тасовка глазами математика

При тасовке внахлёст вы держите колоду в одной руке и роняете маленькие пачки карт в другую. Статья моделирует это так: каждый из n − 1 промежутков между соседними картами разрезается независимо с вероятностью p, а порядок получившихся пачек переворачивается. Один полный проход по колоде считается одной тасовкой.

Согласно статье, более ранние работы уже установили порядок величины. Пемантл ограничил время перемешивания между n² и n² log n; затем Йонассон показал, что правильный порядок — n² log n. Но точная константа, как и вопрос о том, возникает ли вообще резкий порог, оставались открытыми: Диаконис и Пал включили каттоф для тасовки внахлёст в список открытых проблем в 2022 году.

Результат

Юньцзян Цзян доказывает, что каттоф существует, и находит его положение.

Теорема. При фиксированной вероятности разреза p тасовка внахлёст перемешивает колоду, в первом порядке, за

p² / (2(1 − p)π²) × n² log n

тасовок. Чуть раньше колода остаётся далёкой от случайной; чуть позже — близка к случайной.

При p = 1/2 — в среднем разрезается половина промежутков — формула принимает вид n² log n / (4π²).

Как устроено доказательство

Доказательство состоит из трёх независимых частей.

1. Нижняя оценка следит за одной картой. Её положение эволюционирует удивительно чисто: точные косинусоидальные узоры затухают с известной скоростью, даже для конечной колоды. Просуммированные по всей колоде, они сохраняют обнаружимый след исходного порядка вплоть до предсказанного момента.
2. Верхняя оценка сравнивает две колоды, отличающиеся только перестановкой двух карт. При одних и тех же случайных разрезах различие ведёт себя как две отмеченные позиции, блуждающие по колоде, пока они не станут соседями и не смогут слиться. Скорость, с которой это происходит, совпадает с нижней оценкой.
3. Статическое неравенство для перестановок, не связанное с тасованием, превращает это сравнение в утверждение обо всей колоде. Это самая техническая часть статьи, построенная рекурсивно на таблицах, подсчитывающих, как карты распределены по блокам.

Статья также доказывает каттоф для другой меры беспорядка, относительной энтропии, не определяя его точного положения.

Что формула говорит о настоящей колоде

Подстановка колоды из 52 карт в формулу при p = 1/2 даёт 52² × ln 52 / (4π²), около 270 тасовок. Это наш собственный подсчёт, а не цифра из статьи, и её следует понимать как грубый ориентир: теорема описывает поведение очень больших колод, а поправочный член не оценён количественно. Для сравнения статья приводит масштаб (3/2) log₂ n, установленный Байером и Диаконисом для тасовки «ёлочкой» (riffle shuffle), — около 8,6 для 52 карт, с той же оговоркой. Именно разрыв между n² log n и log n делает тасовку внахлёст такой медленной.

Первый порядок, идеализированные руки

Результат относится к первому порядку: он не даёт ни ширины переходного окна, ни его точной формы. Вероятность разреза фиксирована, а разрезы предполагаются независимыми — идеализация реальных рук. В сноске автор указывает, что система ИИ GPT-6 Astra «использовалась при разработке рассуждений, проверке вычислений и подготовке изложения» и что автор несёт ответственность за математическое содержание. Статья является препринтом.