§4. Блуждание на плоскости и в пространстве: вернёшься ли домой

Материал этого параграфа продолжает тему траекторий случайных блужданий из §6 главы 14, только теперь частица перемещается по точкам с целыми координатами на плоскости или в пространстве (блуждание по $k$ -мерной решётке — в §4 главы 17).

Случайным будем называть блуждание, при котором частица переходит в одну из $2k$ соседних по осям точек с вероятностью $\frac1{2k}$ независимо от своего положения. (Траекторией теперь называем не развёртку во времени, а ломаную в $\mathbb R^k$ , соединяющую последовательные положения частицы.) Как и в §6 главы 14, $u_{2n}$ — вероятность вернуться в начало координат на $2n$ -м шаге, $f_{2n}$ — вероятность того, что первое возвращение произошло в момент $2n$ .

Лемма о первом возвращении

Лемма. При $n \ge 1$ верно равенство $u_{2n} = \sum_{i=1}^nf_{2i}u_{2n-2i}$ (здесь $u_0 = 1$ ).

Доказательство. Общее число путей за время $2n$ равно $(2k)^{2n}$ . Попадание в начало в момент $2n$ может быть либо первым возвращением, либо первое возвращение произошло в некоторый момент $2i < 2n$ , и далее через $2n - 2i$ шагов частица вновь вернулась. Вероятность последнего при фиксированном $i$ равна $f_{2i}u_{2n-2i}$ : имеется $(2k)^{2i}f_{2i}$ путей длины $2i$ , оканчивающихся первым возвращением, и $(2k)^{2n-2i}u_{2n-2i}$ путей из начала в начало длины $2n - 2i$ . При разных $i$ эти события несовместны. Складывая вероятности, получаем формулу. $\blacksquare$

По кирпичикам: «вернулся на шаге $2n$ » = «впервые вернулся на шаге $2i$ » и «потом от начала опять вернулся через $2n - 2i$ ». Перебираем, когда было первое возвращение, — и всё.

Время правее нуля

Теорема 1. Пусть $k = 1$ . Обозначим через $\delta_{2n}$ время, в течение которого частица, совершая $2n$ шагов по прямой, находилась правее нуля. Тогда при $n \ge 1$ $\beta_{2i,2n} \equiv \mathbf P(\delta_{2n} = 2i) = u_{2i}u_{2n-2i}$ , $i = 0, 1, \dots, n$ (сравни с теоремой 3 главы 14).

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

Доказательство. По теореме 1 главы 14 $\beta_{2n,2n} = u_{2n}$ , по симметрии $\beta_{0,2n} = u_{2n}$ . Пусть $1 \le i \le n - 1$ и частица ровно $2i$ из $2n$ шагов была правее нуля. Тогда первое возвращение в нуль произошло в некоторый момент $2r < 2n$ , и до него частица была либо правее нуля, либо левее. В первом случае $1 \le r \le i$ , и после $2r$ частица была правее нуля $2i - 2r$ шагов из $2n - 2r$ : таких путей $\frac12 2^{2r}f_{2r}\cdot2^{2n-2r}\beta_{2i-2r,2n-2r}$ . Во втором — после $2r$ правее нуля $2i$ шагов из $2n - 2r$ , откуда $r \le n - i$ ; таких путей $\frac12 2^{2r}f_{2r}\cdot2^{2n-2r}\beta_{2i,2n-2r}$ . Следовательно,

\beta_{2i,2n} = \frac12\sum_{r=1}^if_{2r}\beta_{2i-2r,2n-2r} + \frac12\sum_{r=1}^{n-i}f_{2r}\beta_{2i,2n-2r}. \tag{18}

По индукции (для путей короче $2n$ теорема верна) (18) сводится к

\beta_{2i,2n} = \frac12u_{2n-2i}\sum_{r=1}^if_{2r}u_{2i-2r} + \frac12u_{2i}\sum_{r=1}^{n-i}f_{2r}u_{2n-2i-2r},

и по лемме первая сумма равна $u_{2i}$ , вторая — $u_{2n-2i}$ . $\blacksquare$

Производящие функции

Рассмотрим степенные ряды

U(z) = \sum_{n=0}^\infty u_{2n}z^{2n}, \qquad F(z) = \sum_{n=1}^\infty f_{2n}z^{2n}, \qquad 0 \le z < 1.

Теорема 2. Имеет место соотношение $F(z) = 1 - 1/U(z)$ .

Доказательство. По условию $u_0 = 1$ и лемме

U(z) - 1 = \sum_{n=1}^\infty u_{2n}z^{2n} = \sum_{n=1}^\infty z^{2n}\Bigl(\sum_{i=1}^nf_{2i}u_{2n-2i}\Bigr) = \sum_{i=1}^\infty f_{2i}z^{2i}\sum_{n=i}^\infty u_{2n-2i}z^{2n-2i} = F(z)U(z).

Перестановка порядка суммирования законна из-за неотрицательности членов. $\blacksquare$

Так как $U(z)$ и $F(z)$ — ряды с положительными коэффициентами, их пределы при $z \to 1$ (конечные или бесконечные) равны соответственно $\sum u_{2n}$ и $\sum f_{2n}$ . По теореме 2 расходимость ряда $\sum u_{2n}$ равносильна тому, что $\sum f_{2n} = 1$ . Последнее означает, что частица рано или поздно вернётся в начало с вероятностью 1. Такое блуждание называют возвратным.

Смысл по-пацански: если в среднем частица бывает дома бесконечно много раз ( $\sum u_{2n} = \infty$ ), то хоть раз она туда точно вернётся. И наоборот.

Теорема Пойа

Докажем замечательный результат, впервые опубликованный Д. Пойа в 1921 году.

Теорема Пойа. Случайное блуждание на прямой и плоскости возвратно, а в трёхмерном пространстве — невозвратно.

Доказательство. Исследуем сходимость $\sum u_{2n}$ в двумерном и трёхмерном случаях (одномерный разобран в §6 главы 14).

Плоскость. Всего путей длины $2n$ — $4^{2n}$ . Чтобы в момент $2n$ вернуться в начало, число шагов вверх должно совпасть с числом шагов вниз, а вправо — с числом влево. Если шагов вверх $i$ , то вниз тоже $i$ , а вправо и влево — по $n - i$ . Представим шаг шариком, направление — ящиком: раскладываем $2n$ шариков по четырём ящикам. По формуле 3 главы 10 число таких раскладок

\frac{(2n)!}{i!\,i!\,(n - i)!\,(n - i)!} = C^n_{2n}\bigl(C^i_n\bigr)^2. \tag{19}

Суммируя по $i$ от 0 до $n$ ,

u_{2n} = 4^{-2n}C^n_{2n}\sum_{i=0}^n\bigl(C^i_n\bigr)^2 = 4^{-2n}C^n_{2n}\sum_{i=0}^nC^i_nC^{n-i}_n = \bigl(2^{-2n}C^n_{2n}\bigr)^2. \tag{20}

Здесь использовано тождество

\sum_{i=0}^nC^i_nC^{n-i}_n = C^n_{2n}, \tag{21}

вытекающее из сравнения коэффициентов при $t^n$ в равенстве $(1 + t)^{2n} = (1 + t)^n(1 + t)^n$ . (Другое доказательство — в примере 4 ниже.) Формула Стирлинга (формула (14) главы 14) даёт $u_{2n} \sim (1/\sqrt{\pi n})^2 = 1/(\pi n)$ , и ряд $\sum u_{2n}$ расходится — блуждание на плоскости возвратно.

Пространство. Аналогично

u_{2n} = 6^{-2n}\sum_{0\le i+j\le n}\frac{(2n)!}{i!\,i!\,j!\,j!\,(n - i - j)!\,(n - i - j)!} = 2^{-2n}C^n_{2n}\sum_{0\le i+j\le n}\Bigl[3^{-n}\frac{n!}{i!\,j!\,(n - i - j)!}\Bigr]^2. \tag{22}

В квадратных скобках стоят вероятности $r_{ij}$ того, что при случайном размещении $n$ различимых шариков по трём ящикам в первом окажется $i$ , во втором $j$ , в третьем $n - i - j$ (§5 главы 10). Поэтому

\sum_{0\le i+j\le n}r_{ij}^2 \le \max_{0\le i+j\le n}r_{ij}\sum_{0\le i+j\le n}r_{ij} = \max_{0\le i+j\le n}r_{ij}. \tag{23}

Вероятности $r_{ij}$ максимальны при $i_0 = j_0 \sim n/3$ (задача 2). По формуле Стирлинга

\max_{0\le i+j\le n}r_{ij} \sim \frac cn, \qquad c = \frac{3\sqrt3}{2\pi}. \tag{24}

Так как $2^{-2n}C^n_{2n} \sim 1/\sqrt{\pi n}$ , из (22)–(24) в трёхмерном случае $u_{2n}$ по порядку не превосходит $n^{-3/2}$ . Следовательно, ряд $\sum u_{2n}$ сходится, и блуждание невозвратно. Вероятность возвращения когда-нибудь $F(1) = \sum f_{2n}$ приближённо равна 0,35 (§4 главы 17; точнее, 0,3405). $\blacksquare$

Сверху — одно блуждание из 400 шагов. Возвращений в начало: 0.Снизу — точная вероятность вернуться в начало не позже шага t (Σf₂ᵢ из леммы) для прямой, плоскости и пространства; точки — доля из 3000 смоделированных блужданий для выбранной размерности. На прямой и плоскости кривые ползут к 1 (на плоскости — очень медленно), в пространстве — к 0.34.

Смысл по-пацански: на одномерной улице и на плоском районе тот, кто гуляет по монетке, обязательно когда-нибудь вернётся к своему подъезду. А вот птица, которая так же наугад порхает в трёхмерном пространстве, с вероятностью около двух третей не вернётся к гнезду никогда — «есть куда улететь». (На плоскости, правда, возвращения придётся ждать очень долго: к шагу 300 вернулись лишь около 63 %, а на прямой — уже 95 %.)

Две частицы

Перескажем своими словами рассуждение Феллера о теореме Пойа. Почти очевидно, что в одномерном и двумерном случаях частица с вероятностью 1 бесконечно число раз пройдёт через каждое возможное положение, а в трёхмерном это неверно. Для двух измерений в известном смысле справедливо «все дороги ведут в Рим».

Теперь возьмём две частицы, блуждающие независимо и одновременно. Встретятся ли они когда-нибудь? Расстояние между положениями определим как наименьшее число шагов от одного до другого (сумма модулей разностей координат). Если обе частицы делают по шагу, расстояние меняется на 0 или на 2, поэтому его чётность сохраняется. При нечётном начальном расстоянии они никогда не займут одно положение. При чётном — вероятность встречи на $n$ -м шаге равна вероятности того, что первая частица за $2n$ шагов дойдёт до начального положения второй. Значит, в двумерном (но не трёхмерном) случае две частицы наверняка бесконечно много раз будут занимать одно и то же положение (при нечётном начальном расстоянии — соседние). Итог: в одно- и двумерном случаях две частицы с достоверностью встретятся бесконечное число раз, а в трёхмерном с положительной вероятностью не встретятся никогда.

Пример 4. Гипергеометрическое распределение

В урне $M$ чёрных шаров и $N - M$ белых. Случайно без возвращения извлекается группа из $n$ шаров. Вероятность того, что в ней ровно $m$ чёрных,

p(m, n, M, N) = C^m_MC^{n-m}_{N-M}\big/C^n_N, \qquad m = 0, 1, \dots, n. \tag{25}

Доказательство. Занумеруем чёрные шары числами от 1 до $M$ , белые — от $M + 1$ до $N$ . Пусть чёрные шары появились при извлечениях с номерами $1 \le i_1 < \dots < i_m \le n$ . Эти номера можно выбрать $C^m_n$ способами. Для фиксированного набора число вариантов выбора номеров шаров равно $A^m_MA^{n-m}_{N-M}$ , где $A^m_M = M(M - 1)\dots(M - m + 1) = m!\,C^m_M$ — число размещений из $M$ по $m$ . Так как всех элементарных событий $A^n_N$ ,

p(m, n, M, N) = \frac{C^m_nA^m_MA^{n-m}_{N-M}}{A^n_N} = \frac{C^m_n\,m!\,C^m_M\,(n - m)!\,C^{n-m}_{N-M}}{n!\,C^n_N} = \frac{C^m_MC^{n-m}_{N-M}}{C^n_N}. \tag{26}

$\blacksquare$

Поскольку сумма вероятностей (25) по всем $m$ равна 1, взяв $m = i$ , $N = 2n$ и $M = n$ , получаем ещё одно доказательство тождества (21).

Название «гипергеометрическое» происходит от гипергеометрического ряда

G(a, b, c, z) = 1 + \frac{ab}cz + \frac1{2!}\frac{a(a + 1)b(b + 1)}{c(c + 1)}z^2 + \dots, \tag{27}

который при $a = 1$ , $b = c$ сводится к геометрической прогрессии. Нетрудно проверить, что

p(m, n, M, N) = \frac{A^n_{N-M}}{A^n_N}\Bigl[\frac1{m!}\frac{A^m_MA^m_n}{A^m_{N-M-n+m}}\Bigr],

где величина в квадратных скобках — коэффициент при $z^m$ ряда (27) с $a = -M$ , $b = -n$ , $c = N - M - n + 1$ . Любопытно, что многие элементарные функции выражаются через $G$ :

(1 + z)^n = G(-n, 1, 1, -z), \quad \ln(1 + z) = zG(1, 1, 2, -z), \quad \arcsin z = zG(1/2, 1/2, 3/2, z^2), \quad \mathrm{arctg}\,z = zG(1/2, 1, 3/2, -z^2).

Где применяется. Модель выбора без возвращения используется при выборочном контроле качества продукции: в партии из $N$ изделий дефектные играют роль чёрных шаров, их число $M$ неизвестно. Если в контрольной выборке размера $n$ найдено $m$ дефектных, (25) позволяет делать выводы об $M$ .

Ещё пример — оценка размера популяции по повторному отлову. Из озера вылавливают $M$ рыб, помечают краской и выпускают обратно. При повторном отлове $n$ рыб $m$ из них оказались помечены. Как оценить общее число $N$ рыб (задача 1)? Ответ: $\hat N = [nM/m]$ — доля помеченных в улове примерно равна их доле в озере.

Загрузка редактора…

(Заметь: средняя оценка заметно больше 1000 — оценка $[nM/m]$ смещена вверх, потому что малые $m$ дают огромные $\hat N$ . Медиана же близка к истине.)

Смысл по-пацански: пометил сотню, поймал сотню, в улове десяток меченых — значит, меченые составляют десятую часть, и в озере около тысячи. Но если меченых в улове случайно оказалось двое, оценка улетит до пяти тысяч. Поэтому одному отлову не верь — повтори.

Наконец, из (26) вытекает сходимость

p(m, n, M, N) \to C^m_np^m(1 - p)^{n-m}

при $N \to \infty$ и $M/N \to p$ , $0 < p < 1$ . Для больших $N$ и $M$ практически нет различия между выбором без возвращения и с возвращением.