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

В математике шаркающий играя в карты, то Модель Гилберта – Шеннона – Ридса это распределение вероятностей на перестановки в случайном порядке который, как сообщается, хорошо соответствует экспериментально наблюдаемым результатам перетасовки человека,^[1] и это является основанием для рекомендации, что колоду карт следует перетерять семь раз, чтобы тщательно ее рандомизировать.^[2] Он назван в честь работы Эдгар Гилберт, Клод Шеннони Дж. Ридс в техническом отчете Гилберта за 1955 г.^[3] и в неопубликованной рукописи Ридса 1981 года.

Модель

Модель Гилберта – Шеннона – Ридса может быть определена несколькими эквивалентными способами.

Наиболее похоже на то, как люди тасуют карты, это можно определить как случайное нарезание и тасование. Колода карт разрезается на две пачки; если есть в общей сложности п карты, то вероятность выбора k карты в первой колоде и п − k во второй колоде ${ Displaystyle { tbinom {п} {к}} / 2 ^ {п}}$. Затем по одной карте за раз повторно перемещается из нижней части одного из пакетов в верхнюю часть перетасованной колоды, так что если Икс карты остаются в одной пачке и у карты остаются в другом пакете, то вероятность выбора карты из первого пакета равна Икс/(Икс + у), а вероятность выбора карты из второго пакета равна у/(Икс + у).^[2]

Альтернативное описание может быть основано на том свойстве модели, что она генерирует перестановку исходной колоды, в которой каждая карта с равной вероятностью пришла из первого или второго пакета.^[2] Чтобы сгенерировать случайную перестановку в соответствии с этой моделью, начните с переворота честная монета п раз, чтобы определить для каждой позиции перетасованной колоды, из первого она или из второго пакета. Затем разделите на два пакета, размеры которых соответствуют количеству решек и количеству перевернутых орлов, и используйте ту же последовательность подбрасывания монеты, чтобы определить, из какого пакета вытащить каждую карту перетасованной колоды.

Другое альтернативное описание более абстрактно, но лучше поддается математическому анализу. Создать набор п ценности из равномерное непрерывное распределение на единичном интервале и расположите их в отсортированном порядке. Тогда удвоение карты ${ Displaystyle х mapsto 2x { pmod {1}}}$ из теории динамические системы отображает эту систему точек в перестановку точек, в которых переставленный порядок подчиняется модели Гилберта – Шеннона – Ридса, и положения новых точек снова равномерно случайны.^[2][4]

Среди всех возможных перестановки в случайном порядке колоды карт модель Гилберта – Шеннона – Ридса дает почти всем рифлям равную вероятность, 1/2^п, встречающихся. Однако есть одно исключение: перестановка идентичности, что имеет большую вероятность (п + 1)/2^п возникновения.^[5][6]

Обратный

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

Эффект повторяющихся рифов

Байер и Диаконис (1992) математически проанализировал общее расстояние вариации между двумя вероятностными распределениями перестановок: равномерное распределение в котором все перестановки равновероятны, и распределение, порожденное повторными применениями модели Гилберта – Шеннона – Ридса. Общее расстояние вариации показывает, насколько похожи или различны два распределения вероятностей; он равен нулю только тогда, когда два распределения идентичны, и достигает максимального значения, равного единице, для распределений вероятностей, которые никогда не генерируют одинаковые значения друг с другом. Байер и Диаконис сообщили, что для колод п карты перемешаны ${ Displaystyle { tfrac {3} {2}} log _ {2} п + тета}$ раз, где θ - произвольная константа, полное расстояние вариации близко к единице, когда θ значительно меньше нуля и близко к нулю, когда θ значительно больше нуля, независимо отп. В частности, их расчеты показали, что для п = 52, пять рифлей дают распределение, общее расстояние отклонения от униформы по-прежнему близко к единице, а семь рифлей дают общее расстояние отклонения 0,334. Этот результат был широко известен как подразумевающий, что колоды карт должны быть перетасованы семь раз, чтобы тщательно их рандомизировать.^[7][8][9]

Подобные анализы были выполнены с использованием Дивергенция Кульбака – Лейблера, расстояние между двумя распределениями вероятностей, определенными в терминах энтропия; отклонение распределения от равномерного можно интерпретировать как количество биты информации о начальном состоянии колоды карт, которую еще можно восстановить. Результаты качественно разные: вместо того, чтобы иметь резкий порог между случайным и неслучайным на ${ displaystyle { tfrac {3} {2}} log _ {2} n}$ перемешивания, как это происходит для общего расстояния вариации, расхождение уменьшается более постепенно, уменьшаясь линейно по мере того, как количество перемешиваний изменяется от нуля до ${ Displaystyle журнал _ {2} п}$ (в этот момент количество оставшихся битов информации линейно, меньше на логарифмический коэффициент, чем его начальное значение), а затем экспоненциально уменьшается до тех пор, пока ${ displaystyle { tfrac {3} {2}} log _ {2} n}$ перемешивается, остается только постоянное количество бит информации.^[10][11]

Рекомендации