Честная монета: теория вероятностей

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

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

Джон Эдмунд Керрич (John Edmund Kerrich) провёл эксперименты по бросанию монеты и обнаружил, что монета, изготовленная из деревянного диска размером примерно с корону и покрытая свинцом с одной стороны, выпадала орлом (деревянной стороной вверх) 679 раз из 1000. В этом эксперименте монета подбрасывалась путём балансирования её на указательном пальце, а затем отбрасывалась большим пальцем так, чтобы она вращалась в воздухе примерно на расстояние фута, прежде чем приземлиться на плоскую ткань, расстеленную на столе. Эдвин Томпсон Джейнс (Edwin Thompson Jaynes) утверждал, что когда монета ловится в руке вместо того, чтобы отскакивать, физическое смещение монеты незначительно по сравнению с методом броска, и при достаточной практике монету можно заставить выпадать орлом в 100% случаев. Проверка того, является ли монета честной, — это хорошо зарекомендовавший себя педагогический инструмент в преподавании статистики.

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

В теории вероятностей честная монета определяется как вероятностное пространство, которое в свою очередь определяется пространством элементарных исходов, пространством событий и вероятностной мерой. Используя О для орла и Р для решки, пространство элементарных исходов монеты определяется как:

Ω = {О, Р}

Пространство событий для монеты включает все подмножества исходов из пространства элементарных исходов, которым можно приписать вероятность, то есть полный набор всех подмножеств. Таким образом, пространство событий определяется как:

F = {{}, {О}, {Р}, {О, Р}}

{} — это событие, при котором ни один из исходов не происходит (что невозможно и поэтому может быть приписано вероятность 0), а {О, Р} — это событие, при котором происходит один из исходов (что гарантировано и может быть приписано вероятность 1). Поскольку монета честная, вероятность каждого отдельного исхода составляет 50 на 50. Вероятностная мера определяется функцией:

P(О) = 1/2, P(Р) = 1/2

Таким образом, полное вероятностное пространство, определяющее честную монету, — это тройка (Ω, F, P), как определено выше. Заметим, что это не случайная величина, поскольку орёл и решка не имеют собственных числовых значений, как вы могли бы найти на честной двузначной кости. Случайная величина добавляет дополнительную структуру, присваивая числовое значение каждому исходу. Обычные выборы — это (О, Р) → (1, 0) или (О, Р) → (1, −1).

Роль в статистическом обучении и теории

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

Честные результаты из смещённой монеты

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

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

Причина, по которой эта процедура даёт честный результат, заключается в том, что вероятность получить сначала орла, а затем решку должна быть такой же, как вероятность получить сначала решку, а затем орла, поскольку монета не меняет своё смещение между бросками и два броска независимы. Это работает только в том случае, если получение одного результата в одном испытании не изменяет смещение в последующих испытаниях, что верно для большинства немягких монет (но не для процессов, таких как урна Пойа (Pólya urn)). Исключая события двух орлов и двух решек путём повторения процедуры, бросающий монету остаётся с единственными двумя оставшимися исходами, имеющими эквивалентную вероятность. Эта процедура работает только в том случае, если броски правильно спарены; если часть одной пары используется в другой паре, честность может быть нарушена. Кроме того, монета не должна быть настолько смещённой, чтобы одна сторона имела вероятность нуль. Эдсгер Дейкстра (Edsger W. Dijkstra) писал о процессе:

Создание честной «физической» монеты довольно сложно, потому что как установить, что у вас она есть? Вы не можете её протестировать. Здесь у нас есть «математическая» монета, которая честна по построению! Два ура математике.

— Эдсгер Дейкстра, EWD-1069

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

Ожидаемое значение количества бросков в игре n не сложно вычислить. Сначала заметим, что на шаге 3, независимо от того, какое событие произойдёт (ОР или РО), мы подбросили монету дважды, поэтому ожидаемое значение равно 2. Но на шаге 2 (РР или ОО) нам также нужно повторить процедуру, поэтому у нас будет 2 броска плюс ожидаемое значение бросков следующей игры. Однако, поскольку мы начинаем заново, ожидаемое значение следующей игры такое же, как и предыдущей игры или любой другой игры, поэтому оно не зависит от n. Следовательно:

E(F) = (2 + E(F)) · P(РР или ОО) + 2 · P(ОР или РО)

Решая это уравнение:

E(F) = 1 / (P(О) · P(Р))

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

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

Предположим, что смещение b := P(О) известно. В этом разделе мы предоставляем простой алгоритм, который улучшает ожидаемое количество бросков монеты. Алгоритм позволяет имитировать монету с любой вероятностью p, и значение p изменяется внутри на протяжении итераций. Чтобы получить честную монету, алгоритм сначала устанавливает p = 0,5, а затем выполняет следующие шаги:

• Подбросьте смещённую монету. Пусть X ∈ {О, Р} — результат.
• Если p ≥ b, используйте О, если результат броска X = О. В противном случае установите p на (p − b) / (1 − b) и вернитесь к шагу 1.
• В противном случае, если p < b, используйте Р, если результат броска X = Р. В противном случае установите p на p / b и вернитесь к шагу 1.

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

Приведённый выше алгоритм имеет ожидаемое количество бросков смещённой монеты, равное 1 / (2b(1 − b)), что ровно в два раза меньше, чем ожидаемое количество бросков для подхода фон Неймана.

Анализ

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

Учитывая смещение b = P(О) и текущее значение p, можно определить функцию f_b(p), которая представляет ожидаемое количество бросков монеты перед возвращением результата. Рекуррентное соотношение f_b(p) можно описать следующим образом:

f_b(p) = {

1 + b · f_b(p/b), если p < b

1 + (1−b) · f_b((p−b)/(1−b)), если p ≥ b

}

Это решается в следующую функцию:

f_b(p) = (b + (1 − 2b)p) / (b(1 − b))

Когда p = 0,5, ожидаемое количество бросков монеты равно f_b(0,5) = 1 / (2b(1 − b)), как и требовалось.