35. Решение задачи «На краю утеса»

Перед решением задачи полезно задуматься о возможном ответе. Посмотрим, что может случиться на нескольких первых шагах. Приведенная схема иллюстрирует тот факт, что человек может упасть вниз только через нечетное число шагов. После одного шага вероятность упасть вниз равна 1/3 (рис. 6). Путь 1 ? 2 ? 1 ? 0 добавляет еще 2/27 к вероятности падения, давая общую вероятность несчастья 11/27. После пяти шагов пути 1 ? 2 ? 1 ? 2 ? 1 ? 0 и 1 ? 2 ? 3 ? 2 ? 1 ? 0 вместе добавляют 8/243 к вероятности падения, давая общий результат 107/243. Этот список можно продолжить, но мы обратимся теперь к иному подходу.

Рис. 6. Схема блуждания пьяницы, показывающая вероятность нахождения на различных расстояниях от края пропасти.

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

Рассмотрим частицу, которая сначала находится в положении x = 1 на оси. Структура задачи будет яснее, если вероятность шага направо вместо 2/3 будет равна p. Частица движется из положения 1 либо в точку x = 2 с вероятностью p, либо в точку x = 0 с вероятностью 1 ? p (рис. 7). Вообще, если частица находится в положении x = n, n > 0, n — целое число, то она сдвигается либо в точку x = n + 1 с вероятностью p, либо в точку x = n ? 1 с вероятностью 1 ? p. Если частица попадает в положение x = 0, то там она поглощается (не делает других шагов). Нас интересует значение вероятности P? того, что частица поглощается в точке x = 0, если она выходит из точки x = 1. Разумеется, значение P? зависит от p. Кажется естественным, что если p близко к 1, то вероятность P? мала, а если p близко к нулю, то P? мало отличается от 1.

Рис. 7.

Рассмотрим ситуацию после первого шага: либо частица сдвинулась налево, попала в точку x = 0 и поглотилась там (это событие имеет вероятность 1 ? p), либо сдвинулась направо в точку x = 2 (это событие происходит с вероятностью p). Пусть P? обозначает вероятность того, что частица поглощается в начале координат x = 0, если она выходит из точки x = 2. Тогда мы имеем

P? = 1 ? p + p·P?, (1)

так как 1 ? p есть вероятность поглощения на первом шаге и p·P? — вероятность поглощения на последующих шагах.

Каждый путь, ведущий к поглощению из x = 2, можно разбить на две части:

(1) Путь, идущий из точки x = 2 и достигающий положения x = 1 в первый раз (не обязательно за один шаг) и

(2) Путь, идущий из точки x = 1 в точку x = 0 (также не обязательно за один шаг). Вероятность пути из положения x = 2 в x = 1 есть P? поскольку структура блуждания здесь идентична структуре первоначального блуждания (см. рис. 35.1), за исключением того, что начало координат переносится на один шаг направо. Вероятность попасть из точки x = 1 в x = 0 также равна P? как и в исходной задаче. Величина P? поэтому есть P??, так как события A (частица идет по пути от точки x = 2 к x = 1) и B (частица движется по пути от точки x = 1 до x = 0) независимы, и P(A) = P(B) = P?.

Мы можем переписать уравнение (1) как

P? = 1 ? p + p·P??, (2)

Уравнение (2) — квадратное относительно P? и имеет два решения:

P? = 1; P? = (1 ? p)/p. (3)

В таких задачах одно или оба решения могут быть подходящими, в зависимости от значений p.

Если p = 1/2, то оба решения совпадают, и P? = 1. Когда p = 1, P? = 0, так как частица всегда движется вправо. И когда p = 0, очевидно, P? = 1. При p < 1/2 второе решение (3) не подходит, так как тогда (1 ? p)/p > 1, а по смыслу задачи P? ? 1. Поэтому при 0 ? p ? 1/2 мы имеем P? = 1.

Чтобы доказать, что второе решение P? = (1 ? p)/p имеет место при p > 1/2, нам достаточно установить, что P? является непрерывной функцией от p (грубо говоря, что P? не слишком изменяется, когда p меняется мало). Мы предполагаем эту непрерывность, но не доказываем ее.

Кривая (см. рис. 8) начинается в точке P? = 1 при p = 1/2; она должна спуститься к P = 0 при p = 1, и ее ордината всегда должна равняться 1 или (1 ? p)/p. Кривая не имеет разрывов только в том случае, когда при p > 1/2 соответствующее значение равно (1 ? p)/p. Итак, при предположении непрерывности функции P? мы получаем P? = (1 ? p)/p при p > 1/2. Поэтому наш пьяница с вероятностью 1/2 упадет вниз.

Рис. 8. Вероятности поглощения P.

Приведем другую интерпретацию. Рассмотрим игрока, имеющего начальный капитал в одну денежную единицу (x = 1). Он может играть неограниченно долго, причем в каждом туре игры он с какими-то вероятностями выигрывает или проигрывает эту единицу. Чтобы вероятность банкротства игрока была не более 1/2, вероятность выигрыша в отдельной партии должна быть не менее 2/3. То, что банкротство неизбежно при p = 1/2, для большинства из нас неожиданность.

Приведем еще один взгляд на задачу. Рассмотрим игрока с начальным капиталом x = 1, играющего неограниченно долго против казино с бесконечным капиталом в «безобидную игру» (p = 1/2), при которой он выигрывает или проигрывает единицу в каждом туре. Он наверное обанкротится (P? = 1). Чтобы он не стал банкротом с вероятностью 1/2, вероятность его выигрыша в каждой отдельной партии должна быть p = 2/3. То, что банкротство неизбежно при p = 1/2, является неожиданным для большинства из нас. Обычно считают, что если отдельные партии «безобидны» (средняя потеря равна нулю), то и вся игра безобидна. Разумеется, это представление в обычном смысле верно. Если мы представим такую игру с p = 1/2 и большим числом партий, то среднее значение денежной суммы на руках после n туров равно 1 для каждого конечного числа n. Таким образом, отсутствие «безобидности» является одним из парадоксов бесконечного.

Другой удивительный факт состоит в том, что при p = 1/2 среднее число шагов, требуемое для поглощения, бесконечно. Случай p = 1/2 является странным и глубоким.

Вас может заинтересовать применение указанного здесь метода к частице, выходящей из точки x = m, а не из точки x = 1. Обобщение приведенного выше результата, показывает, что вероятность поглощения с абсциссы x = m есть [(1 ? p)/p]^m или 1, в зависимости от того, будет ли p больше или меньше 1/2. Если p > 1/2 и m велико, то весьма вероятно, что частица избежит поглощения, и поэтому вероятность поглощения мала, а не равна 1.

Если частица выходит из начала координат 0 и ей разрешается делать шаги в обоих направлениях с вероятностью p = 1/2, то в другой классической задаче о блуждании ставится вопрос о том, вернется ли частица когда-либо в начало координат. Мы уже видели, что так действительно будет, ибо она заведомо вернется из положений x = 1 и x = ?1. Дальнейшие сведения об этой задаче будут сообщены ниже.