Закон больших чисел

Покажите, что $Z_{n} \rightarrow Z$ с вероятностью 1 тогда и только тогда, когда для каждого положительного $\epsilon$ существует такое $n$, что $P\left[\left|Z_{k}-Z\right|<\epsilon , n \leq k \leq m\right]>1-\epsilon$ для всех $m$, превосходящих $n$. Это описывает сходимость с вероятностью 1 в «конечных» терминах.

Покажите в условиях Примера 6.3, что $P\left[\left|S_{n}-L_{n}\right| \geq L_{n}^{1 / 2+\epsilon }\right] \rightarrow 0$.

Как и в Примерах 5.6 и 6.3, пусть $\omega$ — случайная перестановка чисел $1,2, \ldots , n$ Каждое $k, 1 \leq k \leq n$, занимает некоторую позицию в нижней строке перестановки $\omega$; пусть $X_{n k}(\omega )$ — число меньших элементов (от 1 до $k-1$) лежащих справа от $k$ в нижней строке. Сумма $S_{n}=X_{n 1}+\cdots +X_{n n}$ — это общее число инверсий, то есть число пар, встречающихся в нижней строке в обратном по величине порядке. Для перестановки из Примера 5.6 значения $X_{71}, \ldots , X_{77}$ равны $0,0,0,2,4,2,4$, а $S_{7}=12$. Покажите, что $X_{n 1}, \ldots , X_{n n}$ независимы и $P\left[X_{n k}=i\right]=k^{-1}$ для $0 \leq i<k$. Вычислите $E\left[S_{n}\right]$ и $\operatorname {Var}\left[S_{n}\right]$. Покажите, что $S_{n}$, скорее всего, близко к $n^{2} / 4$.

Для функции $f$ на $[0,1]$ обозначим $\left\| f\right\| =\sup_{x}\left|f(x)\right|$. Покажите, что если $f$ имеет непрерывную производную $f^{\prime }$, то $\left\| f-B_{n}\right\| \leq \epsilon \left\| f^{\prime }\right\| +2\left\| f\right\| / n \epsilon^{2}$. Заключите, что $\left\| f-B_{n}\right\| =O\left(n^{-1 / 3}\right)$.

Докажите теорему Пуассона: если $A_{1}, A_{2}, \ldots$ — независимые события, $\bar{p}_{n}= n^{-1} \sum_{i=1}^{n} P\left(A_{i}\right)$, и $N=\sum_{t=1}^{n} I_{A}$, то $n^{-1} N_{n}-\bar{p}_{n} \rightarrow_{P} 0$.

В последующих задачах $S_{n}=X_{\mathrm{i}}+\cdots +X_{n}$

Докажите теорему Кантелли. Если $X_{1}, X_{2}, \ldots$ независимы, $E\left[X_{n}\right]=0$, и $E\left[X_{n}^{4}\right]$ ограничены, то $n^{-1} S_{n} \rightarrow 0$ с вероятностью 1. Величины $X_{n}$ не обязаны быть одинаково распределены

$\uparrow$ Предположим, что $X_{1}, X_{2}, \ldots$ независимы, равномерно ограничены и $E\left[X_{n}\right]=0$. Используя только предыдущий результат, первую лемму Бореля—Кантелли и неравенство Чебышева, докажите, что $n^{-1} S_{n} \rightarrow 0$ с вероятностью 1.

↑ Используя идеи Задачи 6.8, дайте новое доказательство теоремы Бореля о нормальных числах, Теоремы 1.2. Смысл в том, чтобы вернуться к первоначальным принципам и использовать только пренебрежимость и другие идеи Раздела 1, а не аппарат Разделов 2–6; в частности, $P(A)$ следует считать определённой, только если $A$ — конечное объединение непересекающихся интервалов.

$5.116 .7 \uparrow$ Предположим, что (в обозначениях (5.41)) $\beta_{n}-\alpha_{n}^{2}=O(1 / n)$. Покажите, что $n^{-1} N_{n}-\alpha_{n} \rightarrow 0$ с вероятностью 1. Какое условие на $\beta_{n}-\alpha_{n}^{2}$ обеспечит выполнение слабого закона? Заметим, что независимость здесь не предполагается.

Предположим, что $X_{1}, X_{2}, \ldots$ являются $m$-зависимыми в том смысле, что случайные величины, отстоящие в последовательности более чем на $m$, независимы. Точнее, пусть $\mathscr {A}_{j}^{k}=\sigma \left(X_{j}, \ldots , X_{k}\right)$, и предположим, что $\mathscr {A}_{j_{1}}^{k_{1}}, \ldots , \mathscr {A}_{j_{l}}^{k_{l}}$ независимы, если $k_{i-1}+ m<j_{i}$ для $i=2, \ldots , l$. (Независимые случайные величины являются 0-зависимыми.) Предположим, что $X_{n}$ обладают этим свойством, равномерно ограничены и $E\left[X_{n}\right]=0$. Покажите, что $n^{-1} S_{n} \rightarrow 0$. Указание: рассмотрите подпоследовательности $X_{i}, X_{i+m+1}, X_{i+2(m+1)}$, для $1 \leq i \leq m+1$.

$\uparrow$ Предположим, что $X_{n}$ независимы и принимают значения $x_{1}, \ldots , x$, с вероятностями $p\left(x_{1}\right), \ldots , p\left(x_{1}\right)$. Для $k$-набора $u_{1}, \ldots , u_{k}$ значений $x_{i}$ пусть $N_{n}\left(u_{1}, \ldots , u_{k}\right)$ — частота этого $k$-набора среди первых $n+k-1$ испытаний, то есть число таких $t$, что $1 \leq t \leq n$ и $X_{1}=u_{1}, \ldots , X_{1+k-1}=u_{k}$. Покажите, что с вероятностью 1 все асимптотические относительные частоты таковы, какими должны быть, то есть с вероятностью $1, n^{-1} N_{n}\left(u_{1}, \ldots , u_{k}\right) \rightarrow p\left(u_{1}\right) \cdots p\left(u_{k}\right)$ для каждого $k$ и каждого $k$-набора $u_{1}, \ldots , u_{k}$.

↑ Число $\omega$ из единичного интервала называется вполне нормальным, если для каждого основания $b$, каждого $k$ и каждого $k$-набора цифр по основанию $b$ этот $k$-набор встречается в разложении $\omega$ по основанию $b$ с асимптотической относительной частотой $b^{-k}$. Покажите, что множество вполне нормальных чисел имеет меру Лебега 1.

Теорема Шеннона. Предположим, что $X_{1}, X_{2}, \ldots$ — независимые, одинаково распределённые случайные величины, принимающие значения $1, \ldots , r$ с положительными вероятностями $p_{1}, \ldots , p_{r}$ Если $p_{n}\left(i_{1}, \ldots , i_{n}\right)=p_{i_{1}} \ldots p_{i_{n}}$ и $p_{n}(\omega )=p_{n}\left(X_{1}(\omega ), \ldots X_{n}(\omega )\right)$, то $p_{n}(\omega )$ — это вероятность того, что новая серия из $n$ испытаний даст ту самую последовательность исходов $X_{1}(\omega ), \ldots , X_{n}(\omega )$, которая фактически была уже получена. Покажите, что

с вероятностью 1. В теории информации $1, \ldots , r$ интерпретируются как буквы алфавита, $X_{1}, X_{2}, \ldots$ — последовательные буквы, порождаемые источником информации, а $h$ — энтропия источника. Докажите свойство асимптотической равнораспределённости: при больших $n$ с вероятностью, превышающей $1-\epsilon$, вероятность $p_{n}(\omega )$ наблюдаемой последовательности длины $n$, то есть сообщения, лежит в диапазоне $e^{-n(h \pm \epsilon )}$.

В терминологии Примера 6.5 покажите, что $\log_{2} n+\log_{2} \log_{2} n+ \theta \log_{2} \log_{2} \log_{2} n$ является внешней или внутренней границей в зависимости от того, $\theta >1$ или $\theta \leq 1$. Обобщите. (Сравните с Задачей 4.12.)

$5.20 \uparrow$ Пусть $g(m)=\sum_{p} \delta_{p}(m)$ — число различных простых делителей числа $m$. Для $a_{n}=E_{n}[g]$ (см. (5.46)) покажите, что $a_{n} \rightarrow \infty$. Покажите, что

для $p \neq q$, и, следовательно, что дисперсия $g$ относительно $P_{n}$ удовлетворяет

Докажите теорему Харди—Рамануджана:

Поскольку $a_{n} \sim \log \log n$ (см. Задачу 18.17), у большинства целых чисел, меньших $n$, число различных простых делителей — величина порядка $\log \log n$. Поскольку $\log \log 10^{7}$ немного меньше 3, типичное целое число, меньшее $10^{7}$, имеет около трёх простых делителей — удивительно мало.

Предположим, что $X_{1}, X_{2}, \ldots$ независимы и $P\left[X_{n}=0\right]=p$. Пусть $L_{n}$ — длина серии нулей, начинающейся в $n$-й позиции: $L_{n}=k$, если $X_{n}=\cdots =X_{n+k-1} =0 \neq X_{n+k}$. Покажите, что $P\left[L_{n} \geq r_{n}\right.$ б.ч. $]$ равно 0 или 1 в зависимости от того, сходится или расходится $\sum_{n} p^{r_{n}}$. Пример 6.5 охватывает случай $p=\frac{1}{2}$.