Парадокс Феллера

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

История

Парадокс был впервые сформулирован и проанализирован Уильямом Феллером в середине XX века. В своей работе Феллер исследовал свойства случайных последовательностей, в частности, время ожидания появления определённых комбинаций в бесконечной серии независимых испытаний Бернулли (например, подбрасываний симметричной монеты). Он обнаружил, что для последовательностей одинаковой длины, но с разной внутренней структурой (наличие перекрытий), среднее время ожидания может существенно различаться. Это открытие противоречило интуитивному представлению о том, что все последовательности из n символов должны появляться в среднем через одинаковое количество шагов.

Феллер опубликовал свои результаты в первом издании своей книги в 1950 году. Парадокс быстро привлёк внимание математиков и статистиков, став классическим примером того, как интуиция может подводить в теории вероятностей. Впоследствии парадокс был обобщён и применён в различных областях, включая теорию игр, анализ случайных процессов и даже в криптографии.

Формулировка парадокса

Рассмотрим подбрасывание симметричной монеты (орёл и решка выпадают с вероятностью 1/2). Пусть нас интересует время ожидания (количество подбрасываний) до первого появления одной из двух последовательностей длины 3: ОР-О (орёл, решка, орёл) и ОР-Р (орёл, решка, решка). Интуитивно кажется, что обе последовательности должны появляться в среднем за одинаковое количество шагов, так как вероятность выпадения каждой из них за три броска равна 1/8. Однако математический расчёт показывает, что среднее время ожидания для ОР-О составляет 10 бросков, а для ОР-Р — 8 бросков.

Причина различия

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

Формально, для последовательности ОР-О максимальное перекрытие составляет 2 символа (префикс «ОР» совпадает с суффиксом «ОР»), а для ОР-Р — 0 символов. Это приводит к тому, что при появлении «орла» после «решки» вероятность того, что следующим будет «орёл» (для ОР-О) или «решка» (для ОР-Р), одинакова, но в случае ОР-О неудачный бросок (выпадение решки после ОР-О) может быть частично использован для начала новой последовательности, в то время как для ОР-Р неудачный бросок (выпадение орла после ОР-Р) полностью сбрасывает процесс.

Математическое обоснование

Среднее время ожидания появления заданной последовательности в бесконечной серии независимых испытаний Бернулли можно вычислить с помощью метода, основанного на марковских цепях или на решении системы линейных уравнений. Для последовательности длины n из символов с вероятностью p для одного исхода и q=1-p для другого, среднее время ожидания E выражается через автокорреляционную функцию последовательности.

Для симметричной монеты (p=q=1/2) среднее время ожидания для последовательности S можно вычислить по формуле:

E(S) = 2^n * (1 + сумма по всем k от 1 до n-1, где префикс длины k совпадает с суффиксом длины k, 2^k)

Для последовательности ОР-О (n=3) префикс длины 1 («О») не совпадает с суффиксом длины 1 («О»), префикс длины 2 («ОР») совпадает с суффиксом длины 2 («ОР»). Таким образом:

E(ОР-О) = 2^3 (1 + 2^2) = 8 (1 + 4) = 8 * 5 = 40?

Ошибка в расчёте. Правильная формула для среднего времени ожидания с учётом перекрытий:

E(S) = 2^n * (1 + сумма по всем k от 1 до n-1, где префикс длины k совпадает с суффиксом длины k, 2^k)

Для ОР-О: n=3, префикс длины 1 («О») совпадает с суффиксом длины 1 («О»)? Нет, суффикс длины 1 — это последний символ «О», префикс длины 1 — первый символ «О». Они совпадают. Префикс длины 2 («ОР») совпадает с суффиксом длины 2 («ОР»). Таким образом:

E(ОР-О) = 2^3 (1 + 2^1 + 2^2) = 8 (1 + 2 + 4) = 8 * 7 = 56?

Это неверно. Правильный расчёт для ОР-О даёт 10, для ОР-Р — 8. Формула, используемая в литературе, иная. Более точный метод — решение системы уравнений для марковской цепи. Для ОР-О среднее время ожидания равно 10, для ОР-Р — 8. Эти значения подтверждаются как аналитически, так и численным моделированием.

Пример расчёта для ОР-Р

Для последовательности ОР-Р (без самоперекрытий) среднее время ожидания можно вычислить проще. Пусть E — среднее время ожидания. Рассмотрим первый бросок. Если выпадает решка (вероятность 1/2), то процесс начинается заново, и ожидаемое время увеличивается на 1 + E. Если выпадает орёл (вероятность 1/2), то переходим к ожиданию следующего символа. Аналогично, для второго и третьего бросков. Решение системы даёт E=8.

Для ОР-О (с самоперекрытием) решение сложнее, но результат E=10.

Примеры и иллюстрации

Игра в казино

Парадокс Феллера можно проиллюстрировать на примере игры в казино, где игроки делают ставки на появление определённых последовательностей при подбрасывании монеты. Если два игрока выбирают разные последовательности, один из них может иметь преимущество за счёт разницы в среднем времени ожидания. Например, игрок, выбравший ОР-Р, будет в среднем выигрывать быстрее, чем игрок, выбравший ОР-О, при прочих равных условиях.

Соревнование последовательностей

Рассмотрим соревнование между последовательностями ОР-О и ОР-Р. Если обе последовательности «стартуют» одновременно, то вероятность того, что ОР-Р появится раньше, составляет 3/4, а ОР-О — 1/4. Это также является следствием парадокса.

Другие примеры

Парадокс Феллера проявляется не только для последовательностей длины 3, но и для более длинных. Например, для последовательностей длины 4: ОР-О-Р (среднее время ожидания 20) и ОР-Р-Р (среднее время ожидания 16). Разница обусловлена разной степенью самоперекрываемости.

Критика и обсуждение

Парадокс Феллера часто воспринимается как контр-интуитивный, что приводит к его активному обсуждению в учебной литературе. Некоторые критики утверждают, что парадокс не является парадоксом в строгом смысле, а лишь демонстрирует неочевидные свойства случайных процессов. Однако большинство математиков признают его важность для понимания теории вероятностей и её приложений.

Парадокс также имеет практическое значение в таких областях, как:

• Теория игр: анализ оптимальных стратегий в играх с последовательными ставками.
• Биоинформатика: поиск паттернов в генетических последовательностях.
• Криптография: анализ случайных последовательностей и генераторов псевдослучайных чисел.

Интересные факты

• Парадокс Феллера иногда называют «парадоксом времени ожидания» или «парадоксом последовательностей».
• В русскоязычной литературе парадокс также известен как «парадокс Феллера о времени ожидания».
• Уильям Феллер (1906–1970) был хорватско-американским математиком, внёсшим значительный вклад в теорию вероятностей.

Источники

• Феллер В. «Введение в теорию вероятностей и её приложения». Том 1. — М.: Мир, 1967.
• Гнеденко Б. В. «Курс теории вероятностей». — М.: Наука, 1988.
• Ширяев А. Н. «Вероятность». — М.: Наука, 1989.