2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 01:13 


13/02/17

317
Varanasi
svv в сообщении #1235771 писал(а):
Если все перечисленные условия выполнены, маршрут реализуем, его длина $n$, он начинается и заканчивается в $A$. Значит, надо сосчитать все такие.


Спасибо, это Вы Dmitriy40 объяснили? Задача состоит в том, чтобы найти общую формулу, а не посчитать, но посчитать тоже было бы неплохо.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 01:16 
Заслуженный участник


23/07/08
10626
Crna Gora
Это я произношу мысли вслух. Можно сказать, обозначаю те объекты, которые надо пересчитывать.

Мы сейчас уже свободны от детального рассмотрения каждого маршрута. Каждый класс эквивалентности (множество эквивалентных маршрутов) определяется четырьмя числами.

-- Вт июл 25, 2017 02:04:11 --

Фиксируем $m=a+b+c$, чтобы $n-2m=3p$ было положительным числом, кратным $3$. Для фиксированного $m$ число неэквивалентных маршрутов равно количеству композиций числа $m$ длиной $3$ с нулевыми частями, то есть $\frac{(m+1)(m+2)}{2}$.
Остаётся просуммировать это для допустимых $m$.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:06 


13/02/17

317
Varanasi
svv
Спасибо.
Итого, имеем одно уравнение с четырьмя неизвестными:
$2(a+b+c)+3p=n$, необходимо найти выражение через $n$ для количества его решений.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:10 
Заслуженный участник


23/07/08
10626
Crna Gora
Я там чуть подредактировал. В итоге: случай отрицательных $p$ сводится к случаю положительных $p$ (в силу симметрии). Случай $p=0$ потом рассмотрим отдельно. А для положительных надо просуммировать $\frac{(m+1)(m+2)}2$ по всем таким $m\geqslant 0$, для которых $n-2m$ — положительное число, кратное $3$.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:31 


13/02/17

317
Varanasi
Это работает только для нечетных $n$(решается только перебором похоже), нужна ещё часть, работающая для четных.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:35 
Заслуженный участник


23/07/08
10626
Crna Gora
Имеете в виду, что не рассмотрен случай $p=0$, а без него можно обойтись только для нечётных $n$?

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:36 


13/02/17

317
Varanasi
svv в сообщении #1235783 писал(а):
Имеете в виду, что не рассмотрен случай $p=0$, а без него можно обойтись только для нечётных $n$?

По крайней мере мне так кажется.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:40 


20/09/05
85
Как один из способов, для вычисления вероятности попасть домой за $n$ шагов можно использовать цепи Маркова. Матрица переходных вероятностей $P$ очевидно, как составляется, ее собственные значения ищутся без труда, матрица переходных вероятностей $P^n$ за $n$ шагов в качестве собственных значений имеет $n$-е степени собственных значений матрицы $P$. Из соображений симметрии ясно, что на ее диагонали стоят равные между собой элементы, поэтому искомая вероятность равна $1/3 \operatorname{tr} P^n$, то есть трети суммы $n$-х степеней собственных значений $P$.

Чтобы совсем тоскливо не было, ответ не пишу.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 02:46 


13/02/17

317
Varanasi
Ну это видимо тоже будет количество композиций длины 3 с нулями числа $\frac{n}{2}$

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 03:20 


09/03/17
41
Условие задачи можно выразить через однородную цепь маркова.
Начальное распределение вероятностей будет П: (1, 0, 0)
Матрица вероятностей переходов P:
(0, 0.5, 0.5)
(0.5, 0, 0.5)
(0.5, 0.5, 0)

При этом P в квадрате будет:
(0.5, 0.25, 0.25)
(0.25, 0.5, 0.25)
(0.25, 0.25, 0.5)

Откуда в соответствии с эргодической теоремой (на втором шаге минимальный элемент больше нуля) получаем, что задача имеет решение (матрица переходных вероятностей имеет предел).
Нужно лишь найти предел, и умножить на П.
С пределом тут легко, если заметить, что сумма элементов в каждой строке и в каждом столбце равны единице. И что в соответствии с той самой эргодической теоремой в пределе мы получим одинаковые значения элементов внутри каждого столбца. А учитывая, что в сумме они должны дать единицу(доказывается элементарно), то этому удовлетворяет только 1/3.
Далее умножаем предельную матрицу состоящую из элементов равных 1/3 на вектор П и получаем вектор (1/3, 1/3, 1/3).
Где первый элемент является вероятностью вернуться домой, то есть ответом.

PS: Опередили xD

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 03:33 


20/09/05
85
slu4ayniyProcess
Это, конечно, хорошо, но о другом. Предельных вероятностей не требовалось, требовалась, в соответствии с буквой задачи, вероятность ровно за $n$ шагов. Это никогда не $1/3$, хотя, естественно, начиная с некоторого номера $n$, и очень быстро, поскольку зависимость экспоненциальная, значение вероятности отличается от $1/3$ незначительно. Здесь post1235715.html#p1235715 это хорошо видно. Видимость, что далее - всегда треть - это только видимость, вызванная погрешностью округления.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 03:41 
Заслуженный участник


23/07/08
10626
Crna Gora
slu4ayniyProcess, NDP
Вероятности, о которых спрашивалось в исходной задаче, мы уже посчитали. Теперь вычисляется количество замкнутых маршрутов с началом в $A$ длиной $n$, с точностью до описанной здесь эквивалентности.

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение25.07.2017, 17:38 


13/02/17

317
Varanasi
svv в сообщении #1235781 писал(а):
Я там чуть подредактировал. В итоге: случай отрицательных $p$ сводится к случаю положительных $p$ (в силу симметрии). Случай $p=0$ потом рассмотрим отдельно. А для положительных надо просуммировать $\frac{(m+1)(m+2)}2$ по всем таким $m\geqslant 0$, для которых $n-2m$ — положительное число, кратное $3$.


А как быть с невозможными случаями? Они учтены в данной редакции? И ещё, у меня что-то не получается применить практически всё это (

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение26.07.2017, 01:41 
Заслуженный участник


23/07/08
10626
Crna Gora
С какими невозможными? :-)

 Профиль  
                  
 
 Re: Вероятность вернуться домой за n шагов (случайное блуждание)
Сообщение26.07.2017, 11:07 


13/02/17

317
Varanasi
svv в сообщении #1235947 писал(а):
С какими невозможными? :-)

Рассмотрим случай $n=4$, m в данном случае может быть равно только 2. Число указанных Вами композиций равно 6-ти, в реальности же для n=4 существует 5, учитывающих "описанную эквивалентность" случаев. Т.е. Ваш метод не учитывает эту эквивалентность(дает решение задачи в стартовой постановке), либо я неправильно им пользуюсь, тогда поправьте пожалуйста меня.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 74 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group