Феномен внезапной сходимости цепей Маркова и тасование игральных карт

В середине 80х годов было обнаружено, что некоторые цепи Маркова обладают свойством внезапной сходимости (cutoff). Это означает, что в течение длительного времени распределение цепи далеко от стационарного (расстояние близко к 1 в метрике полной вариации), но затем на узком временном интервале происходит скачок, при котором это расстояние внезапно “падает” и далее быстро убывает к нулю. В качестве примера такого поведения мы рассмотрим модель Гильберта–Шеннона–Ридса тасования колоды двумя руками (riffle shuffling). Данная тематика обязана своим развитием Перси Дьяконису, который начал свой жизненный путь в качестве профессионального фокусника. Его результаты и будут рассказаны.