Участник:Unreal.eugene — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Случайное блуждание''' (англ. ''random walk'') {{---}} случайный процесс, состоящий из последовательности случайных шагов на каком-нибудь множестве. Обычно рассматриваются случайные блуждания на множестве целых чисел $\mathbb{Z}$ с началом в нуле и с равновероятными шагами либо на +1, либо на -1.}}
+
|definition = '''Случайное блуждание''' (англ. ''random walk'') {{---}} случайный процесс, состоящий из последовательности случайных шагов на каком-нибудь множестве. Обычно рассматриваются случайные блуждания на множестве целых чисел $\mathbb{Z}$ с началом в нуле и с равновероятными шагами либо на $+1$, либо на $-1$.}}
  
 
{{Определение
 
{{Определение
|definition = Иногда также может рассматриваться просто '''блуждание''' {{---}} комбинаторный объект, который появляется как результат случайного блуждания над целочисленной прямой. Блуждание из $n$ шагов можно однозначно задать последовательностью длины $n$, на $i$-й позиции которой стоит либо +1, либо -1, то есть битовым вектором. }}
+
|definition = Иногда также может рассматриваться просто '''блуждание''' {{---}} комбинаторный объект, который появляется как результат случайного блуждания над целочисленной прямой. Блуждание из $n$ шагов можно однозначно задать последовательностью длины $n$, на $i$-й позиции которой стоит либо $+1$, либо $-1$, то есть битовым вектором. }}
  
 
== Примеры ==
 
== Примеры ==
Строка 29: Строка 29:
 
Теорема | id=2
 
Теорема | id=2
 
|statement=
 
|statement=
Число различных блужданий длины $n$, заканчивающихся в целой координате $x$ (<tex>|x| \leq \lfloor \frac{n}{2} \rfloor</tex>), равно <tex>\binom{n}{\frac{n + x}{2}}</tex>, если $n$ и $x$ имеют одинаковую четность, и 0 иначе.
+
Число различных блужданий длины $n$, заканчивающихся в целой координате $x$ (<tex>|x| \leq \lfloor \frac{n}{2} \rfloor</tex>), равно <tex>\dbinom{n}{\frac{n + x}{2}}</tex>, если $n$ и $x$ имеют одинаковую четность, и 0 иначе.
  
 
|proof=
 
|proof=
  
Чтобы блуждание закончилось в координате $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>\binom{n}{\frac{n + x}{2}}</tex>.
+
Чтобы блуждание закончилось в координате $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
 
Теорема | 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$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула:
Строка 44: Строка 64:
  
 
|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>
Строка 52: Строка 72:
  
 
{{
 
{{
Теорема | id=4
+
Теорема | id=6
 
|statement=
 
|statement=
 
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
 
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
Строка 68: Строка 88:
  
 
<tex>W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}</tex>
 
<tex>W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}</tex>
 +
}}
 +
 +
{{
 +
Теорема | id=7
 +
|statement=
 +
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
 +
 +
<tex>W_n(t) = \dfrac{(1 - \sqrt{1 - 4t^2})^{n+1}}{2^{n+1}t^{n+2}} = t^n C^{n+1}(t^2)</tex>
 +
 +
|proof=Потом.
 +
}}
 +
 +
{{
 +
Теорема | id=8
 +
|statement=
 +
Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:
 +
 +
<tex>W(u, v) = \dfrac{C(v^2)}{1 - u v C(v^2)}</tex>
 +
 +
|proof=Потом.
 
}}
 
}}

Текущая версия на 02:36, 2 июня 2021

Определение:
Случайное блуждание (англ. 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]\dbinom{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]\dbinom{n}{\frac{n + x}{2}}[/math].
[math]\triangleleft[/math]

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

Теорема:
Математическое ожидание квадрата координаты, в которой заканчивается блуждание длины $n$, равно $n$.
Доказательство:
[math]\triangleright[/math]
Потом.
[math]\triangleleft[/math]
Теорема:
Математическое ожидание модуля координаты, в которой заканчивается блуждание длины $n$, асимптотически растёт, как [math]\mathcal O(\sqrt n)[/math].
Доказательство:
[math]\triangleright[/math]
Из предыдущей теоремы известно, что [math]E \left[ X_n^2 \right] = n[/math]. По неравенству Йенсена для математического ожидания для выпуклой функции [math]\varphi (x)[/math] выполнено [math]\varphi \left( E \left[ X \right] \right) \leq E \left[ \varphi (X) \right][/math]. Таким образом, взяв [math]X = |X_n|[/math] и [math]\varphi (x) = x^2[/math], получаем [math]E |X_n| \leq \left( E \left[ X_n^2 \right] \right)^{1/2} = \sqrt{n}[/math], а значит [math]E |X_n| = \mathcal O(\sqrt{n})[/math].
[math]\triangleleft[/math]

Производящие функции

Теорема:
Пусть $w_i$ — количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула: [math]w_n = 2 \sum\limits_{i = 0}^{n - 1}{w_i C_{n-i-1}}[/math], где $C_i$ — число Каталана.
Доказательство:
[math]\triangleright[/math]

Доказательство очень похоже на вывод формулы для числа путей Дика длины $2n$.

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

[math]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}}[/math]
[math]\triangleleft[/math]
Теорема:
Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна: [math]W(t) = \dfrac{1}{\sqrt{1 - 4t}}[/math]
Доказательство:
[math]\triangleright[/math]

Доказательство через производные можно посмотреть здесь. Далее будет приведено доказательство, использующее реккурентное соотношение из предыдущей теоремы.

Реккурентному соотношению из предыдущей теоремы соответствует равенство соответствующих формальных рядов:

$W(t) = 1 + 2 t W(t) C(t)$, где $C(t)$ — производящая функция для чисел Каталана.

Таким образом, можно выразить $W(t)$:

[math]W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}[/math]
[math]\triangleleft[/math]
Теорема:
Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна: [math]W_n(t) = \dfrac{(1 - \sqrt{1 - 4t^2})^{n+1}}{2^{n+1}t^{n+2}} = t^n C^{n+1}(t^2)[/math]
Доказательство:
[math]\triangleright[/math]
Потом.
[math]\triangleleft[/math]
Теорема:
Производящая функция для значений $w_{n,m}$ — количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна: [math]W(u, v) = \dfrac{C(v^2)}{1 - u v C(v^2)}[/math]
Доказательство:
[math]\triangleright[/math]
Потом.
[math]\triangleleft[/math]