Задача про пьяницу +93


В книге «Пятьдесят занимательных вероятностных задач с решениями - Ф. Мостеллер» есть интересная задача под номером 35.

В книге приводится решение этой задачи (что ясно из названия). В этой статье будет разобран другой подход к решению аналогичной задачи.

Первые шаги

Будем решать следующую задачу

Прежде, чем переходить к решению задачи, рассмотрим, что может случится на первых шагах (рис. 1).

Рис. 1 Схема блуждания пьяницы за 7 шагов
Рис. 1 Схема блуждания пьяницы за 7 шагов

Например, вероятность того, что пьяница упадет ровно за три шага равнаp^2(1-p).Вероятность же упасть ровно за четыре шага равна0.Вообще говоря, пьяница не может упасть ровно за четное количество шагов, это можно объяснить следующим образом. Чтобы пьяница упал с обрыва, он должен находиться в начальном положение (на расстоянии одного шага от обрыва) и сделать шаг к обрыву. Пьяница находится в начальном положение только за четное количество шагов. Значит, он не может упасть за четное количество шагов.

Обозначим теперь заP_1вероятность того, что пьяница упал с обрыва, находясь при этом на расстоянии одного шага от него. Тогда,P_1можно представить в виде

P_1 = p_1 + p_3 + p_5 + \ldots = \sum_{n=0}^{\infty}p_{2n+1},

гдеp_{2n+1}вероятность того, что пьяница упадет ровно за2n+1шагов.

Получаем, что для решения задачи нужно ответить на два вопроса

  1. Какая явная формула уp_{2n+1}(очевидно, чтоp_{2n+1}зависит отp).

  2. Чему равна сумма ряда \sum_{i=0}^{\infty}p_{2n+1}.

Ответим сначала на первый вопрос.

Как в задаче про пьяницу возникают числа Каталана

Смотря на схему блуждания пьяницы (рис. 1), очевидно предположить, что

p_{2n+1} = p^{n+1}(1-p)^n,

но это не так и вот почему.

Вычислим p_5,то есть вероятность того, что пьяница упадет ровно за пять шагов. Он может упасть пройдя по одному из следующих путей:

1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0, \\ 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1\rightarrow 0.

Пьяница проходит по одному из путей с вероятностьюp^3(1-p)^2,кроме того, события пройти по первому пути и пройти по второму пути несовместны. Тогда, вероятность того, что пьяница упадет с обрыва ровно за пять шагов равна

p_5 = 2p^3(1-p)^2.

Можно вычислить и следующие вероятности

p_7 = 5p^4(1-p)^3, \quad p_9 = 14p^5(1-p)^4, \quad p_{11} = 42p^6(1-p)^5.

Получаем, чтоp_{2n+1}имеет вид

p_{2n+1} = c_np^{n+1}(1-p)^n,

где коэффициент c_nравен количеству путей, при которых пьяница упадет с обрыва ровно за 2n+1шагов.

Более строгое доказательство этого ниже

Строгое доказательство

Утверждение. Для любого целого неотрицательногоnверно, что

p_{2n+1} = c_np^{n+1}(1-p)^n,

где коэффициентc_nравен количеству путей, при которых пьяница упадет с обрыва ровно за2n+1шагов.

Доказательство. Доказательство проведем по индукции.

База индукции. Приn = 0утверждение верно, т.к.p_1 = p,где c_0 = 1.

Шаг индукции. Пустьp_{2n+1} = c_np^{n+1}(1-p)^n.Покажем, что из этого следует, чтоp_{2n+3} = c_{n+1}p^{n+2}(1-p)^{n+1}.

Рис. 1.1
Рис. 1.1

Поскольку,p_{2n+1} = c_np^{n+1}(1-p)^n,то вероятность того, что пьяница был в начальном положение ровно за2n+1шагов, учитывая только один путь, равна p^{n}(1-p)^n.Значит, чтобы он упал ровно за2n+3шагов, он должен сделать один шаг в сторону от обрыва и два шага в сторону обрыва (рис. 1.1).

Получаем, что пьяница упадет с обрыва ровно за2n+3шагов, учитывая только один путь, с вероятностью

p^{n}(1-p)^n \cdot (1-p) \cdot p^2 = p^{n+2}(1-p)^{n+1}.

Так как суть коэффициентаc_{n+1}- количество путей, при которых пьяница упадет с обрыва ровно за2n+3шагов, получаем

p_{2n+3} = c_{n+1}p^{n+2}(1-p)^{n+1}.

Значит, утверждение верно для любого целого неотрицательногоn.

Таким образом, чтобы ответить на первый вопрос, нужно найти явную формулу для c_n. Здесь и возникают числа Каталана.

Числа Каталана

Числами Каталана называется следующая последовательность чисел

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, \ldots

Они возникают во многих комбинаторных задачах среди которых:

  • Количество правильных скобочных последовательностей длины2n.

    Правильные скобочные последовательности длины 8
    Правильные скобочные последовательности длины 8
  • Количество путей Дика (Dyck path) длины2n.

    Пути Дика длины 8
    Пути Дика длины 8
  • Количество различных триангуляций выпуклого(n+2)- угольника.

    Триангуляции правильного шестиугольника
    Триангуляции правильного шестиугольника
Первые числа Каталана, которые появляются в выше описанных задачах
Первые числа Каталана, которые появляются в выше описанных задачах

Важно отметить, что между структурами, которые появляются в этих задачах, можно установить взаимно однозначное соответствие. Так, например, каждой правильной скобочной последовательности ставится в соответствие путь Дика. Покажем это на примере нашей задачи.

Преобразуем сначала таблицу к следующему виду

А теперь рассмотрим соответствие между правильной скобочной последовательностью и путем Дика.

Или другой пример, более длинной скобочной последовательности

Более строгое доказательство этого ниже.

Строгое доказательство

Утверждение. Существует взаимно однозначное соответствие между множеством правильных скобочных последовательностей (п.с.п) и множеством путей Дика.

Доказательство. ПустьSиDмножества п.с.п. и путей Дика одинаковой длины соответственно.

Пустьs \in S,тогда будем писать, что

s = (i_1,i_2,\ldots,i_n),

гдеi_k = 1,если наk-ом месте стоит открывающаяся скобка, иi_k = -1,если закрывающаяся скобка.

Для элементаd \in Dвсе тоже самое, то есть

d = (i_1,i_2,\ldots,i_n),

гдеi_k = 1,еслиk-ое движение - это движение вверх, иi_k = -1,если вниз.

Осталось заметить, что для любогоs \in Sвыполнено

\sum_{t=1}^{m}i_{t} \geq 0, \quad t =1,\ldots n-1

и

\sum_{t=1}^{n}i_{t} = 0.

И тоже самое выполнено любогоd \in D.

Получаем, что множестваSиDравны. Значит, существует взаимно однозначное соответствие. Например, таковым является тождественное отображение (по сути, оно переводит открывающуюся скобку в движение вверх, а закрывающуюся в движение вниз).

Явная формула для чисел чисел Каталана

Найдем явную формулу для чисел Каталана. Для этого рассмотрим правильные скобочные последовательности длины2n.

Правильная скобочная последовательность - это

  • Пустая строка.

  • Строка вида(w), где w- правильная скобочная последовательность.

  • Строка видаw_1w_2,гдеw_1,w_2- правильные скобочные последовательности.

Первые правильные скобочные последовательности длины 2n
Первые правильные скобочные последовательности длины 2n

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

А точнее, верно следующее утверждение.

Утверждение. Каждая правильная скобочная последовательностьw(кроме пустой) имеет вид

w= (w_1)w_2,

гдеw_1,w_2- правильные скобочные последовательности.

Доказательство этого ниже.

Доказательство

Заметим, что любая правильная скобочная последовательность начинается с открывающейся скобки, иначе она не правильная скобочная последовательность. Поэтому, найдем такую закрывающуюся скобку, что

w = (w_1)w_2,

гдеw_1- правильная скобочная последовательность.

Это можно сделать следующим образом:

  1. Пустьi = 1.

  2. Рассматриваем вторую скобку.

  3. Если рассматриваемая скобка открывающаяся, то увеличиваемiна 1,иначе уменьшаем на1.

  4. Еслиi=0,то последняя рассматриваемая скобка и есть искомая, иначе рассматриваем следующую скобку и переходим к пункту 3 и 4.

Мы всегда найдем такую закрывающуюся скобку, т.к.w- правильная скобочная последовательность, а из этого следует, что количество открывающихся и закрывающихся скобок равно, то есть на последней скобкеi  = 0.

Так какw_1- правильная скобочная последовательность, то и(w_1)- правильная скобочная последовательность. Из этого следует, чтоw_2- правильная скобочная последовательность, иначеw- не правильная скобочная последовательность.

Получаем, что каждая правильная скобочная последовательность (кроме пустой) имеет выше описанный вид.

Пусть теперьC_n- n-ое число Каталана или, что тоже самое, количество правильных скобочных последовательностей длины2n.Выведем из утверждения выше рекуррентное соотношение

C_n = C_{0}C_{n-1}+C_{1}C_{n-2}+\ldots+C_{n-1}C_{0} = \sum_{i=0}^{n-1}C_{i}C_{n-i-1}
Вывод рекуррентного соотношения

Пустьw- правильная скобочная последовательность длины2n.Из утверждения выше следует, что она представима в виде

w=(w_1)w_2,

гдеw_1,w_2- правильные скобочные последовательности. Поэтому, рассмотрим варианты длинw_1и w_2.

Если длинаw_1равна0,то длинаw_2равна2n-2.Тогда, количество правильных скобочных последовательностей данного вида равноC_{0}C_{n-1}, т.к. количество правильных скобочных последовательностей длины0равноC_0,а длины2n-2равноC_{n-1.}

Если длинаw_1равна2,то длинаw_2равна2n-4.Тогда, количество правильных скобочных последовательностей данного вида равноC_{1}C_{n-2.}

Продолжая по аналогии, в конце получим. Если длинаw_1равна2n-2,то длинаw_2равна0.Тогда, количество правильных скобочных последовательностей данного вида равноC_{n-1}C_{0}.

Складывая количества правильных скобочных последовательностей каждого вида, получим количество правильных скобочных последовательностей длины 2nи искомое рекуррентное соотношение.

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

Напомню, что это такое.

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

Простыми словами, производящая функция - это следующий ряд

a_0+a_1z+a_2z^2+\ldots=\sum_{n=0}^{\infty}a_nz^n,

где коэффициентыa_0,a_1,a_2,\ldots- члены последовательности.

Более строго, пусть дана последовательность\{a_n\},тогда формально степенной рядG(z),который имеет вид

G(z) = a_0+a_1z+a_2z^2+\ldots=\sum_{n=0}^{\infty}a_nz^n,

называется производящей функциейG(z)данной последовательности.

В определение стоит обратить внимание на то, что, вообще говоря, производящая функция - это формально степенной ряд.

В отличие от обычных степенных рядов, у формально степенных рядов зачастую не рассматривают сходимость. Как следствие этого, нет смысла подставлять вместоzкакое-либо значение, за некоторым исключением. Например, если подставить в рядz=0,то G(0) = a_0.

Так зачем они вообще нужны?

А вот зачем, для формально степенных рядов можно определить операции сложения и умножения следующим образом

A(z)+B(z) = \sum_{n=0}^{\infty}a_nz^n + \sum_{n=0}^{\infty}b_nz^n = \sum_{n=0}^{\infty}(a_n + b_n)z^n = \sum_{n=0}^{\infty}c_nz^n = C(z);A(z)B(z) = (\sum_{n=0}^{\infty}a_nz^n)(\sum_{n=0}^{\infty}b_nz^n)=\sum_{n=0}^{\infty}(\sum_{k=0}^{n}a_kb_{n-k})z^n = \sum_{n=0}^{\infty}c_nz^n = C(z).

И если коэффициенты ряда принадлежат кольцуR,то и формально степенные ряды образуют кольцо относительно этих операций, которое обозначаетсяR[[z]].Так ещё оказывается, что, если кольцоRобладало каким-либо свойством, то и кольцоR[[z]]может обладать этим свойством.

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

ПустьG(z)- производящая функция последовательности чисел Каталана, то есть

G(z) = \sum_{n=0}^{\infty}C_nz^n.

Воспользуемся рекуррентным соотношением и распишем правую часть

G(z) = \sum_{n=0}^{\infty}C_nz^n = C_0 + \sum_{n=1}^{\infty}(\sum_{k=0}^{n-1}C_{k}C_{n-k-1})z^n.

Преобразуем правую часть, двойную сумму можно представить в следующем виде

 \sum_{n=1}^{\infty}(\sum_{k=0}^{n-1}C_{k}C_{n-k-1})z^n=zG^2(z).
Преобразование двойной суммы

Прежде чем переходить к преобразованию, введем определение свертки последовательностей.

Пусть даны последовательности\{a_n\}, \{b_n\} и\{c_n\}.Последовательность\{c_n\}называется сверткой последовательностей\{a_n\}и\{b_n\},если

c_n = \sum_{i=0}^{n}a_{i}b_{n-i}.

Пусть теперьA(z),B(z)иC(z)производящие функции последовательностей \{a_n\}, \{b_n\}и\{c_n\}соответственно. Тогда, из определения умножения для формально степенных рядов, следует, что

A(z)B(z) = C(z).

То есть, получаем следующее свойство. Произведение производящих функций есть производящая функция свертки последовательностей.

Рассмотрим свертку следующих последовательностей

\{C_0,C_1,C_2,\ldots\} \quad\text{и} \quad \{0,C_0,C_1,\ldots\}.

Получим последовательность

\{0,C_0C_0,C_0C_1+C_0C_1,\ldots,C_0C_{n-1}+\ldots+C_{n-1}C_0,\ldots\}.

Получаем, что множитель

\sum_{n=1}^{\infty}(\sum_{k=0}^{n-1}C_{k}C_{n-k-1})z^n

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

Производящая функция последовательности\{C_0,C_1,C_2,\ldots\}естьG(z).

Производящая функция последовательности\{0,C_0,C_1,\ldots\}есть

C_0z+C_1z^2+C_2z^3+\ldots=\sum_{n=0}^{\infty}C_nz^{n+1}=z\sum_{n=0}^{\infty}C_nz^{n}=zG(z).

Значит,

\sum_{n=0}^{\infty}(\sum_{k=0}^{n-1}C_{k}C_{n-k-1})z^n = zG^2(z).

И с тем учетом, чтоC_0=1,получаем

G(z)=1+zG^2(z).

Решаем квадратное уравнение относительноG(z)и находим, что

G(z) = \frac{1-\sqrt{1-4z}}{2z} \quad \text{или} \quad G(z) = \frac{1+\sqrt{1-4z}}{2z}.

Чтобы понять, какой знак выбрать, перепишем равенства в следующий вид

zG(z) = \frac{1-\sqrt{1-4z}}{2} \quad \text{или} \quad zG(z) = \frac{1+\sqrt{1-4z}}{2},

и подставимz=0,получим

0=0 \quad \text{или} \quad 0 = 1.

Слева верное равенство, значит

G(z) = \frac{1-\sqrt{1-4z}}{2z}.

Разложим теперь правую часть в ряд

\frac{1-\sqrt{1-4z}}{2z} = \sum_{i=0}^{n}\frac{1}{n+1}\binom{2n}{n}z^n.
Разложение правой части в ряд

Воспользуемся тем, что

(1+x)^\alpha = 1 + \sum_{n=1}^{\infty}\binom{\alpha}{n}x^n.

Тогда,

\sqrt{1-4z} = 1 + \sum_{n=1}^{\infty}\binom{\frac{1}{2}}{n}(-4z)^n.

Осталось подставить и преобразовать

\frac{1-\sqrt{1-4z}}{2z} = -\sum_{n=1}^{\infty}\binom{\frac{1}{2}}{n}\frac{(-4z)^n}{2z} = \sum_{n=0}^{\infty}(-1)^{n}\binom{\frac{1}{2}}{n+1} \cdot 2\cdot4^nz^{n}.

Преобразуем множитель\binom{\frac{1}{2}}{n+1}отдельно

\binom{\frac{1}{2}}{n+1} = \frac{\prod\limits_{k=0}^{n}(\frac{1}{2}-k)}{(n+1)!}= \frac{\prod\limits_{k=0}^{n}(1-2k)}{2^{n+1}(n+1)!}=\frac{(-1)^{n+1}\prod\limits_{k=0}^{n}(2k-1)}{2^{n+1}(n+1)!} == \frac{(-1)^{n}\prod\limits_{k=0}^{n-1}(2k+1)}{2^{n+1}(n+1)!}= \frac{(-1)^{n}\prod\limits_{k=0}^{n-1}(2k+1) \prod\limits_{k=1}^{n}(2k)}{2^{n+1} \prod\limits_{k=1}^{n}(2k)(n+1)!} = \frac{(-1)^{n}(2n)!}{2^{2n+1}\prod\limits_{k=1}^{n}k \, (n+1)!}== (-1)^n \cdot\frac{1}{2^{2n+1}} \cdot \frac{(2n)!}{n!(n+1)!} = (-1)^n \frac{1}{2^{2n+1}(n+1)}\binom{2n}{n}.

Подставляем и после сокращения, получаем

\frac{1-\sqrt{1-4z}}{2z}= \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n} z^n.

То есть

G(z)=\sum_{i=0}^{\infty}C_nz^n= \sum_{i=0}^{n}\frac{1}{n+1}\binom{2n}{n}z^n.

Получаем, что ряды равны, значит и коэффициенты перед одинаковыми степенями равны, то есть

C_n = \frac{1}{n+1}\binom{2n}{n}z^n.

Мы нашли явную формулу для чисел Каталана.

Маленькое замечание для тех, кому интересна мат. часть

А законно ли то, что мы сделали?

Например, когда выбирали знак дляG(z)или использовали ряд Тейлора для формально степенного ряда.

Правильно ли всё это?

Скучный ответ заключается в том, чтобы ответить. Вот, мы получили формулу для чисел Каталан, осталось её доказать с помощью мат. индукции. И да, это в каком-то смысле правильный ответ. Но нужно ли всё это? В данном случае, нет.

Важно понимать, что мы работаем в кольце формально степенных рядов, то есть мы должны понимать, что выражение

\frac{1-\sqrt{1-4z}}{2z}

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

Если бы мы выбрали знак плюс, то в числители получился бы ряд, который не делится на2z(2zтакже является формальным рядом).

А что значит, что один ряд делится на другой ряд?

Поделить один ряд на другой, например, рядA(z) на рядB(z), это значит решить следующее уравнение относительноC(z)

A(z)=B(z)\cdot C(z).

Если расписать равенство через коэффициенты рядов, то получится бесконечная система. Иногда она будет иметь решение, иногда нет. Это зависит от того, будет лиB(z)обратим. Достаточным и необходимым условием этого является обратимость его свободного члена (что легко доказывается).

Или эта формула

(1+x)^\alpha = 1 + \sum_{n=1}^{\infty}\binom{\alpha}{n}x^n.

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

Кроме того, что значит извлечь корень из какого-либо ряда, например, извлечь корень из рядаA(z).По сути, нужно решить следующее уравнение относительно B(z)

A(z) = B(z)\cdot B(z).

Если опять таки расписать равенство через коэффициенты рядов, то получится бесконечная система. И она опять таки иногда будет иметь решение, иногда нет.

Обратно к задаче про пьяницу

Вот мы и нашли явную формулу дляc_n,тем самым и явную формулу дляp_{2n+1}.Теперь дело за малым, подставить в сумму всё, что мы нашли, и найти эту сумму.

Имеем

P_1 =  \sum_{n=0}^{\infty}p_{2n+1} = p\sum_{i=0}^{\infty}C_n(p(1-p))^n.

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

\sum_{i=0}^{\infty}C_nz^n = \frac{1-\sqrt{1-4z}}{2z}, \quad\forall z\in\mathbb{R}: |z|\leq\frac{1}{4}.

Подставимz = p(1-p),получим

\sum_{i=0}^{\infty}C_n(p(1-p))^n = \frac{1-\sqrt{1-4p(1-p)}}{2p(1-p)}, \quad \forall p \in \mathbb{R}:p\in[0,1].

И наша сумма легко находится

P_1 = p\sum_{i=0}^{\infty}C_n(p(1-p))^n= \frac{1-\sqrt{1-4p(1-p)}}{2(1-p)}, \quad \forall p \in \mathbb{R}:p\in[0,1].
Второе маленькое пояснение для тех, кому интересна мат. часть

Было оговорено, что производящая функция - это формальный степенной ряд, а теперь мы подставляем значения вместоzи находим сумму.

Правильно ли это?

Зададимся таким вопросом, а что нам мешает вместо формально степенного ряда использовать обычный степенной ряд? А вот что, мы не можем выполнять никакие действия с рядом, пока ничего не знаем про его сходимость. Другими словами, для этого перехода мы должны исследовать сходимость этого ряда, что будет сделано ниже.

Исследование сходимости ряда

Найдем сперва радиус сходимости

\lim\limits_{n \rightarrow \infty} \frac{|C_{n+1}z^{n+1}|}{|C_nz^n|} = |z|\lim\limits_{n \rightarrow \infty} \frac{(n+1)\binom{2n+2}{n+1}}{(n+2)\binom{2n}{n}} = |z|\lim\limits_{n \rightarrow \infty} \frac{(2n+2)! n! n!}{(2n)! (n+1)! (n+1)!} ==|z|\lim\limits_{n \rightarrow \infty} \frac{(2n+1)(2n+2)}{(n+1)^2} = 4 |z| < 1 \Rightarrow |z| < \frac{1}{4}.

Теперь рассмотрим сходимость ряда приz = \frac{1}{4}

G(\frac{1}{4}) = \sum\limits_{n=0}^{\infty}\frac{C_n}{4^n}=\sum\limits_{n=0}^{\infty}\frac{1}{4^n(n+1)}\binom{2n}{n}.

Воспользуемся тем, что

\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}.

Это можно вывести из формулы Стерлинга

n! \sim	\sqrt{2\pi n} \left({n \over e}\right)^n.

Получаем

\frac{1}{4^n(n+1)}\binom{2n}{n} \sim \frac{1}{(n+1)\sqrt{\pi n}},

то есть ряд

\sum_{n=0}^{\infty}\frac{1}{(n+1)\sqrt{\pi n}},

который сходится. Значит и исходный ряд сходится приz = \frac{1}{4}.Кроме того, ряд сходится и приz=-\frac{1}{4}(абсолютная сходимость).

Таким образом, исходный ряд сходится при|z| \leq \frac{1}{4}.

Подставим теперьz=p(1-p),гдеp\in[0,1],получим ряд

\sum_{i=0}^{\infty}C_n(p(1-p))^n = \frac{1-\sqrt{1-4p(1-p)}}{2p(1-p)},

который сходится для любогоp\in[0,1],так как

|p(1-p)|\leq \frac{1}{4} \Leftrightarrow (p-\frac{1}{2})^2\geq0.

То есть все действия, который мы выполняли с исходным рядом, имеют смысл.

Это и есть ответ на нашу задачу. Пьяница упадет с обрыва, находясь при это на расстоянии одного шага от него, с вероятностью

P_1 = \frac{1-\sqrt{1-4p(1-p)}}{2(1-p)}.

Рассмотрим график этой функции (рис. 2)

Рис. 2 График функции
Рис. 2 График функции

Посмотрим, как будет меняться вероятностьP_1с ростомp.

На промежутке[0,0.5)всё в принципе очевидно. Чем большеp,тем большеP_1.Переломный же момент наступает приp=0.5.

При p= 0.5,получаем, чтоP_1 =1,то есть пьяница точно упадет с обрыва.

На промежутке[0.5,1]функцияP_1принимает постоянное значение равное единице.

Таким образом, если вероятностьp \geq0.5,то пьяница точно упадет (другими словами, это достоверное событие).

Заключение

Вот такая интересная задача, при решении которой используются сразу несколько разделов математики.

Отдельно упомяну, что при значениеp=0.5,у нас возникает случайное блуждание, которое описывается с помощью цепи Маркова. Применительно к этой задаче, её описывает цепь Маркова со счетным множеством состояний, что сложнее, чем приведенное решение, но в каком-то смысле более правильное.

Кто хочет углубиться в эту тему, ниже различная литература.

Ссылки на литературу и различные источники

Основное:

[1] Пятьдесят занимательных вероятностных задач с решениями. Ф. Мостеллер.

[2] Конкретная математика. Основание информатики (1998). Р. Грэхем, Д. Кнут, О. Паташник.

Дополнительное:

[1] Блужданья по цепям Александр Гиль и Антон Петрунин.

[2] Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения. Кельберт М. Я., Сухов Ю. М.

Прочее:

Для создания графики использовался manimCE: https://github.com/manimCommunity/manim