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

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

Модель

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

Модель Гилберта-Шеннона-Ридса, наиболее похожая на то, как люди тасуют карты, описывает вероятности, полученные на основе определенной математической модели случайного вырезания, а затем перелистывания колоды карт. Сначала колода разрезается на два пакета. Если всего имеется $n$ карты, то вероятность выбора $k$ карты в первой колоде и $n-k$ во второй колоде определяется как ${\tbinom {n}{k}}/2^{n}$ . Затем по одной карте неоднократно перемещается со дна одной из пачек на верх перетасованной колоды, так что если $x$ карты остаются в одной пачке и $y$ карты остаются в другом пакете, то вероятность выбрать карту из первого пакета равна $x/(x+y)$ а вероятность выбрать карту из второго пакета равна $y/(x+y)$ . ^{[ 2 ]}
Второе, альтернативное описание может быть основано на свойстве модели, заключающейся в том, что она генерирует перестановку исходной колоды, в которой каждая карта с равной вероятностью произошла из первого или второго пакета. ^{[ 2 ]} Чтобы сгенерировать случайную перестановку в соответствии с этой моделью, начните с подбрасывания честной монеты. $n$ раз, чтобы определить для каждой позиции перетасованной колоды, принадлежит ли она первому пакету или второму пакету. Затем разделите их на две пачки, размеры которых равны числу решек и количеству перевернутых орлов, и используйте ту же последовательность подбрасывания монеты, чтобы определить, из какой пачки вытащить каждую карту перетасованной колоды.
Третье альтернативное описание более абстрактно, но лучше поддается математическому анализу. Сгенерировать набор $n$ значения из равномерного непрерывного распределения на единичном интервале и расположите их в отсортированном порядке. Тогда карта удвоения $x\mapsto 2x{\pmod {1}}$ из теории динамических систем отображает эту систему точек в перестановку точек, в которой перестановочный порядок подчиняется модели Гилберта – Шеннона – Ридса, а положения новых точек снова являются равномерно случайными. ^{[ 2 ]}^{[ 4 ]}

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

Обратный

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

Эффект повторных рифлений

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

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

Ссылки

^ Диаконис, Перси (1988), Представления групп в вероятности и статистике , Конспекты лекций Института математической статистики - серия монографий, 11, Хейворд, Калифорния: Институт математической статистики, ISBN 978-0-940600-14-0 , МР 0964069 .
^ Jump up to: ^а ^б ^с ^д ^и Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову» (PDF) , The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752 , MR 1161056 .
^ Гилберт, Э. (1955), Теория перетасовки , Технический меморандум, Bell Labs
^ Лалли, Стивен П. (1999), «Перетасовка винтовок и связанные с ними динамические системы», Journal of Theoretical Probability , 12 (4): 903–932, doi : 10.1023/A:1021636902356 , MR 1729462 , S2CID 123898250 .
^ Это непосредственно следует из теоремы 1 Байера и Диакониса (1992) вместе с наблюдением, что тождественная перестановка имеет одну восходящую последовательность, а все другие перестановки с винтовыми перестановками имеют ровно две восходящие последовательности. Вместо этого Лалли (1999) ошибочно утверждает, что все перестановки вероятны.
^ Остин, Дэвид (декабрь 2010 г.), Сколько раз мне придется тасовать эту колоду? , Столбцы функций AMS .
^ Numb3rs 519: Обряды с животными , Математические занятия Numb3rs, Математический факультет Корнелльского университета .
^ Колата, Джина (9 января 1990 г.), «При перетасовке карт 7 — выигрышное число» , New York Times .
^ Трефетен, LN ; Трефетен, Л.М. (2000), «Сколько тасований нужно для рандомизации колоды карт?», Труды Лондонского королевского общества. Серия A: Mathematical, Physical and Engineering Sciences , 456 (2002): 2561–2568, Bibcode : 2000RSPSA.456.2561T , doi : 10.1098/rspa.2000.0625 , MR 1796496 , S2CID 14055379 .
^ Старк, Дадли; Ганеш, А.; О'Коннелл, Нил (2002), «Потеря информации при перетасовке», Combinatorics, Probability and Computing , 11 (1): 79–95, doi : 10.1017/S0963548301004990 , MR 1888184 , S2CID 29990983 .

[1] Диаконис, Перси (1988), Представления групп в вероятности и статистике , Конспекты лекций Института математической статистики - серия монографий, 11, Хейворд, Калифорния: Институт математической статистики, ISBN 978-0-940600-14-0 , МР 0964069 .

[bd92-2] Jump up to: ^а ^б ^с ^д ^и Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову» (PDF) , The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752 , MR 1161056 .

[3] Гилберт, Э. (1955), Теория перетасовки , Технический меморандум, Bell Labs

[4] Лалли, Стивен П. (1999), «Перетасовка винтовок и связанные с ними динамические системы», Journal of Theoretical Probability , 12 (4): 903–932, doi : 10.1023/A:1021636902356 , MR 1729462 , S2CID 123898250 .

[5] Это непосредственно следует из теоремы 1 Байера и Диакониса (1992) вместе с наблюдением, что тождественная перестановка имеет одну восходящую последовательность, а все другие перестановки с винтовыми перестановками имеют ровно две восходящие последовательности. Вместо этого Лалли (1999) ошибочно утверждает, что все перестановки вероятны.

[6] Остин, Дэвид (декабрь 2010 г.), Сколько раз мне придется тасовать эту колоду? , Столбцы функций AMS .

[7] Numb3rs 519: Обряды с животными , Математические занятия Numb3rs, Математический факультет Корнелльского университета .

[8] Колата, Джина (9 января 1990 г.), «При перетасовке карт 7 — выигрышное число» , New York Times .

[9] Трефетен, LN ; Трефетен, Л.М. (2000), «Сколько тасований нужно для рандомизации колоды карт?», Труды Лондонского королевского общества. Серия A: Mathematical, Physical and Engineering Sciences , 456 (2002): 2561–2568, Bibcode : 2000RSPSA.456.2561T , doi : 10.1098/rspa.2000.0625 , MR 1796496 , S2CID 14055379 .

[10] Старк, Дадли; Ганеш, А.; О'Коннелл, Нил (2002), «Потеря информации при перетасовке», Combinatorics, Probability and Computing , 11 (1): 79–95, doi : 10.1017/S0963548301004990 , MR 1888184 , S2CID 29990983 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]