31
правка
Изменения
Нет описания правки
Чтобы блуждание закончилось в координате $x$, нужно, чтобы количество движений на $+1$ было на $x$ больше (на $-x$ меньше) количества движений на $-1$. Ясно, что это невозможно, если координата $x$ имеет не ту же четность, что и $n$, так как в результате любого блуждания из $n$ шагов координата, в которой мы оказываемся в конце, всегда имеет такую же четность, что и $n$. В случае однаковой четности искомое количество равно количеству битовых векторов длины $n$, в которых ровно <tex>\frac{n + x}{2}</tex> единиц. Понятно, что все такие битовые вектора можно получить следующим способом: выберем <tex>\frac{n + x}{2}</tex> позиций в векторе длины $2n$, на этих позициях расположим значение $1$, а на остальных {{---}} значение $0$. Из построения ясно, что количество таких способов по определению равно числу сочетаний <tex>\dbinom{n}{\frac{n + x}{2}}</tex>.
}}
=== Свойства случайных блужданий ===
{{
Теорема | 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=35
|statement=
Пусть $w_i$ {{---}} количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула:
|proof=
Доказательство очень похоже на вывод количества формулы для числа путей Дика длины $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>
{{
Теорема | id=46
|statement=
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
{{
Теорема | id=57
|statement=
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
{{
Теорема | id=68
|statement=
Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:
