Изменения

|definition = '''Случайное блуждание''' (англ. ''random walk'') {{---}} случайный процесс, состоящий из последовательности случайных шагов на каком-нибудь множестве. Обычно рассматриваются случайные блуждания на множестве целых чисел $\mathbb{Z}$ с началом в нуле и с равновероятными шагами либо на $+1$, либо на $-1$.}}

|definition = Иногда также может рассматриваться просто '''блуждание''' {{---}} комбинаторный объект, который появляется как результат случайного блуждания над целочисленной прямой. Блуждание из $n$ шагов можно однозначно задать последовательностью длины $n$, на $i$-й позиции которой стоит либо $+1$, либо $-1$, то есть битовым вектором. }}

Чтобы блуждание закончилось в координате $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>.

Рассмотрим позицию последнего пересечения путем блуждания нулевой координаты, не равную $2n$. Пусть эта координата равна $2x$, тогда после этого есть два варианта развития: перемещение либо на $+1$, либо на $-1$. В обоих случаях путь в следующий раз пересечёт нулевую координату только на $2n$-ое пермещение, поэтому при перемещении из координаты $2x$ далее лежит путь Дика длины $2n - 2x - 2$, не заходящий либо левее координаты $1 $ (в случае перемещений $+1$), либо не заходящий правее кординаты $-1 $ (в случае перемещения $-1$). Количество путей Дика длины $2n - 2x - 2$ равно $C_{n-x-1}$. Так как в каждом пути существует последняя позиция пересечения нулевой координаты, не равная $2n$, то можно рекурсивно посчитать все блуждания следующим образом: