Участник:Unreal.eugene

Определение:

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

Определение:

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

Примеры

Тут когда-нибудь появятся примеры

Пути Дика

Что-то про пути Дика

Свойства

Свойства блужданий

Теорема:

Число различных блужданий длины $n$ равно $2^n$.

Доказательство:

[math]\triangleright[/math]

Для любого блуждания длины $n$ можно взаимно однозначно сопоставить битовый вектор длины $n$. Таким образом, количество различных блужданий длины $n$ равно количеству битовых векторов, а именно [math]2^n[/math].

[math]\triangleleft[/math]

Теорема:

Число различных блужданий длины $n$, заканчивающихся в целой координате $x$ ([math]|x| \leq \lfloor \frac{n}{2} \rfloor[/math]), равно [math]\binom{n}{\frac{n + x}{2}}[/math], если $n$ и $x$ имеют одинаковую четность, и 0 иначе.

Доказательство:

[math]\triangleright[/math]

Чтобы блуждание закончилось в координает $x$, нужно, чтобы количество движений на +1 было на $x$ больше ($-x$ меньше) количества движений на -1. Ясно, что это невозможно, если координата $x$ имеет не ту же четность, что и $n$, так как в результате любого блуждания из $n$ шагов координата, в которой мы оказываемся в конце, всегда имеет такую же четность, что и $n$. В случае однаковой четности искомое количество равно количеству битовых векторов длины $n$, в которых ровно [math]\frac{n + x}{2}[/math] единиц. Понятно, что все такие битовые вектора можно получить следующим способом: выберем [math]\frac{n + x}{2}[/math] позиций в векторе длины $2n$, на этих позициях расположим значение 1, а на остальных — значение 0. Из построения ясно, что количество таких способов по определению равно числу сочетаний [math]\binom{n}{\frac{n + x}{2}}[/math].

[math]\triangleleft[/math]