В 1992 году математики Дэйв Байер и Перси Диаконис доказали, что семи riffle shuffles — когда колоду делят на две стопки и зиппером перетасовывают — достаточно для полного перемешивания. Они обнаружили эффект cutoff phenomenon: после шестого перемешивания карты ещё сохраняют порядок, а на седьмом резко становятся хаотичными. Но доказательство работало только для строгих условий — колоду нужно было разрезать примерно пополам, а перемешивание должно было следовать точной вероятностной модели. Если тасовать «как школьник», результат не держался.
Теперь трое математиков расширили это на менее аккуратные перемешивания. Марк Селлке — статистик из Гарварда, сейчас в отпуске в OpenAI — вместе с аспирантами Дзялу Ши (Кембридж) и Цзяминь Ван (Принстон) доказали, что cutoff существует даже когда колоду режут не пополам и каждый раз по-разному.
Они придумали остроумный трюк — присвоили каждой карте «штрих-код» из единиц и нулей. При каждом разрезе и перемешивании карта получает 1, если попадает в левую стопку, и 0 — в правую. После нескольких шагов у каждой карты накапливается уникальная последовательность, которая кодирует её путь. Если две карты, скажем 16 и 17, получают одинаковый штрих-код, они сохраняют свой относительный порядок. Чтобы доказать cutoff, нужно показать, что после определённого числа перемешиваний таких совпадений почти не остаётся. И тут помогли так называемые cold spots — участки колоды, где порядок сохраняется дольше всего. Достаточно проверить только их.
Диаконис восторженно отозвался о работе: «Это свежая идея, и замечательно, что она так эффективно работает. Блестящая математика». Ранее другие математики, в частности Стивен Лалли, пытались ослабить ограничения, но доказать не смогли. Новое доказательство — важный шаг в понимании cutoff phenomenon, который встречается не только в картах, но и в физике спиновых стёкол и других сложных системах.