Решение задачи 498

Условие:

Дано вещественное число p из отрезка [0;1]. С помощью симметричной монетки реализовать вероятность p.

Решение:

Представим число p в виде двоичной дроби. Например, 5/8 = 0, 101. Конечно, дробь может получиться бесконечной длины. В любом случае, мы представляем число p в виде суммы (возможно, бесконечной) целых степеней 1/2.

Реализуем для примера вероятность 41 / 64 = 1/2 + 1/8 + 1/64. Выпишем вектор степеней в порядке возрастания: (1, 3, 6). Реализуем следующий процесс:

1) Подрасываем монетку один раз, если выпал орел, то заканчиваем процесс с успехом, иначе подбрасываем монетку еще два раза (3 − 1)

2) Если выпали два орла, то заканчиваем процесс с успехом. Если выпали два орла, бросаем еще три (6 − 3) раза, иначе заканчиваем процесс с неуспехом.

3) Если выпали три орла, то заканчиваем процесс с упехом, иначае заканчиваем процесс с неуспехом.

Для наглядности представим наш процесс в виде схемы:

Галочкам обозначены успешные исходы

Какая вероятность закончить процесс с успехом? Есть три пути (три способа дойти до галочек), посчитаем вероятности каждого.

1) Вероятность первой галочки одна вторая (вероятность что выпал орел)

2) Вероятность второй галочки: сначала должна выпасть решка, потом два раза орел, то есть 1/2 ∙ 1/4 = 1/8

3) Вероятность третьей галочки: сначала должна выпасть решка, потом два раза орел, потом три раза орел: 1/2 ∙ 1/4 ∙ 1/8 = 1/64

Суммируя все вероятности, получаем 1/2 + 1/4 + 1/64 = 41/64, что и требовалось.

Два замечания:

1) мы заканчиваем процесс, только когда выпали все орлы при очередном бросании

2) продолжаем бросать только когда выпали все решки при очередном бросании

Как же все-таки реализовать "страшную" вероятность, например p = ln(10) / 10?

Переводим число в двоичную дробь: p = 0, 10001100011000.... Пусть d = (d1, d2, ...) — вектор степений, или, говоря по-другому, номера позиций, на которых стоят единички.

Итак, наши действия:

1) Кидаем монетку d1 раз, если выпали все орлы, то заканчиваем процесс с успехом. Если выпали все решки, то подбрасываем еще d2−d1 раз. Иначе заканчиваем процесс с неуспехом.

2) Если выпали все орлы, то заканчиваем процесс с успехом. Если выпали все решки, то подбрасываем еще d3−d2 раз. Иначе заканчиваем процесс с неуспехом

3) и так далее

Может ли процесс продолжаться бесконечно? Нет, потому что вероятность такого события равна пределу 1/2^n, при n стремящемуся к бесконечности, то есть нулю.