Теория вероятностей. Задача про пути.

[toreto]

Здравствуйте! Есть вопрос по задаче:

Пусть $x,n\in \matbb{N}$. Доказать, что доля путей из $(0;0)$ в $(n;x)$, которые не пересекают нулевой уровень, от общего числа путей из $(0;0)$ в $(n;x)$ составляет $\dfrac{x}{n}$

Начнем-с) Думаю, что здесь нужно использовать принцип отражения:

Цитата:

Пусть $A$ и $B$ — точки с целыми координатами, причём $B$ лежит выше оси абсцисс и правее оси ординат, $B'$ — точка, симметричная $B$ относительно оси абсцисс.
Количество путей, начинающихся в точке $A$ и оканчивающихся в точке $B$, которые касаются оси абсцисс или пересекают её, равно числу путей, оканчивающихся в точке $B'$ .

Через $N_{n,s}$ обозначим количество путей, начинающихся в начале координат и оканчивающихся в точке $(n, s)$ . Очевидно, если среди $(1,... ,n)$ имеется $p$ единиц и $q$ минус единиц,

то $s =p-q$. Поскольку $p$ мест для положительных $i$ выбираются из $n = p + q$ имеющихся мест, $N_{p+q,p-q}=C_{p+q}^p$

Но а как дальше?

[iancaple]

toreto в сообщении #1075976 писал(а):

Пусть $x,n\in \matbb{N}$. Доказать, что доля путей из $(0;0)$ в $(n;x)$, которые не пересекают нулевой уровень, от общего числа путей из $(0;0)$ в $(n;x)$ составляет $\dfrac{x}{n}$

Раз уж ответ известен, индукцию по $n=p+q$ попробуйте

[toreto]

Спасибо! А считается ли точка старта пересечением?

А это как будет выглядеть? База $n=1$. доля $0,5$?

Переход. Если стал $n+1$ по оси абсцисс, для ординаты два расклада $x+1$ или $x-1$. Но как это привязано к доле -- не пойму.

[iancaple]

toreto в сообщении #1076120 писал(а):

Спасибо! А считается ли точка старта пересечением?

А это как будет выглядеть? База $n=1$. доля $0,5$?

Переход. Если стал $n+1$ по оси абсцисс, для ординаты два расклада $x+1$ или $x-1$. Но как это привязано к доле -- не пойму.

Точка старта пересечением не считается. а точка финиша считается (иначе утверждение неверно)
База $n=1,x=1$, доля $p=1$
В переходе надо доказать, что для $(n=p+q,x=p-q)$ доля $\frac xn$. Что эквивалентно- число путей, не пересекающих ноль, равно $C^p_{p+q}\frac {p-q}{p+q}$ Отдельно смотрим $x=0$ и/или $x=1$. Для остальных случаев пути делятся на 2 класса $(p-1,q)$ и $(p,q-1)$, по предположению индукции, число путей в каждом классе известно, осталось проверить тождество.

[toreto]

iancaple в сообщении #1076197 писал(а):

Для остальных случаев пути делятся на 2 класса $(p-1,q)$ и $(p,q-1)$, по предположению индукции, число путей в каждом классе известно, осталось проверить тождество.

Спасибо! Что-то не очень очевидно -- почему пути делятся на классы $(p-1,q)$ и $(p,q-1)$. Ведь первая координата $n$, если мы осуществляем индукционный переход, то $n$ должно только увеличиваться.

На самом деле, я уже нашел доказательство. Но и там пока что не получается разобраться. Не очевидно -- почему рассматривается точка $(1;1)$ и зачем эта разность количества путей.

[iancaple]

toreto в сообщении #1076227 писал(а):

Что-то не очень очевидно -- почему пути делятся на классы $(p-1,q)$ и $(p,q-1)$. Ведь первая координата $n$, если мы осуществляем индукционный переход, то $n$ должно только увеличиваться.

так вы же сами сказали: попасть в точку $(p+q,p-q)$ можно либо через точку $(p+q-1,p-1)$, либо через точку $(p+q-1,p)$.
---
Что должно увеличиваться? Принцип индукции : в любом непустом подмножестве натуральных чисел (для которых эта формула, возможно, неверна хотя бы для одного $x$) существует наименьший элемент $n$. Вот мы его берем и уменьшаем на единицу. А там для всех $x$ формула уже верна. Получаем противоречие, значит то множество пусто.