Участник:Unreal.eugene - История изменений

Unreal.eugene в 23:36, 1 июня 2021

2021-06-01T23:36:30Z

Unreal.eugene в 21:32, 23 мая 2021

2021-05-23T21:32:11Z

Unreal.eugene: /* Производящие функции */

2021-05-21T00:20:57Z

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

Unreal.eugene: /* Производящие функции */

2021-05-21T00:20:22Z

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

Unreal.eugene: /* Свойства блужданий */

2021-05-21T00:18:00Z

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

Unreal.eugene в 17:22, 20 мая 2021

2021-05-20T17:22:00Z

Unreal.eugene в 00:29, 20 мая 2021

2021-05-20T00:29:20Z

Unreal.eugene в 00:06, 20 мая 2021

2021-05-20T00:06:51Z

Unreal.eugene в 23:13, 19 мая 2021

2021-05-19T23:13:59Z

Новая страница

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

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

== Примеры ==

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

== Пути Дика ==

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

== Свойства ==

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

{{
Теорема | id=1
|statement=
Число различных блужданий длины $n$ равно $2^n$.

|proof=
Для любого блуждания длины $n$ можно взаимно однозначно сопоставить битовый вектор длины $n$. Таким образом, количество различных блужданий длины $n$ равно количеству битовых векторов, а именно <tex>2^n</tex>.
}}

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

|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>.
}}

@@ Строка 64: / Строка 64: @@
 |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>

@@ Строка 34: / Строка 34: @@
 Чтобы блуждание закончилось в координате $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>.
 }}
@@ Строка 39: / Строка 57: @@
 {{
-Теорема | id=3
+Теорема | id=5
 |statement=
 Пусть $w_i$ {{---}} количество блужданий длины $2n$, которые оканчиваются в нуле. Тогда верна следующая рекуррентная формула:
@@ Строка 54: / Строка 72: @@
 {{
-Теорема | id=4
+Теорема | id=6
 |statement=
 Производящая функция для количества блужданий чётной длины, заканчивающихся в нулевой координате, равна:
@@ Строка 73: / Строка 91: @@
 {{
-Теорема | id=5
+Теорема | id=7
 |statement=
 Производящая функция для количества блужданий, заканчивающихся в некоторой положительной координате $n$ и не заходящих в отрицательную полупрямую, равна:
@@ Строка 83: / Строка 101: @@
 {{
-Теорема | id=6
+Теорема | id=8
 |statement=
 Производящая функция для значений $w_{n,m}$ {{---}} количества блужданий длины $n$, заканчивающихся в некоторой положительной координате $m$ и не заходящих в отрицательную полупрямую, равна:

@@ Строка 48: / Строка 48: @@
 Доказательство очень похоже на вывод количества путей Дика длины $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>

@@ Строка 48: / Строка 48: @@
 Доказательство очень похоже на вывод количества путей Дика длины $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>

@@ Строка 33: / Строка 33: @@
 |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>\dbinom{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>.
 }}

@@ Строка 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$, то есть битовым вектором. }}
 == Примеры ==
@@ Строка 33: / Строка 33: @@
 |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>\dbinom{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>.
 }}
@@ Строка 48: / Строка 48: @@
 Доказательство очень похоже на вывод количества путей Дика длины $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>

@@ Строка 29: / Строка 29: @@
 Теорема | id=2
 |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=
-Чтобы блуждание закончилось в координате $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>.
 }}
 {{
@@ Строка 68: / Строка 70: @@
 <tex>W(t) = \dfrac{1}{1 - 2 t C(t)} = \dfrac{1}{\sqrt{1 - 4 t}}</tex>
 }}