§4. Счастливый билетик и возвращение блуждания

Математика — дело настолько серьёзное, что ей всегда нужно немножко занимательности.

— Б. Паскаль

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

Напомним: характеристической функцией случайной величины $\xi$ называется $\psi_\xi(t) = \mathbf Me^{it\xi}$ (свойства — в П9). В отличие от характеристических, производящие функции определяются только для случайных величин с целыми неотрицательными значениями:

По кирпичикам: производящая функция — это «вешалка» для вероятностей. Вероятность $\mathbf P(\eta = n)$ висит на крючке $z^n$. Чтобы достать её обратно, раскрываем функцию в ряд и смотрим на коэффициент при $z^n$.

Отметим, что $F(z)$ из теоремы 2 главы 16 является производящей функцией времени возвращения частицы в начало координат при $k \le 2$. При $k = 3$ она не является вероятностной производящей функцией, поскольку $F(1) < 1$: время возвращения с положительной вероятностью бесконечно (теорема Пойа, §4 главы 16).

Пример 1. Счастливый билетик

Назовём шестизначный номер билетика (талончика) счастливым, если сумма трёх первых цифр равна сумме трёх последних. Пусть $\eta_j$ — $j$-я цифра номера случайно выбранного билета ($j = 1, \dots, 6$). Эти величины независимы и одинаково распределены: $\mathbf P(\eta_j = m) = 1/10$, $m = 0, 1, \dots, 9$. Производящая функция

Нас интересует $\mathbf P(\eta_1 + \eta_2 + \eta_3 = \eta_4 + \eta_5 + \eta_6)$. Покажем, что число таких номеров совпадает с числом номеров, у которых сумма всех шести цифр равна 27. Для этого воспользуемся «принципом отражения» (§6 главы 14): номеру $(\eta_1, \dots, \eta_6)$ сопоставим номер $(\eta_1, \eta_2, \eta_3, 9 - \eta_4, 9 - \eta_5, 9 - \eta_6)$. Это взаимно однозначное отображение первой группы номеров на вторую: если $\eta_1 + \eta_2 + \eta_3 = \eta_4 + \eta_5 + \eta_6$, то новая сумма равна $27$, и наоборот.

Основное свойство производящих (и характеристических) функций — они перемножаются при сложении независимых величин. Действительно, в силу леммы о независимости (§3 главы 1) и свойства 5 математического ожидания (П2)

Положим $S_6 = \eta_1 + \dots + \eta_6$. Из (16) и (17)

По принципу отражения вероятность счастливого билета равна $\mathbf P(S_6 = 27)$ — коэффициенту при $z^{27}$ в разложении (18) по степеням $z$. Используем разложение бинома в ряд Тейлора

где $C^k_x = x(x - 1)\dots(x - k + 1)/k!$ — обобщённый биномиальный коэффициент. Правая часть (18) записывается как

Перемножая почленно, видим, что коэффициент при $z^{27}$ равен $10^{-6}\bigl(-C^{27}_{-6} + C^1_6C^{17}_{-6} - C^2_6C^7_{-6}\bigr)$. Нетрудно подсчитать, что искомая вероятность есть

Смысл по-пацански: раньше в трамвае считали: «счастливый — съешь». Съедать приходилось примерно каждый восемнадцатый билет.

Проверим и формулой, и прямым перебором:

Пример 2. Возвращение несимметричного блуждания

Найдём вероятность возвращения в 0 одномерного несимметричного случайного блуждания $S_n = \xi_1 + \dots + \xi_n$, у которого шаги независимы и $\mathbf P(\xi_k = 1) = p$, $\mathbf P(\xi_k = -1) = 1 - p \equiv q$, $0 < p < 1$. Эта модель уже встречалась в §4 главы 13 в задаче о разорении игрока.

При $p \ne \frac12$ по закону больших чисел (П6) у блуждания есть «снос»: траектория идёт вдоль прямой $(p - q)n$. Поэтому интуитивно понятно, что вероятность возвращения меньше 1. Вычислим, как она зависит от $p$.

Как в главе 16, $u_{2n} = \mathbf P(S_{2n} = 0)$, $f_{2n}$ — вероятность вернуться в 0 впервые в момент $2n$. Очевидно, $u_{2n} = C^n_{2n}p^nq^n$. Пусть $U(z) = \sum_{n=0}^\infty u_{2n}z^{2n}$, $F(z) = \sum_{n=1}^\infty f_{2n}z^{2n}$. Формула из леммы §4 главы 16 остаётся верной и для несимметричного блуждания. Поэтому справедливо и $F(z) = 1 - 1/U(z)$ (теорема 2 главы 16). Для вычисления $U(z)$ понадобится тождество $C^n_{2n} = (-1)^nC^n_{-1/2}4^n$ (вопрос 2). Применяя (19) с $x = -1/2$:

Следовательно, вероятность возвращения в 0 когда-нибудь равна

В частности, при $p = 0{,}9$ получаем $F(1) = 0{,}2$. Заметим, что $F(1) = f_2 + f_4 + \dots$, но $f_2 = 2pq = 0{,}18$. Таким образом, если частица не вернулась сразу, то её шансы на возвращение в дальнейшем составляют всего 0,02. (Как $1 - F(1) = |p - q|$ связана с вероятностью никогда не проиграть бесконечно богатому противнику — вопрос 3.)

Смысл по-пацански: течение реки. Если тебя не прибило к причалу на первом же шаге, дальше течение уносит — и вернуться почти невозможно.

Пример 3. Возвращение на $k$-мерной решётке

Наконец, вычислим вероятность возвращения в начало координат для симметричного блуждания по $k$-мерной целочисленной решётке (продолжение §4 главы 16). Здесь потребуются не только степенные ряды $U(z)$ и $F(z)$, но и характеристические функции.

Обозначим через $\mathbf S_n$ положение частицы после $n$ шагов: $\mathbf S_n = \boldsymbol\xi_1 + \dots + \boldsymbol\xi_n$, где $k$-мерные шаги $\boldsymbol\xi_i$ независимы и имеют вид $(0, \dots, 0, \pm1, 0, \dots, 0)$, причём каждое из $2k$ направлений равновероятно.

Одномерный случай. Характеристическая функция шага

По свойству 2 из П9 $\psi_{S_n}(t) = \sum_le^{itl}\mathbf P(S_n = l) = \cos^nt$. В силу периодичности при $l \ne m$ интегралы от $e^{it(l-m)}$ по $[-\pi, \pi]$ равны нулю, поэтому

По кирпичикам: характеристическая функция — это ряд Фурье, у которого коэффициенты — вероятности. Интеграл с $e^{-itm}$ «вылавливает» нужный коэффициент, потому что все остальные гармоники за период гасятся.

$k$-мерный случай. Для векторов $\mathbf t = (t_1, \dots, t_k)$ и $\mathbf m = (m_1, \dots, m_k)$

Положив $\mathbf m = \mathbf 0$ и просуммировав под интегралом геометрическую прогрессию, получаем

По теореме 2 главы 16 возвратность блуждания равносильна расходимости интеграла

Подынтегральная функция непрерывна всюду внутри куба $[-\pi, \pi]^k$, кроме начала координат. Поэтому расходимость (20) эквивалентна расходимости интеграла по $k$-мерному шару сколь угодно малого радиуса $\varepsilon$ с центром в $\mathbf 0$. Перейдём к полярным координатам $(r, \varphi_1, \dots, \varphi_{k-1})$ с якобианом $J = r^{k-1}\sin^{k-2}\varphi_1\sin^{k-3}\varphi_2\dots\sin\varphi_{k-2}$ (формулы (8) главы 3). Разложение $\cos t = 1 - \frac12t^2 + o(t^2)$ позволяет заменить подынтегральную функцию вблизи $\mathbf 0$ на $\bigl[\frac1{2k}(t_1^2 + \dots + t_k^2)\bigr]^{-1} = \bigl[\frac1{2k}r^2\bigr]^{-1}$. Интеграл по шару эквивалентен произведению одномерных интегралов

где выражение в квадратных скобках — положительная константа. Сходимость или расходимость определяется интегралом $\int_0^\varepsilon r^{k-3}dr$, который расходится при $k \le 2$ и сходится при больших $k$. $\blacksquare$

Так получается второе доказательство теоремы Пойа. Вероятность возвращения когда-нибудь $F(1) = 1 - 1/U(1)$ можно найти, численно подсчитав интеграл (20). Она приближённо равна 0,35 при $k = 3$ и 0,2 при $k = 4$. (Удобнее считать не $k$-кратный интеграл, а одномерный: $U(1) = \int_0^\infty e^{-t}I_0(t/k)^k\,dt$, где $I_0$ — модифицированная функция Бесселя. Так считает виджет: 0,3405; 0,1932; 0,1352; 0,1047 при $k = 3, 4, 5, 6$.)

Смысл по-пацански: чем больше измерений, тем больше «дорог, ведущих не домой». На прямой и на плоскости их не хватает, чтобы потеряться навсегда, а начиная с трёх — хватает.

Проверь себя