Модель Гилберта–Шеннона–Ридса

Математическая формализация перетасовки карт

В математике перетасовки игральных карт модель Гилберта–Шеннона–Ридса (Gilbert–Shannon–Reeds model) представляет собой распределение вероятностей на перестановках, получаемых при рифл-перетасовке. Она служит основанием для рекомендации перетасовывать колоду карт семь раз для её полной рандомизации. Модель названа в честь работ Эдгара Гилберта (Edgar Gilbert), Клода Шеннона (Claude Shannon) и Джима Ридса (J. Reeds), описанных в техническом отчёте Гилберта 1955 года и неопубликованной рукописи Ридса 1981 года.

Описание

Перестановка при рифл-перетасовке последовательности элементов получается путём разделения элементов на две смежные подпоследовательности с последующим произвольным чередованием этих подпоследовательностей. Например, это описывает многие распространённые способы перетасовки колоды карт: колода разрезается на две стопки, которые затем перемешиваются вместе. Модель Гилберта–Шеннона–Ридса назначает вероятность каждой из этих перестановок, описывая вероятность получения каждой перестановки при случайной перетасовке. Модель может быть определена несколькими эквивалентными способами:

• **Способ, наиболее близкий к тому, как люди перетасовывают карты.** Модель Гилберта–Шеннона–Ридса описывает вероятности, получаемые при определённой математической модели случайного разрезания и последующей рифл-перетасовки колоды. Сначала колода разрезается на два пакета. Если всего n карт, то вероятность выбрать k карт в первый пакет и n−k во второй определяется как C(n,k)/2^n. Затем карты по одной перемещаются со дна одного из пакетов на верх перетасованной колоды таким образом, что если в одном пакете осталось x карт, а в другом y карт, то вероятность выбрать карту из первого пакета равна x/(x+y), а из второго — y/(x+y).

• **Второе альтернативное описание** основано на свойстве модели, согласно которому она генерирует перестановку исходной колоды, в которой каждая карта с равной вероятностью могла прийти из первого или второго пакета. Для генерации случайной перестановки по этой модели нужно n раз подбросить честную монету, чтобы определить для каждой позиции перетасованной колоды, откуда она происходит. Затем разделить на два пакета размерами, равными числу выпавших решек и орлов, и использовать ту же последовательность бросаний для определения, из какого пакета брать каждую карту.

• **Третье альтернативное описание** более абстрактно, но лучше подходит для математического анализа. Генерируются n значений из равномерного непрерывного распределения на единичном интервале и упорядочиваются. Затем отображение удвоения x ↦ 2x (mod 1) из теории динамических систем преобразует эту систему точек в перестановку, в которой новый порядок подчиняется модели Гилберта–Шеннона–Ридса, а позиции новых точек снова распределены равномерно.

Среди всех возможных перестановок при рифл-перетасовке колоды карт модель Гилберта–Шеннона–Ридса присваивает почти всем перетасовкам одинаковую вероятность 1/2^n. Однако есть одно исключение — тождественная перестановка (когда порядок карт не меняется), которая имеет большую вероятность (n+1)/2^n. Таким образом, для стандартной 52-карточной колоды перетасовка, не изменяющая порядок карт, в 53 раза более вероятна, чем любая другая отдельная перестановка.

Обратная перестановка

Обратную перестановку случайной рифл-перетасовки можно сгенерировать непосредственно. Для этого начните с колоды из n карт и повторно снимайте карты со дна колоды на одну из двух стопок, выбирая случайно с равной вероятностью, на какую стопку положить каждую карту. Когда все карты разложены, сложите две стопки обратно вместе.

Эффект повторных перетасовок

Формула для одной перетасовки показывает, что тождественная перестановка намного более вероятна, чем любая другая отдельная перестановка. Она остаётся наиболее вероятной перестановкой даже после повторных перетасовок в этой модели.

Байер и Диакони (Bayer & Diaconis, 1992) математически проанализировали полную вариационную дистанцию между двумя распределениями вероятностей на перестановках: равномерным распределением, в котором все перестановки равновероятны, и распределением, генерируемым повторным применением модели Гилберта–Шеннона–Ридса. Полная вариационная дистанция измеряет сходство или различие двух распределений вероятностей; она равна нулю только когда распределения идентичны, и достигает максимума один для распределений, которые никогда не генерируют одинаковые значения. Байер и Диакони обнаружили, что для колод из n карт, перетасованных (3/2)log₂n + θ раз, где θ — произвольная константа, полная вариационная дистанция близка к единице, когда θ значительно меньше нуля, и близка к нулю, когда θ значительно больше нуля, независимо от n. В частности, их расчёты показали, что для n = 52 пять перетасовок дают распределение, полная вариационная дистанция которого от равномерного всё ещё близка к единице, тогда как семь перетасовок дают полную вариационную дистанцию 0,334. Этот результат широко интерпретировался как указание на то, что колоды карт следует перетасовывать семь раз для их полной рандомизации.

Подобные анализы проводились с использованием дивергенции Кульбака–Лейблера (Kullback–Leibler divergence) — дистанции между двумя распределениями вероятностей, определяемой через энтропию; дивергенция распределения от равномерного может интерпретироваться как количество битов информации, которые всё ещё можно восстановить об исходном состоянии колоды карт. Результаты качественно отличаются: вместо резкого порога между случайным и неслучайным состояниями при (3/2)log₂n перетасовках, как происходит для полной вариационной дистанции, дивергенция убывает более постепенно, уменьшаясь линейно при количестве перетасовок от нуля до log₂n (в этой точке количество оставшихся битов информации линейно, на логарифмический множитель меньше исходного значения), а затем убывает экспоненциально, пока после (3/2)log₂n перетасовок остаётся только постоянное количество битов информации.