Честная монета

Статистическая концепция

Подброшенная честная монета должна иметь равные шансы упасть любой стороной вверх.

В теории вероятностей и статистике последовательность независимых испытаний Бернулли с вероятностью успеха 1/2 в каждом испытании метафорически называется честной монетой . Монета, для которой вероятность не равна 1/2, называется предвзятой или нечестной монетой . В теоретических исследованиях предположение о честности монеты часто делается путем ссылки на идеальную монету .

Джон Эдмунд Керрич проводил эксперименты по подбрасыванию монеты и обнаружил, что монета, сделанная из деревянного диска размером с корону и покрытая с одной стороны свинцом, приземлялась орлом (деревянной стороной вверх) 679 раз из 1000. ^[1] В этом эксперименте монету подбрасывали, удерживая ее на указательном пальце, подбрасывая ее большим пальцем так, чтобы она прокрутилась в воздухе около фута, прежде чем приземлиться на плоскую ткань, расстеленную на столе. Эдвин Томпсон Джейнс утверждал, что когда монету ловят в руку, вместо того, чтобы позволить ей отскочить, физическое смещение в монете незначительно по сравнению с методом подбрасывания, когда при достаточной практике можно заставить монету приземляться орлом в 100% случаев. ^[2] Исследование проблемы проверки того, является ли монета честной, является общепризнанным педагогическим инструментом в обучении статистике .

Определение вероятностного пространства

В теории вероятностей честная монета определяется как вероятностное пространство , которое в свою очередь определяется пространством выборки , пространством событий и мерой вероятности . Используя для орла и для решки, пространство выборки монеты определяется как: ${\displaystyle (\Omega ,{\mathcal {F}},P)}$ ${\displaystyle H}$ ${\displaystyle T}$

$${\displaystyle \Omega =\{H,T\}}$$

Пространство событий для монеты включает все наборы результатов из выборочного пространства, которым может быть назначена вероятность, которая является полным набором мощности . Таким образом, пространство событий определяется как: ${\displaystyle 2^{\Omega }}$

$${\displaystyle {\mathcal {F}}=\{\{\},\{H\},\{T\},\{H,T\}\}}$$

${\displaystyle \{\}}$— это событие, при котором не происходит ни один из результатов (что невозможно и, следовательно, может иметь вероятность 0), и — это событие, при котором происходит любой из результатов (что гарантировано и может иметь вероятность 1). Поскольку монета честная, вероятность любого отдельного результата составляет 50-50. Тогда мера вероятности определяется функцией: ${\displaystyle \{H,T\}}$

Таким образом, полное вероятностное пространство, которое определяет честную монету, — это триплет, как определено выше. Обратите внимание, что это не случайная величина , поскольку орел и решка не имеют собственных числовых значений, которые вы могли бы найти на честной двузначной кости. Случайная величина добавляет дополнительную структуру присвоения числового значения каждому результату. Обычные варианты — или . ${\displaystyle (\Omega ,{\mathcal {F}},P)}$ ${\displaystyle (H,T)\to (1,0)}$ ${\displaystyle (H,T)\to (1,-1)}$

Роль в статистическом преподавании и теории

Вероятностные и статистические свойства игр с подбрасыванием монеты часто используются в качестве примеров как в вводных, так и в продвинутых учебниках, и они в основном основаны на предположении, что монета является честной или «идеальной». Например, Феллер использует эту основу для введения как идеи случайных блужданий , так и для разработки тестов на однородность в последовательности наблюдений, рассматривая свойства серий одинаковых значений в последовательности. ^[3] Последнее приводит к тесту на серии . Временной ряд, состоящий из результата подбрасывания честной монеты, называется процессом Бернулли .

Честные результаты от предвзятой монеты

Если мошенник изменил монету, чтобы предпочесть одну сторону другой (необъективная монета), монету все равно можно использовать для честных результатов, немного изменив игру. Джон фон Нейман дал следующую процедуру: ^[4]

1. Подбросьте монету дважды.
2. Если результаты совпадают, начните заново, забыв оба результата.
3. Если результаты различаются, используйте первый результат, забыв о втором.

Причина, по которой этот процесс дает справедливый результат, заключается в том, что вероятность выпадения орла, а затем решки должна быть такой же, как вероятность выпадения решки, а затем орла, поскольку монета не меняет своего смещения между подбрасываниями, и два подбрасывания независимы. Это работает только в том случае, если получение одного результата в испытании не меняет смещения в последующих испытаниях, что имеет место для большинства нековких монет (но не для таких процессов, как урна Пойя ). Исключая события двух орлов и двух решек путем повторения процедуры, подбрасывающий монету остается только с двумя оставшимися результатами, имеющими эквивалентную вероятность. Эта процедура работает только в том случае, если броски правильно парные; если часть пары повторно используется в другой паре, справедливость может быть нарушена. Кроме того, монета не должна быть настолько смещена, чтобы одна сторона имела вероятность, равную нулю .

Этот метод можно расширить, также рассмотрев последовательности из четырех бросков. То есть, если монета подбрасывается дважды, но результаты совпадают, и монета подбрасывается еще дважды, но результаты совпадают теперь уже для противоположной стороны, то можно использовать первый результат. Это потому, что HHTT и TTHH равновероятны. Это можно расширить до любого кратного 2.

Ожидаемое значение подбрасываний в n-й игре несложно вычислить, сначала обратите внимание, что на шаге 3, независимо от события , мы подбросили монету дважды, но на шаге 2 ( или ) нам также придется все переделать, так что у нас будет 2 подбрасывания плюс ожидаемое значение подбрасываний следующей игры, то есть, но поскольку мы начинаем заново, ожидаемое значение следующей игры такое же, как и значение предыдущей игры или любой другой игры, поэтому оно на самом деле не зависит от n, таким образом (это можно понять, поскольку процесс является мартингалом , где повторное взятие ожидания дает нам это, но из-за закона полного ожидания мы получаем это ), следовательно, у нас есть: ${\displaystyle E(F_{n})}$ ${\displaystyle HT}$ ${\displaystyle TH}$ ${\displaystyle E(F_{n}|HT,TH)=2}$ ${\displaystyle TT}$ ${\displaystyle HH}$ ${\displaystyle E(F_{n}|TT,HH)=2+E(F_{n+1})}$ ${\displaystyle E(F)=E(F_{n})=E(F_{n+1})}$ ${\displaystyle E(F_{n+1}|F_{n},...,F_{1})=F_{n}}$ ${\displaystyle E(E(F_{n+1}|F_{n},...,X_{1}))=E(F_{n})}$ ${\displaystyle E(F_{n+1})=E(E(F_{n+1}|F_{n},...,F_{1}))=E(F_{n})}$

График того, чем дальше от нас, тем больше ожидаемое количество подбрасываний до успешного результата ${\displaystyle {\frac {1}{P(H)(1-P(H))}}}$ ${\displaystyle P(H)}$ ${\displaystyle 0.5}$

${\displaystyle {\begin{aligned}E(F)&=E(F_{n})\\&=E(F_{n}|TT,HH)P(TT,HH)+E(F_{n}|HT,TH)P(HT,TH)\\&=(2+E(F_{n+1}))P(TT,HH)+2P(HT,TH)\\&=(2+E(F))P(TT,HH))+2P(HT,TH)\\&=(2+E(F))(P(TT)+P(HH))+2(P(HT)+P(TH))\\&=(2+E(F))(P(T)^{2}+P(H)^{2})+4P(H)P(T)\\&=(2+E(F))(1-2P(H)P(T))+4P(H)P(T)\\&=2+E(F)-2P(H)P(T)E(F)\\\end{aligned}}}$

${\displaystyle \therefore E(F)=2+E(F)-2P(H)P(T)E(F)\Rightarrow E(F)={\frac {1}{P(H)P(T)}}={\frac {1}{P(H)(1-P(H))}}}$

Чем более предвзята наша монета, тем больше вероятность, что нам придется провести большее количество испытаний, прежде чем будет получен справедливый результат.

Лучший алгоритм, когда P(H) известен

Предположим, что смещение известно. В этом разделе мы предоставим простой алгоритм ^[5] , который улучшает ожидаемое количество подбрасываний монеты. Алгоритм использует идеальную вероятность , которая Сначала рассмотрим алгоритм для генерации произвольной монеты со смещением . Чтобы получить честную монету, алгоритм сначала устанавливает , а затем выполняет следующий алгоритм. ${\displaystyle b:=P({\mathtt {H}})}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p=0.5}$

1. Подбросьте необъективную монету, и пусть будет результат. ${\displaystyle X\in \{{\mathtt {H}},{\mathtt {T}}\}}$
2. Если , используйте , если результат переворота . В противном случае замените на и вернитесь к шагу 1. ${\displaystyle p\geq b}$ ${\displaystyle {\mathtt {H}}}$ ${\displaystyle X={\mathtt {H}}}$ ${\displaystyle p}$ ${\displaystyle p\gets {\frac {p-b}{1-b}}}$
3. В противном случае , используйте, если результат переворота равен . В противном случае установите значение и вернитесь к шагу 1. ${\displaystyle p<b}$ ${\displaystyle {\mathtt {T}}}$ ${\displaystyle X={\mathtt {T}}}$ ${\displaystyle p}$ ${\displaystyle p\gets {\frac {p}{b}}}$

Обратите внимание, что приведенный выше алгоритм не достигает оптимального ожидаемого числа подбрасываний монеты, которое равно , вот бинарная функция энтропии . Существуют алгоритмы, которые достигают этого оптимального значения в ожидании. Однако эти алгоритмы более сложны, чем показанный выше. ${\displaystyle 1/H(b)}$ ${\displaystyle H(b)}$

Приведенный выше алгоритм имеет ожидаемое количество смещенных подбрасываний монеты , равное , что ровно вдвое меньше по сравнению с трюком фон Неймана. ${\displaystyle {\frac {1}{2b(1-b)}}}$

Анализ

Корректность вышеприведенного алгоритма является идеальным упражнением условного ожидания. Теперь проанализируем ожидаемое количество подбрасываний монеты.

Учитывая смещение и текущее значение , можно определить функцию , которая представляет ожидаемое количество подбрасываний монеты до возврата результата. Рекуррентное соотношение для можно описать следующим образом. ${\displaystyle b=P(H)}$ ${\displaystyle p}$ ${\displaystyle f_{b}(p)}$ ${\displaystyle f_{b}(p)}$

$${\displaystyle f_{b}(p)={\begin{cases}1+b\cdot f_{b}\left({\frac {p}{b}}\right)&{\text{if }}p<b\\1+(1-b)\cdot f_{b}\left({\frac {p-b}{1-b}}\right)&{\text{if }}p\geq b\end{cases}}}$$

Это волшебным образом приводит к следующей функции:

$${\displaystyle f_{b}(p)={\frac {b+(1-2b)p}{b(1-b)}}}$$

Когда , ожидаемое количество подбрасываний монеты равно желаемому. ${\displaystyle p=0.5}$ ${\displaystyle f_{b}(0.5)={\frac {1}{2b(1-b)}}}$

Замечание

Идею этого алгоритма можно расширить для генерации любой несимметричной монеты с заданной вероятностью.

Смотрите также

• Проверка честности монеты
• Подбрасывание монеты
• Константы Феллера для подбрасывания монеты

Ссылки

1. Керрич, Джон Эдмунд (1946). Экспериментальное введение в теорию вероятностей . Э. Манксгаард.
2. Джейнс, ET (2003). Теория вероятностей: логика науки. Кембридж, Великобритания: Cambridge University Press. стр. 318. ISBN 9780521592710. Архивировано из оригинала 2002-02-05. любой, кто знаком с законом сохранения момента импульса, может, после некоторой практики, жульничать в обычной игре в подбрасывание монеты и делать броски со 100-процентной точностью. Вы можете получить любую частоту выпадения орла, какую захотите; и смещение монеты вообще не оказывает влияния на результаты!{{cite book}}: CS1 maint: bot: original URL status unknown (link)
3. Феллер, В. (1968). Введение в теорию вероятностей и ее приложения . Wiley. ISBN 978-0-471-25708-0.
4. фон Нейман, Джон (1951). «Различные методы, используемые в связи со случайными цифрами». Серия «Прикладная математика» Национального бюро стандартов . 12 : 36.
5. Генри Цай, 12 апреля 2024 г.

Дальнейшее чтение

• Гельман, Эндрю; Дебора Нолан (2002). «Уголок учителя: можно подставить кубик, но нельзя подставить монету». American Statistician . 56 (4): 308–311. doi :10.1198/000313002605.Доступно на сайте Эндрю Гельмана
• «Пожизненный разоблачитель бросает вызов арбитру нейтрального выбора: фокусник, ставший математиком, раскрывает предвзятость в подбрасывании монеты». Стэнфордский отчет . 2004-06-07 . Получено 2008-03-05 .
• Джон фон Нейман, «Различные методы, используемые в связи со случайными цифрами», в книге под ред. А. С. Хаусхолдера, Г. Е. Форсайта и Х. Х. Джермонда « Метод Монте-Карло» , Серия «Прикладная математика» Национального бюро стандартов, 12 (Вашингтон, округ Колумбия: Типография правительства США, 1951): 36-38.