Jump to content

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

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

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

  • Модель Гилберта-Шеннона-Ридса, наиболее похожая на то, как люди тасуют карты, описывает вероятности, полученные на основе определенной математической модели случайного вырезания, а затем перелистывания колоды карт. Сначала колода разрезается на два пакета. Если всего имеется карты, то вероятность выбора карты в первой колоде и во второй колоде определяется как . Затем по одной карте неоднократно перемещается со дна одной из пачек на верх перетасованной колоды, так что если карты остаются в одной пачке и карты остаются в другом пакете, то вероятность выбрать карту из первого пакета равна а вероятность выбрать карту из второго пакета равна . [ 2 ]
  • Второе, альтернативное описание может быть основано на свойстве модели, заключающейся в том, что она генерирует перестановку исходной колоды, в которой каждая карта с равной вероятностью произошла из первого или второго пакета. [ 2 ] Чтобы сгенерировать случайную перестановку в соответствии с этой моделью, начните с подбрасывания честной монеты. раз, чтобы определить для каждой позиции перетасованной колоды, принадлежит ли она первому пакету или второму пакету. Затем разделите их на две пачки, размеры которых равны числу решек и количеству перевернутых орлов, и используйте ту же последовательность подбрасывания монеты, чтобы определить, из какой пачки вытащить каждую карту перетасованной колоды.
  • Третье альтернативное описание более абстрактно, но лучше поддается математическому анализу. Сгенерировать набор значения из равномерного непрерывного распределения на единичном интервале и расположите их в отсортированном порядке. Тогда карта удвоения из теории динамических систем отображает эту систему точек в перестановку точек, в которой перестановочный порядок подчиняется модели Гилберта – Шеннона – Ридса, а положения новых точек снова являются равномерно случайными. [ 2 ] [ 4 ]

Среди всех возможных перестановок карточной колоды с перетасовкой желобков модель Гилберта – Шеннона – Ридса дает почти все перетасовки с равной вероятностью: , происходящего. Однако есть одно исключение — тождественная перестановка , которая имеет большую вероятность происходящего. [ 5 ]

Обратный

[ редактировать ]

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

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

[ редактировать ]

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

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

  1. ^ Диаконис, Перси (1988), Представления групп в вероятности и статистике , Конспекты лекций Института математической статистики - серия монографий, 11, Хейворд, Калифорния: Институт математической статистики, ISBN  978-0-940600-14-0 , МР   0964069 .
  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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ba2f87b57c8f176fa8fb8a69b8032a40__1714799520
URL1:https://arc.ask3.ru/arc/aa/ba/40/ba2f87b57c8f176fa8fb8a69b8032a40.html
Заголовок, (Title) документа по адресу, URL1:
Gilbert–Shannon–Reeds model - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)