2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Теория вероятностей. Задача про пути.
Сообщение23.11.2015, 14:54 
Здравствуйте! Есть вопрос по задаче:

Пусть $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$

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

 
 
 
 Re: Теория вероятностей. Задача про пути.
Сообщение23.11.2015, 16:39 
Аватара пользователя
toreto в сообщении #1075976 писал(а):
Пусть $x,n\in \matbb{N}$. Доказать, что доля путей из $(0;0)$ в $(n;x)$, которые не пересекают нулевой уровень, от общего числа путей из $(0;0)$ в $(n;x)$ составляет $\dfrac{x}{n}$
Раз уж ответ известен, индукцию по $n=p+q$ попробуйте

 
 
 
 Re: Теория вероятностей. Задача про пути.
Сообщение24.11.2015, 02:05 
Спасибо! А считается ли точка старта пересечением?

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

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

 
 
 
 Re: Теория вероятностей. Задача про пути.
Сообщение24.11.2015, 11:31 
Аватара пользователя
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)$, по предположению индукции, число путей в каждом классе известно, осталось проверить тождество.

 
 
 
 Re: Теория вероятностей. Задача про пути.
Сообщение24.11.2015, 13:10 
iancaple в сообщении #1076197 писал(а):
Для остальных случаев пути делятся на 2 класса $(p-1,q)$ и $(p,q-1)$, по предположению индукции, число путей в каждом классе известно, осталось проверить тождество.


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

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

Изображение

 
 
 
 Re: Теория вероятностей. Задача про пути.
Сообщение24.11.2015, 18:27 
Аватара пользователя
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$ формула уже верна. Получаем противоречие, значит то множество пусто.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group