Випадкове блукання

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Випадкове блуканняматематичний формалізм, описуючий траєкторію, яка утворюється при здійсненні послідовних випадкових кроків. Багато різних типів випадкових блукань представляють інтерес. Найчастіше розглядаються випадкові блукання, які є ланцюгами Маркова, але інші, складніші види блукань також представляють інтерес. Деякі випадкові блукання здійснюються на графах, інші — на прямій, на площині або у більш високих розмірностях, тоді як деякі блукання здійснюються на групах. Випадкові блукання також розрізняються у відношенні до часового параметру. Найчастіше блукання відбувається у дискретному часі та індексується натуральними числами X_0, X_1,X_2,\dots. Однак деякі блукання здійснюють кроки у випадкові моменти часу, і в такому випадку координата X_t визначена на неперервному промені t \geq 0.

Одновимірне дискретне випадкове блукання[ред.ред. код]

Графіки X_i(i) восьми одновимірних випадкових блукань.
Приклад двовимірного випадкового блукання. 229 кроків, довжина кроку від −0.5 до 0.5, рівноймовірні напрями x або y.

Одновимірне дискретне випадкове блукання — це випадковий процес \{Y_n\}_{n \ge 0} з дискретним часом, який має вигляд:  Y_n = Y_0 + \sum\limits_{i=1}^n X_i, де

Випадкове блукання як ланцюг Маркова[ред.ред. код]

Одномірне дискретне випадкове блукання є ланцюгом Маркова з цілими станами, чий початковий розподіл задається функцією ймовірності випадкової величиниX_0, а матриця перехідних ймовірностей має вигляд

P \equiv (p_{ij})_{i,j\in \mathbb{Z}} = 
\left(
\begin{matrix}
\ddots & \ddots & \ddots & \\
       & q_{-1} & 0 & p_{-1} &  \\
       &        & q_0 & 0    & p_0  \\
       &        &     & q_1 & 0 & p_1 \\
       &        &     &     & \ddots & \ddots & \ddots 
\end{matrix}
\right),

тобто

p_{i,i+1}\equiv \mathbb{P}(X_{n+1} = i+1 \mid X_n = i ) = p_i,
p_{i,i-1}\equiv \mathbb{P}(X_{n+1} = i-1 \mid X_n = i ) = q_i, \quad i \in \mathbb{Z},
p_{ij} \equiv \mathbb{P}(X_{n+1} = j \mid X_n = i ) = 0, \quad |i-j| \not= 1.

Теорема Донскера[ред.ред. код]

Розглянемо випадкове блукання Y_n=\sum\limits_{i=1}^{n}{X_i}, где  EX_i=0, DX_i=\sigma^2<\infty.

Центральна гранична теорема стверджує, що \frac{Y_n}{\sigma\sqrt{n}}\rightarrow N(0,1), n\rightarrow\infty за розподілом

Однак, у разі випадкових блукань, це твердження можна значно підсилити.

Побудуємо за Y_n випадковий процес S_n(t), t\in [0,1], визначивши його так: S_n(\frac{k}{n})=\frac{Y_{k}}{\sigma\sqrt{n}}, а при інших t ми довизначимо процес лінійним продовженням:

S_n(t)=(k+1-nt)S_n(\frac{k}{n})+(nt-k)S_n(\frac{k+1}{n}), t\in(\frac{k}{n},\frac{k+1}{n})

З центральної граничної теореми \forall t S_n(t)\rightarrow N(0,t), n\rightarrow\infty за розподілом

Це означає збіжність одновимірних розподілів процесу S_n(t) до одновимірних розподілів вінерівського процесу. Теорема Донскера, звана також принципом інваріантності, стверджує, що має місце слабка збіжність процесів, S_n(t)\rightarrow W(t),n\rightarrow\infty

Слабка збіжність процесів означає збіжність неперервних за вінерівською мірою функціоналів, тобто дозволяє розраховувати значення функціоналів від броунівського руху (наприклад максимуму, мінімуму, останнього нуля, моменту першого досягнення рівня та інших) граничним переходом від простого випадкового блукання.