1000 бросков монеты без двух орлов подряд: вероятность F₁₀₀₂/2¹⁰⁰⁰ ≈ 1,06·10⁻⁹²

Условие

Пьер Ферма подкидывает правильную монетку 1000 раз.

а) Какова вероятность того, что ни разу не выпадет два орла подряд?

б) При чём тут числа Фибоначчи?

Решение источника

Источник приводит только ответ F₁₀₀₀/2¹⁰⁰⁰, без вывода и без указания, как нумеруются числа Фибоначчи.

Редакционное объяснение

Все 2¹⁰⁰⁰ последовательностей орлов и решек равновероятны, поэтому нужно посчитать допустимые последовательности. Пусть a_n — число последовательностей длины n без двух орлов подряд. Если последний бросок — решка, перед ней может стоять любая допустимая последовательность длины n−1. Если последний бросок — орёл, перед ним обязана стоять решка, а перед ней — любая допустимая последовательность длины n−2. Значит,

a_n=a_n−1+a_n−2, a₁=2, a₂=3.

Это рекуррентное соотношение Фибоначчи — ответ на пункт б). При стандартной нумерации F₁=F₂=1, F₃=2, F₄=3 получаем a_n=F_n+2, поэтому

P=F₁₀₀₂/2¹⁰⁰⁰≈1,06·10⁻⁹².

Исправление. При стандартной нумерации ответ источника F₁₀₀₀/2¹⁰⁰⁰ занижен в F₁₀₀₂/F₁₀₀₀≈φ²≈2,618 раза, где φ=(1+√5)/2. Индекс 1000 верен только при нумерации со сдвигом, когда F_n само означает число допустимых последовательностей длины n (F₀=1, F₁=2, F₂=3, …).

Численное значение: по формуле Бине F_k≈φ^k/√5, так что P≈φ¹⁰⁰²/(√5·2¹⁰⁰⁰), и log₁₀P≈−91,974. Точный расчёт с длинными целыми числами даёт то же значение. Вероятность убывает примерно как (φ/2)ⁿ≈0,809ⁿ.

Проверка на малых n (О — орёл, Р — решка): при n=1 вероятность 2/2=1; при n=2 — 3/4 (исключено только ОО); при n=3 — 5/8 (исключены ООО, ООР, РОО); при n=10 — 144/1024≈0,1406, моделирование 400 000 серий дало 0,1411. Полный перебор подтверждает a_n=F_n+2 для всех n от 1 до 15.

Что не следует из ответа

Это не вопрос о среднем времени ожидания двух орлов подряд: для правильной монеты оно равно 6 броскам. Здесь спрашивается, насколько маловероятно избежать такой пары на протяжении 1000 бросков, и ответ показывает, что это практически невозможно.

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

Борис Демешев и участники · probability_dna, задача «Пьер Ферма и два орла подряд» · Исходное задание и решение · CC BY 4.0. Адаптация: добавлен вывод рекуррентного соотношения; индекс в ответе источника исправлен на F₁₀₀₂ для стандартной нумерации F₁=F₂=1; добавлены численная оценка и проверки.