О случайных блужданиях

45

О случайных блужданиях

Кандидат физико-математических наук
С. И. СОВОЛЕВ

В радиопередаче по сказке Джанни Родари «Чиполлино и его друзья» сыщик мистер Моркоу ведет розыск справшегося Чиполлино по принципу:

«Шаг назад, шаг вперед,
От нас разбойник не уйдет».

Этот принцип поиска можно было бы считать шуткой автора, если бы его эффективность не вытекала из одной теоремы теории вероятности. Наша заметка посвязывана этой теореме и примыкающим к ней задачам.

Случайные блуждания по примой

Отметим целочисленные точки на прямой, возьмем монету и фишку. Представим себе, что в момент времени 0 в точке $a \in Z$ стоит фишка. Бросим монету. Если она выпадет гербом, перевиним фишку на 1 вправо, если решкой, то на 1 влево. А дальше снова бросаем монету и поступаем по этому правилу и т. д. Если монета не имеет дефектов, то фишка, в момент времени $t$ ($t = 0, 1, 2, \dots$) стоящая в точке $k \in Z$, вследующий момент времени $t + 1$ с вероятностью 1/2 оказется в точке $k + 1$ или с той же вероятностью оказется в точке $(k - 1)*$.

Описанный процесс называется симметриным случайным блужданием по множеству $Z$ целых точек прямой, начинающихся в точке $a$. Такое блуждание называется симметриным потому, что у монетки герб и решка равноправны.

Немного уточняя ситуацию из сказки Джанни Родари, будем считать, что сыщик Моркоу в розысках Чиполлино совершает симметриное случайное блуждание по множеству $Z$ (с помощью монетки).

*) Вероятность $p(x)$ события $x$ — это некоторая численная характеристика возможности наступления этого события. Вероятность невозможного события принимается равной 0, достоверного события — равной 1, а вообще $0 \leq p(x) \leq 1$. В сложных сituциях вероятность определяется аксиоматически, однako в этой заметке аксиоматически теорию нам заменит небольшая доза здравого смысла. В частности, если несколько событий равновозможны, то их вероятности одинаковы; например, вероятность выпадения двойки (или пaterки) на нежульничекой игральной кости равна, конечно же, 1/6, вероятность выпадения орла на негнутой монете — 1/2.

46

Задание 1. Возьмите монету и фишку, фишку поставьте в точку 0. Бросьте монету, передвините фишку и запишите ее положение. Повторите до 10 раз. В результате вы должны получить строку из последовательных положений фишки.

Конкретное блуждание можно наглядно изображить, нарисовав его траекторию. Положение фишки в момент времени $t$ в точке $k$ отметим точкой $M_t$ с координатами $(t; k)$ на плоскости с прямогольной декартовой системой координат. Соединив стрелкой точку $M_t$ с точкой $M_{t+1}$ ($t = 0, 1, 2, \dots$), мы и получим наглядное изображение траектории фишки.

Например, если при бросании монеты выплали последовательно $\Gamma, \Gamma, P, \Gamma, P$, а начальное положение фишки было в точке 0, то последовательные положения также:

| время | 0 | 1 | 2 | 3 | 4 | 5 |
| :— | :— | :— | :— | :— | :— | :— |
| положение фишки | 0 | 1 | 2 | 1 | 2 | 1 |

и траектория выглядит так, как показано на рисунке 1.

Задание 2. Нарисуйте траекторию, изображенную блуждание фишки из задания 1.

Вероятность попадания в данную точку

Пусть блуждание фишки по прямой начинается в точке 0. Интересным является вопрос, с какой верятностью в момент времени $t$ фишка оказывается в положении $k$. Иначе говоря, с какой верятностью $t$-звенная траектория приходит в точку $(t; k)$? Обозначим эту верятность $P_t(k)$. Ответ на поставленный вопрос зависит от числа $S_t(k)$ траекторий, ведущих из точки $(0; 0)$ в точку $(t; k)$.

Напишем около каждой точки $(t; k)$, в которой приходит хотя бы одна траектория, число $S_t(k)$, показывающее сколько траекторий ведет в эту точку для $t = 0, 1, 2, 3$ (рис. 2).

Задание 3. Продолжите рисунок 2 для $t = 4, 5, 6$.

Можно подметить следующие. В точку $(t; k)$ могут идти стрелки только из точки $(t - 1; k - 1)$ и $(t - 1; k + 1)$, и больше неткуда. Поэтому $S_t(k) = S_{t-1}(k-1) + S_{t-1}(k+1)$.

Таблица, состоящая из чисел $S_t(k)$, начало которой мы нарисовали, оказывается так называемым треугольником Паскала. Она всегда, стольик за столбиком, порождает условия $S_0(0) > 1$ и соответствием (1). Например:

$$\begin{align*} S_1(-1) &= S_0(-2) + S_0(0) = 0 + 1 = 1, \\ S_1(1) &= S_0(0) + S_0(2) = 1 + 0 = 1, \\ S_2(-2) &= S_1(-3) + S_1(-1) = 0 + 1 = 1, \\ S_2(0) &= S_1(-1) + S_1(1) = 1 + 1 = 2, \\ S_2(2) &= S_1(1) + S_1(3) = 1 + 0 = 1, \end{align*}$$

и так далее.

Конечно, $t$-звенных траекторий в два раза больше, чем $(t - 1)$-звенных — ведь каждая $(t - 1)$-звенная траектория порождает две $t$-звенных. Поэтому однозвенных траекторий 2, двухвенных — 4 и так далее, $t$-звенных траекторий — $2^t$.

Все $2^t t$-звенных траекторий — равновозможные траектории движения фишки (поскольку герб $\Gamma$ и решка $P$ — равновозможные исходы бросания монеты), из них $S_t(k)$ траекторий приходит в точку $(t; k)$. Поэтому верятность $P_t(k)$, с которой $t$-звенная траектория приходит в точку $(t; k)$, равна $S_t(k)/2^t$. Okоло точки $(t; k)$, в которой приходит хотя бы одна траектория, выпишем верятность $P_t(k)$. Полученный таблицу назовем треугольником верятностей. Поделив равенство (1) на $2^t$, получим закон

47

$$P_t(k) = \frac{1}{2} P_{t-1}(k-1) + \frac{1}{2} P_{t-1}(k+1),$$

порождащий (с использованием условий $P_0(0) \geq 1$) весь треугольник вероятностей (рис. 3).

Задание 4. Продолжите треугольник вероятностей $P_t(k)$ вправо, выписав его для $t = 4, 5, 6$.

Формула (2) учитывает, что:

1. Фишка может быть в момент времени $t$ в положении $k$ только если она была в момент времени $t - 1$ в одном из соседних положений $k - 1$ или $k + 1$;

2. переходы из положения $k - 1$ в положение $k + 1$ или из положения $k + 1$ в положение $k$ проискают с вероятностями $1/2$ (позному перед $P_{t-1}(k - 1)$ и $P_{t-1}(k + 1)$ и стоит коэффициенты $1/2$).

Следующие два задачи предназначаны для тех, кто знаком с определенным числа сочетаний и знает формулу бинома.

Задание 5. Докажите, что

$$P_n(k) = C_n^{\frac{n+k}{2}}/2^n,$$

еще $C_n^m$ число сочетаний из $n$ элементов по $m$.

Задание 6. а) Проверьте для $t = 1, 2, 3, 4$, что коэффициент при $x^k$ в разложении многочлена

$$\frac{1}{2^n} \left( x + \frac{1}{x} \right)^t$$

по степеням $x$ равен $P_t(k)$. 6) Докажите утверждение пункта a) для любого натурального $t$.

Попадется ли Чиполлино?

Пусть в точке 0 на прямой спратически Чиполлино, а в точке $k$ находится мостер Моркову. Мы предположили, что сыщик, разыскивая Чиполлино, совершает симметриное случайное блуждание, начинающееся в момент времени 0 в точке $k$ на прямой. С какой вероятностю мостер Моркову когдаибудь найдет Чиполлино, т. е. окажется в точке 0?

Обозначим эту вероятность $P(k)$. Как и всякая вероятность, $P(k)$ — какая-то часть единцы:

$$0 \leq P(k) \leq 1.$$

Заметим, что $P(0) > 1$ (если $k = 0$, то уже в момент времени 0 сыщик и Чиполлино находится в одной точке,

помним — достоверное событие, а его вероятность равна 1). Если $k \neq 1$, то поскольку из точки $k$ сыщик может попасть когда-нибудь в точку 0 только,ройдя в следующий момент времени после выхода из точки $k$ через соседние точки $k - 1$ и $k + 1$, оказывается справедливым тот же самый закон полусуммы:

$$P(k) = \frac{1}{2} P(k - 1) + \frac{1}{2} P(k + 1).$$

Здесь учтено, что переход за единицу времени из точки $k$ в точку $k - 1$ проискают с вероятностю $1/2$; то же верно для перехода из точки $k$ в точку $k + 1$.

Рассмотрим точки $M_k(k; p(k))$ на плоскости с прямой угловой декартовой системой координат $xOy$. Поскольку середина отрезка, соединяющего точки $(x_1; y_1)$ и $(x_2; y_2)$, есть точка $\left( \frac{x_1 + x_2}{2}; \frac{y_1 + y_2}{2} \right)$, ясно, что точка $M_k$ (где $k \neq 0$) является серединой отрезка $M_k - 1M_k + 1$. Следовательно, точки $M_k$, где $k \geq 0$, лежат на одном луче, и точки $M_k$, где $k \leq 0$, лежат на одном луче. Оба этих луча выходит из точки $M_0(0; 1)$ (так как $P(0) > 1$) и лежат в полосе $0 \leq y \leq 1$ (так как $0 \leq P(k) \leq 1$ для любого $k$), заключенной на рисунке 4. Следовательно, они составляют прямую $y = 1$. Все точки $M_k(k; P(k))$ лежат на этой прямой, поэтому $P(k) \geq 1$ для любого $k$.

Итак, мы доказали, что сыщик с вероятностю 1 рано или поздно найдет Чиполлино, из какой бы точки $k$ он ни начинал блуждание!

Читатель может спроисть — а что если при бросании монеты все время будет выпадать единца, ведь тогда сыщик будет вправо по прямой и никакого не найдет Чиполлино? Конечно, такое блуждание логически возможно, но вероятность, что произойдет блуждание, не приводящее в точку 0, равна 0. Это — доказанная нами теорема. Вопрос о ее приложи-

48

Случайные блуждания на плоскости и в пространстве

Рассмотрим на плоскости треугольную сетку; возьмем фишку и (недеформированную) игральную кость. ШестЬ направленной движения по сетке обозначим цифрами 1, 2, 3, 4, 5, 6 так, как показано на рисунке 5. Поставим фишку в один из узлов сетки и бросим кость. Переведим фишку в соседний узел по направлению, отвечащему показанию кости. А дальнейшее снова бросаем кость и поступем по этому правлу и т. д. Этот процесс называется симметриным случайным блужданием по плоской треугольной сетке.

Предположим, что Чиполлино спрятался в одном из узлов сетки, а сыщик мистер Моркову совершает случайные симметричные блуждания по сетке; найдет ли он Чиполлино? Оказывается, что и в этом случае сыщик находится свою жертву с вероятностью edиница. Это тоже математическая теорема из теории вероятности, известная под обозначим называемем «все дороги ведут в Рим». Ее доказательство мы не приводим — оно несколько сложнее доказательства теоремы о случайном блуждании на прямой. Результат будет тем же для плоской квадратной сетки (вместо обичной игральной кости придется пользоваться «костью» в форме правильно терраэдра).

Однако если перейти к кубическому сетке в пространстве и аналогично определить на ней симметриное случайное блуждание (здесь снова подой-
Pис. 5.

Pис. 7.

дет обычная игральная кость — ведь из каждой вершины кубического сетки выходит шесть ребер), то результат оказывается совсем другим. Если Чиполлино спрячется далеко от сыщика, то вероятность попмки становится ничтожно малой. Это уже трудная теорема, об ее доказательстве мы говорить ничего не будем.

Два слова о приложениях

Игровой сложет этой заметки не должен вводить читателя в заблуждение. Теория случайных блужданий — важный и очень полезный раздел теории вероятности. Она с успехом применяется при изучении различных процессов развития (в физике, в химии и даже в экономике). Особенно в последние годы, когда случайные процессы легко моделируют на ЭВМ с помощью датчиков случайных чисел. Эффективные и неожиданные приложения она получает в практическом нахождение решений конкретных дифференциальных уравнений с помощью так называемого метода Monte Carlo. Но это предмет для отдельного расскада.

В заключение предлагаем два задачи.

Задание 7. Чиполлино спрятается в точке 0, в точке N находится пропасть, а сыщик Моркову находится в точке k (k∈Z, 0<k<N). Сыщик цитет Чиполлино прежним образом. Если он попадет в точку 0, то найдет Чиполлино, а если попадет в точку N, то свалится в пропасть (рис. 6). С какой вероятностью сыщик найдет Чиполлино? С какой вероятностью сыщик свалится в пропасть?

Указание: Докажите, что (в режних обозначениях)

$$P(k) = \frac{1}{2} P(k-1) + \frac{1}{2} P(k+1),$$