Пьяница на мосту

[neo66]

На мосту, длина которого 100 шагов стоит пьяница. Он стоит на расстоянии 17 шагов от левого края и затем идет, шагая с равной вероятностью направо или налево. Найти вероятность того, что до левого края он дойдет быстрее, чем до правого.

[Shadow]

$\frac{83}{100}$ И логично выгядит, и потверждается. Виду простоты ответа наверное есть более простое решение, но. Пусть $p_{n}$ - вероятность, что когда-нибудь человек окажется на шаг левее своей позици - (n шагов от левого берега).
$\\p_{99}=\frac1 2\\ p_n=\frac1 2+\frac1 2\cdot p_{n+1}\cdot p_n \Rightarrow p_n=\frac{1}{2-p_{n+1}}$
или
$p_n=\frac{100-n}{101-n}$
Тогда
$P=p_{17}\cdot p_{16} \cdots p_1=\frac{83}{84}\cdot \frac{84}{85}\cdots \frac{99}{100}=\frac{83}{100}$

[neo66]

Верно. Вот другой подход: обозначим $q_n$ - вероятность того, что начиная с позиции $n$ пьяница раньше дойдет до левого края, чем до правого. Тогда $q_n=\frac 1 2 q_{n-1} + \frac 1 2 q_{n+1}$ или $q_{n+1}-q_{n}=q_{n}-q_{n-1} $. Отсюда видно, что функция $q_n$ линейна и убывает от $1$ до $0$. Значит $q_n= 1-\frac {n}{100}$.

[Shadow]

Да, так лучше. Похожая задача (но полегче):
Пьяный находится на шаг от бутылки. Делает шаг вперьед с вероятностью $p$ и шаг назад с вер. $1-p$.
а) Какова вероятность что доберется до бутылки?
б) За сколько шагов в среднем доберется до бутылки? (если доберется, конечно)

[statistonline]

Shadow в сообщении #629889 писал(а):

Да, так лучше. Похожая задача (но полегче):
Пьяный находится на шаг от бутылки. Делает шаг вперьед с вероятностью $p$ и шаг назад с вер. $1-p$.
а) Какова вероятность что доберется до бутылки?
б) За сколько шагов в среднем доберется до бутылки? (если доберется, конечно)

В такой постановке а) $P=\frac{p}{1-p(1-p)}$, б)$M=\frac{1-p}{p}$, так как это, вроде, геометрическое распределение.

[Shadow]

statistonline, с ответами не согласен. Если напишете как к ним пришли можно пообсуждать. Сразу видно, что в подусловие б) если $p=1 \Rightarrow M=1$

[statistonline]

Shadow в сообщении #629926 писал(а):

statistonline, с ответами не согласен

Да, я тоже несогласен со вторым пунктом. Это не геометрическое распределение. А про первый пункт вот:
$P=p+(1-p)p^2+(1-p)^2p^3+...=\sum_{n=1}^{\infty }(1-p)^{n-1}p^n=p\sum_{n=1}^{\infty }(p(1-p))^{n-1}=\frac{p}{1-p(p-1)}$

-- 12.10.2012, 21:44 --

$M(X)=p+3p^2(1-p)+5p^3(1-p)^2+...=\sum_{n=0}^{\infty}(2n+1)p^{n+1}(1-p)^n=p\frac{2+p-p^2-p^3}{(1-p(1-p))^2}$

[Shadow]

statistonline, я так понимаю вашу модель. Чтобы оказатся на шаг вперьед, он должен сделать или шаг вперьед, или шаг назад и потом 2 шага вперьед, или 2 шага назад и потом три вперьед....но только в такой последовательности. А если сделает 3 шага назад, потом 1 вперьед, 1 назад и 4 вперьед учтено? Он может оказатся на шаг вперьед только за нечетное число шагов. И придется решать задачу: какова вероятность, что за $2k+1$ шагов k будут назад и $k+1$ вперьед. И будут биномиальные коеффициенты в формуле, а в вашей их нет.

-- 12.10.2012, 21:04 --

И я запутался. Не будут даже биномиальные коеффициенты.

-- 12.10.2012, 21:08 --

Там сложнее. Поэтому предлагаю такую модель:
$P=p+(1-p)\cdot P \cdot P$
(Чтобы оказатся на шаг вперьед своей позиции нужно или сделать шаг вперьед, или шаг назад и два раза оказаться на шаг вперьед своей позиции)

[voipp]

Shadow в сообщении #629851 писал(а):

$\frac{83}{100}$ И логично выгядит, и потверждается. Виду простоты ответа наверное есть более простое решение, но. Пусть $p_{n}$ - вероятность, что когда-нибудь человек окажется на шаг левее своей позици - (n шагов от левого берега).
$\\p_{99}=\frac1 2\\ p_n=\frac1 2+\frac1 2\cdot p_{n+1}\cdot p_n \Rightarrow p_n=\frac{1}{2-p_{n+1}}$
или
$p_n=\frac{100-n}{101-n}$
Тогда
$P=p_{17}\cdot p_{16} \cdots p_1=\frac{83}{84}\cdot \frac{84}{85}\cdots \frac{99}{100}=\frac{83}{100}$

а как вы догадались до такого решения? )

[Corwin]

Shadow в сообщении #629889 писал(а):

Да, так лучше. Похожая задача (но полегче):
Пьяный находится на шаг от бутылки. Делает шаг вперьед с вероятностью $p$ и шаг назад с вер. $1-p$.
а) Какова вероятность что доберется до бутылки?

ИМХО 100%, если $p > 0$.

statistonline
А Ваша формула заведомо неправильная. Для $p = 1/2$ она даёт $2/3$. Даже если засчитывать поражение в случае, когда пьяница оказывается в четырёх шагах от бутылки, всё равно вероятность будет выше ($3/4$).

p.s.
Не уверен, что это является доказательством:

Обозначим $q_n$ вероятность оказаться на расстоянии n шагов от бутылки.
$q_n < (1-p^1) \cdot (1-p^2) \cdot (1-p^2) \cdot ... \cdot (1-p^{n-1})$

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

[nikvic]

neo66 в сообщении #629828 писал(а):

На мосту, длина которого 100 шагов стоит пьяница. Он стоит на расстоянии 17 шагов от левого края и затем идет, шагая с равной вероятностью направо или налево. Найти вероятность того, что до левого края он дойдет быстрее, чем до правого.

Эта задача эквивалентна игре в орлянку до разорения (известны начальные суммы). Решена чёрт знает когда одним из основателей тервера.

[Shadow]

Corwin в сообщении #727421 писал(а):

ИМХО 100%, если p > 0.

ИМХО, только если $ p\ge \frac 1 2$

[Corwin]

Не уверен, что это является доказательством:

Обозначим q_n вероятность оказаться на расстоянии n шагов от бутылки.
$q_n \leqslant (1-p^1) \cdot (1-p^2) \cdot (1-p^2) \cdot ... \cdot (1-p^{n-1})$

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

p.s. Поясню:
$q_n \leqslant q_{n-1} \cdot (1-p^{n-1})$,
где $p^{n-1}$ - это вероятность того, что оказавшись на расстоянии n-1 шагов от бутылки, пьяница начнёт двигаться только вперёд.

-- 23.05.2013, 14:12 --

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

[Corwin]

Shadow в сообщении #727425 писал(а):

Corwin в сообщении #727421 писал(а):

ИМХО 100%, если p > 0.

ИМХО, только если $ p\ge \frac 1 2$

Действительно.
Похоже, что при $p \le \frac{1}{2}$ вероятность дойти до бутылки будет равна $\frac{p}{1-p}$.

[Shadow]

Да.
А насчет вашего прежднего сообщения, это произведение не равно нулю. Потренируюсь в Tex.
$\prod\limits_{k=1}^{\infty} \left(1-\frac{1}{n^k}\right)=n^{\frac{1}{24}}\left[\frac 1 2\theta_1(0,n^{-\frac 1 2})\right]^{\frac 1 3}$