Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).
Вопросы о долгосрочном поведении случайных последовательностей — «случится ли это ещё бесконечно много раз?», «прекратятся ли когда-нибудь сбои?», «сойдётся ли ряд?» — имеют неожиданное свойство: их вероятности почти никогда не бывают «средними». Ответ, как правило, — либо \(0\), либо \(1\), и эта тема — про два инструмента, вычисляющих, какой именно. Лемма Бореля–Кантелли — рабочий счётный критерий («сложи вероятности и посмотри, сходится ли ряд»); закон нуля–единицы Колмогорова — структурная причина, по которой промежуточных ответов не бывает. Практический смысл прямой: «событие с положительной вероятностью в независимых повторениях произойдёт п.н., причём бесконечно часто» — это математика надёжности (любой сбой с ненулевой вероятностью будет происходить регулярно — вопрос лишь в частоте), криптографии (случайный перебор рано или поздно наткнётся на коллизию) и фольклорной «обезьяны с пишущей машинкой».
Лемма Бореля–Кантелли
Определение 1 Для последовательности событий \(A_1, A_2, \ldots\) \[
\limsup _n A_n := \bigcap _{n=1}^\infty \bigcup _{k \geq n} A_k = \left\{ \text{произошло бесконечно много из } A_n\right\} =: \left\{ A_n \text{ б.ч.}\right\}
\] (б.ч. — «бесконечно часто»); двойственно, \(\liminf_n A_n = \left\{ \text{все } A_n, \text{ кроме конечного числа}\right\}\).
Интерактивная иллюстрация ещё не создана. См. исходник: /home/nedosh/Documents/online_math_notes/math-notes_FPMI_2/courses/nedosh_courses/courses/04-probability/02_PT/contents/specials/050/01_infinitely_often_fig.tex.
Теорема 1 (Борель–Кантелли)
Если \(\sum_{n} \mathbb {P}\left(A_n\right) < \infty\), то \(\mathbb {P}\left(A_n \text{ б.ч.}\right) = 0\).
Если события \(A_n\) независимы и \(\sum_{n} \mathbb {P}\left(A_n\right) = \infty\), то \(\mathbb {P}\left(A_n \text{ б.ч.}\right) = 1\).
Обе части — по строчке. (1): \(\mathbb {P}\left(\limsup A_n\right) \leq \mathbb {P}\left(\bigcup_{k \geq n} A_k\right) \leq \sum_{k \geq n} \mathbb {P}\left(A_k\right) \to 0\) как хвост сходящегося ряда. (2): по независимости и неравенству \(1 - x \leq e^{-x}\)
\[
\mathbb {P}\left(\bigcap _{k=n}^{N} A_k^\complement \right) = \prod _{k=n}^N \left(1 - \mathbb {P}\left(A_k\right)\right) \leq \exp \left(-\sum _{k=n}^N \mathbb {P}\left(A_k\right)\right) \xrightarrow [N \to \infty ]{} 0,
\]
поэтому \(\mathbb {P}\left(\bigcup_{k \geq n} A_k\right) = 1\) при каждом \(n\), и пересечение по \(n\) тоже имеет вероятность \(1\).
Первая часть не требует никакой независимости — это чистая теория меры, и потому она безотказна: подавляющее большинство доказательств сходимости п.н.в этом курсе и в курсе СП устроено как «оценили \(\mathbb {P}\left(\left|\xi_n - \xi \right| > \varepsilon \right)\) суммируемой последовательностью — применили Бореля–Кантелли»:
Следствие 1 Если \(\sum_n \mathbb {P}\left(\left|\xi_n - \xi \right| > \varepsilon \right) < \infty\) для каждого \(\varepsilon > 0\), то \(\xi_n \to \xi\) п.н.
Во второй части независимость существенна: возьмите один бросок монеты и \(A_n \equiv A = \left\{ \text{орёл}\right\}\) — ряд расходится, но \(\mathbb {P}\left(A_n \text{ б.ч.}\right) = \mathbb {P}\left(A\right) = \frac12\).
Обезьяна вечно и независимо нажимает равновероятные клавиши (алфавит из \(K\) символов). Докажите, что с вероятностью \(1\) она напечатает полный текст «Войны и мира» (строку длины \(L\)), причём бесконечно много раз.
Разобьём поток нажатий на непересекающиеся блоки длины \(L\): нажатия \(1, \ldots , L\), затем \(L+1, \ldots , 2L\) и т.д. Пусть \(A_n\) — событие «\(n\)-й блок в точности совпал с текстом романа». Блоки не пересекаются, поэтому события \(A_n\) независимы, и \(\mathbb {P}\left(A_n\right) = K^{-L} > 0\) — чудовищно мало, но одинаково для всех \(n\), так что \(\sum_n \mathbb {P}\left(A_n\right) = \infty\). По второй части Бореля–Кантелли \(\mathbb {P}\left(A_n \text{ б.ч.}\right) = 1\).
Приём «нарезать на независимые блоки» — главный трюк применений БК2: сами по себе события «текст начинается с позиции \(t\)» зависимы (перекрываются), а по блокам независимость честная. Инженерная мораль без иронии: в достаточно длинной серии испытаний любое событие положительной вероятности гарантированно происходит — редкие сбои не «может быть, случатся», а случатся наверняка, и проектировать систему надо исходя из этого.
Пусть \(\xi , \xi_1, \xi_2, \ldots\) — независимые одинаково распределённые величины. Докажите:
если \(\mathbb {E}\left[\left|\xi \right|\right] < \infty\), то \(\frac{\xi_n}{n} \to 0\) п.н.;
если \(\mathbb {E}\left[\left|\xi \right|\right] = \infty\), то \(\limsup_n \frac{\left|\xi_n\right|}{n} = \infty\) п.н.
Пусть \(\left\{ \xi_{n}\right\}\) — произвольная (без всяких предположений!) последовательность случайных величин. Докажите, что найдётся неслучайная последовательность \(a_{n} > 0\), для которой \(\frac{\xi_{n}}{a_{n}} \to 0\) почти наверное.
Бросается симметричная монета. Докажите, что для любого \(k \in \mathbb {N}\) серия из \(k\) орлов подряд появится бесконечно много раз п.н. Более того, покажите, что серии длины \(\lfloor \log_2 n \rfloor\), начинающиеся не позже броска \(n\), появляются б.ч. (т.е. рекорды длины серий растут логарифмически).
Закон нуля–единицы
Определение 2 Пусть \(\xi_1, \xi_2, \ldots\) — последовательность случайных величин. Хвостовая \(\sigma\)-алгебра — \[
\mathcal{T} = \bigcap _{n=1}^{\infty } \sigma \left(\xi _n, \xi _{n+1}, \ldots \right).
\] Хвостовые события — те, что не зависят ни от какого конечного набора первых членов: сходимость ряда \(\sum \xi_n\), сходимость \(\frac{S_n}{n}\), конечность \(\limsup \xi_n\), «\(A_n\) бесконечно часто» и т.п.
Теорема 2 (закон нуля–единицы Колмогорова) Если \(\xi_1, \xi_2, \ldots\) независимы, то любое хвостовое событие имеет вероятность \(0\) или \(1\).
Идея доказательства изящна: хвостовое событие \(A\) не зависит от \(\sigma (\xi_1, \ldots , \xi_n)\) при каждом \(n\) (оно лежит в \(\sigma\)-алгебре «хвоста»); по критерию через \(\pi\)-системы (тема 1!) \(A\) не зависит и от \(\sigma (\xi_1, \xi_2, \ldots )\) — но \(A\) само лежит в этой \(\sigma\)-алгебре. Событие, независимое от самого себя: \(\mathbb {P}\left(A\right) = \mathbb {P}\left(A \cap A\right) = \mathbb {P}\left(A\right)^2\), откуда \(\mathbb {P}\left(A\right) \in \left\{ 0, 1\right\}\). \(\blacksquare\)
Закон объясняет «поляризацию» всех наших вопросов: у случайного ряда из независимых слагаемых нет сценария «сходится с вероятностью \(\frac13\)». Но он не говорит, какая из двух альтернатив верна — это выясняют конкретные критерии. Для рядов ответ даёт (факультативно, формулировка):
Теорема 3 (Колмогорова о трёх рядах) Пусть \(\xi_n\) независимы, \(c > 0\), \(\xi_n^c := \xi_n \; \mathbb {1}_{\left|\xi_n\right| \leq c}\). Ряд \(\sum_n \xi_n\) сходится п.н.тогда и только тогда, когда сходятся все три числовых ряда: \[
\sum _n \mathbb {P}\left(\left|\xi _n\right| > c\right), \qquad \sum _n \mathbb {E}\left[\xi _n^c\right], \qquad \sum _n \operatorname {Var}\left[\xi _n^c\right].
\]
Пусть \(\xi_1, \xi_2, \ldots\) независимы. Какие из следующих событий — хвостовые: (а) \(\left\{ \sum_n \xi_n \text{ сходится}\right\}\); (б) \(\left\{ \limsup_n \frac{S_n}{n} > 1\right\}\), где \(S_n = \xi_1 + \ldots + \xi_n\); (в) \(\left\{ \sum_n \xi_n > 1\right\}\); (г) \(\left\{ \xi_n > 0 \text{ б.ч.}\right\}\)? Для хвостовых сделайте вывод о вероятности.
(Случайные знаки.) Пусть \(\varepsilon_1, \varepsilon_2, \ldots\) независимы, \(\mathbb {P}\left(\varepsilon_n = \pm 1\right) = \frac12\). Докажите, что событие \(A = \left\{ \sum_n \frac{\varepsilon_n}{n} \text{ сходится}\right\}\) имеет вероятность \(0\) или \(1\), и определите, какую именно (можно использовать теорему о трёх рядах или дождаться темы 6).