Редактирование: Участник:Unreal.eugene

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 36: Строка 36:
 
}}
 
}}
  
=== Свойства случайных блужданий ===
+
== Производящие функции ==
  
 
{{
 
{{
 
Теорема | id=3
 
Теорема | id=3
|statement=
 
Математическое ожидание квадрата координаты, в которой заканчивается блуждание длины $n$, равно $n$.
 
|proof=
 
Потом.
 
}}
 
 
{{
 
Теорема | id=4
 
|statement=
 
Математическое ожидание модуля координаты, в которой заканчивается блуждание длины $n$, асимптотически растёт, как <tex>\mathcal O(\sqrt n)</tex>.
 
|proof=
 
Из предыдущей теоремы известно, что <tex>E \left[ X_n^2 \right] = n</tex>. По неравенству Йенсена для математического ожидания для выпуклой функции <tex>\varphi (x)</tex> выполнено <tex>\varphi \left( E \left[ X \right] \right) \leq E \left[ \varphi (X) \right]</tex>. Таким образом, взяв <tex>X = |X_n|</tex> и <tex>\varphi (x) = x^2</tex>, получаем <tex>E |X_n| \leq \left( E \left[ X_n^2 \right] \right)^{1/2} = \sqrt{n}</tex>, а значит <tex>E |X_n| = \mathcal O(\sqrt{n})</tex>.
 
}}
 
 
== Производящие функции ==
 
 
{{
 
Теорема | id=5
 
 
|statement=
 
|statement=
 
Пусть $w_i$ {{---}} количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула:
 
Пусть $w_i$ {{---}} количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула:
Строка 64: Строка 46:
  
 
|proof=
 
|proof=
Доказательство очень похоже на вывод формулы для числа путей Дика длины $2n$.  
+
Доказательство очень похоже на вывод количества путей Дика длины $2n$.  
  
Рассмотрим номер шага не равного $2n$, на котором траектория блуждания последний раз заходит в нулевую координату. Пусть эта координата равна $2x$, тогда после этого есть два варианта развития: перемещение либо на $+1$, либо на $-1$. В обоих случаях путь в следующий раз пересечёт нулевую координату только на $2n$-ое пермещение, поэтому при перемещении из координаты $2x$ далее лежит путь Дика длины $2n - 2x - 2$, не заходящий либо левее координаты $1$ (в случае перемещения $+1$), либо правее кординаты $-1$ (в случае перемещения $-1$). Количество путей Дика длины $2n - 2x - 2$ равно $C_{n-x-1}$. Так как у каждого блуждания есть его последняя позиция пересечения нулевой координаты, не равная $2n$, то можно рекурсивно посчитать все блуждания следующим образом:
+
Рассмотрим позицию последнего пересечения путем блуждания нулевой координаты, не равную $2n$. Пусть эта координата равна $2x$, тогда после этого есть два варианта развития: перемещение либо на $+1$, либо на $-1$. В обоих случаях путь в следующий раз пересечёт нулевую координату только на $2n$-ое пермещение, поэтому при перемещении из координаты $2x$ далее лежит путь Дика длины $2n - 2x - 2$, не заходящий либо левее координаты $1$ (в случае перемещений $+1$), либо правее кординаты $-1$ (в случае перемещения $-1$). Количество путей Дика длины $2n - 2x - 2$ равно $C_{n-x-1}$. Так как в каждом пути существует последняя позиция пересечения нулевой координаты, не равная $2n$, то можно рекурсивно посчитать все блуждания следующим образом:
  
 
<tex>w_n = \sum\limits_{x = 0}^{n - 1}{w_x \cdot 2 C_{n-x-1}} = 2 \sum\limits_{i = 0}^{n - 1}{w_i C_{n-i-1}}</tex>
 
<tex>w_n = \sum\limits_{x = 0}^{n - 1}{w_x \cdot 2 C_{n-x-1}} = 2 \sum\limits_{i = 0}^{n - 1}{w_i C_{n-i-1}}</tex>
Строка 72: Строка 54:
  
 
{{
 
{{
Теорема | id=6
+
Теорема | id=4
 
|statement=
 
|statement=
 
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
 
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
Строка 91: Строка 73:
  
 
{{
 
{{
Теорема | id=7
+
Теорема | id=5
 
|statement=
 
|statement=
 
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
 
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
Строка 101: Строка 83:
  
 
{{
 
{{
Теорема | id=8
+
Теорема | id=6
 
|statement=
 
|statement=
 
Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:
 
Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: