16.14: Випадкові прогулянки по графіках

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

Основна теорія

Вступ

Припустимо, що\( G = (S, E) \) це граф з набором вершин\( S \) та набором ребер\( E \subseteq S^2 \). Ми припускаємо, що граф є неорієнтованим (можливо, кращий термін буде двонаправленим) в тому сенсі, що\( (x, y) \in E \) якщо і тільки якщо\( (y, x) \in E \). Набір вершин\( S \) є підрахунковим, але може бути нескінченним. Нехай\( N(x) = \{y \in S: (x, y) \in E\} \) позначають безліч сусідів вершини\( x \in S \), і нехай\( d(x) = \#[N(x)] \) позначають ступінь\( x \). Припускаємо, що\( N(x) \neq \emptyset \) для\( x \in S \), тому не\( G \) має ізольованих точок.

Припустимо, тепер, коли є провідність,\( c(x, y) \gt 0 \) пов'язана з кожним ребром\( (x, y) \in E \). Провідність симетрична в тому сенсі, що\( c(x, y) = c(y, x) \) для\( (x, y) \in E \). Ми\( c \) поширюємося на функцію на всіх,\( S \times S \) визначаючи\( c(x, y) = 0 \) для\( (x, y) \notin E \). Нехай\[ C(x) = \sum_{y \in S} c(x, y), \quad x \in S \] так, що\( C(x) \) це загальна провідність країв, що виходять з\( x \). Наше головне припущення полягає в тому, що\( C(x) \lt \infty \) для\( x \in S \). Як випливає з термінології, ми уявляємо рідину якогось роду, що протікає через краї графіка, так що провідність ребра вимірює ємність ребра в певному сенсі. Однією з кращих інтерпретацій є те, що графік - це електрична мережа, а ребра - резистори. У цій інтерпретації провідність резистора є зворотною опору.

У деяких додатках, зокрема тільки що згаданої резисторної мережі, доречно накладати додаткове припущення, що не\( G \) має шлейфів, так що\( (x, x) \notin E \) для кожного\( x \in S \). Однак це припущення не є математично необхідним для ланцюгів Маркова, які ми розглянемо в цьому розділі.

Марковський ланцюг дискретного часу\( \bs{X} = (X_0, X_1, X_2, \ldots) \) з простором стану\( S \) та матрицею\( P \) ймовірностей переходу\[ P(x, y) = \frac{c(x, y)}{C(x)}, \quad (x, y) \in S^2 \] називається випадковою прогулянкою на графіку\( G \).

обгрунтування

По-перше,\( P(x, y) \ge 0 \) для\( x, \, y \in S \). Далі, за визначенням\( C \),\[ \sum_{y \in S} P(x, y) = \sum_{y \in S} \frac{c(x, y)}{C(x)} = \frac{C(x)}{C(x)} = 1, \quad x \in S \] sp\( P \) є коректною матрицею переходу на\( S \). Крім того,\( P(x, y) \gt 0 \) якщо і тільки\( c(x, y) \gt 0 \) якщо і тільки якщо\( (x, y) \in E \), так що граф стану\( \bs{X} \) є\( G \), графік ми почали з.

Цей ланцюжок керує частинкою, що рухається вздовж вершин\( G \). Якщо частка знаходиться у вершині\( x \in S \) в даний момент часу, то частка буде у сусіда\( x \) в наступний раз; сусід вибирається випадковим чином, пропорційно провідності. У налаштуванні електричної мережі природно інтерпретувати частинку як електрон. Зверніть увагу, що множення функції провідності\( c \) на позитивну константу не впливає на пов'язану випадкову прогулянку.

Припустимо, що\( d(x) \lt \infty \) для кожного\( x \in S \) і\( c \) те постійне по краях. Тоді

1. \( C(x) = c d(x) \)для кожного\( x \in S \).
2. Матриця переходу\( P \) задається\( P(x, y) = \frac{1}{d(x)}\) for\( x \in S\) і\(y \in N(x) \), і в\( P(x, y) = 0 \) іншому випадку.

Марковський ланцюг дискретного часу\( \bs{X} \) - це симетрична випадкова прогулянка далі\( G \).

Доказ

1. \( C(x) = \sum_{y \in N(x)} c(x, y) = c \#[N(x)] = c d(x) \)для\( x \in S \).
2. \( P(x, y) = c(x, y) / C(x) = c / c d(x) = 1 / d(x) \)для\( x \in S \) і\( y \in N(x) \)

Таким чином, для симетричної випадкової ходьби, якщо стан знаходиться\( x \in S \) в даний момент часу, то наступним станом з однаковою ймовірністю буде будь-який з сусідів\( x \). Припущення, що кожна вершина має скінченний ступінь, означає, що граф\( G \) є локально скінченним.

\( \bs{X} \)Дозволяти випадкова прогулянка на графіку\( G \).

1. Якщо\( G \) підключений\( \bs{X} \), то нескоротний.
2. Якщо\( G \) не зв'язано, то класи еквівалентності\( \bs{X} \) є складовими\( G \) (максимальних зв'язаних підмножин\( S \)).

Доказ

1. Нагадаємо, що існує шлях довжини\( n \in \N_+ \) між різними станами\( x, \, y \in S \) в графі стану\( \bs{X} \) if і тільки якщо\( P^n(x, y) \gt 0 \). Якщо\( G \) це пов'язано, між кожною парою різних вершин є шлях, і, отже, ланцюг\( \bs{X} \) є незвідним.
2. Це випливає з (а).

Отже, як завжди, ми зазвичай припускаємо, що\( G \) це пов'язано, бо інакше ми могли б просто обмежити нашу увагу компонентом\( G \). У разі, що не\( G \) має петель (знову ж таки, важливий особливий випадок через аплікацій), легко охарактеризувати періодичність ланцюга. Для наступної теореми нагадаємо, що\( G \) є двороздільним, якщо набір вершин\( S \) може бути розділений на непорожні, нез'єднані множини\( A \) і\( B \) (частини) таким чином, що кожне ребро\( E \) має одну кінцеву точку в\( A \) і одну кінцеву точку в\( B \).

Припустимо, що\( \bs{X} \) це випадкова прогулянка по зв'язаному\( G \) графіку без петель. Потім\( \bs{X} \) є або аперіодичним, або має період 2. Крім того,\( \bs{X} \) має період 2 тоді і тільки тоді, коли\( G \) є двостороннім, і в цьому випадку частини є циклічними класами\( \bs{X} \).

Доказ

Спочатку відзначимо,\( G \) що оскільки з'єднана, ланцюг\( \bs{X} \) є нескорочуваною, і тому всі стани мають однаковий період. Якщо\( (x, y) \in E \) потім\( (y, x) \in E \) також, так повертається до\( x \in S \), починаючи з завжди\( x \) може відбуватися навіть з натуральних чисел. Якщо\( G \) двороздільний, то повернення до\( x \) початку\( x \) може чітко відбуватися тільки при парних позитивних цілих числах, тому період дорівнює 2. І навпаки, якщо\( G \) не двосторонній, то\( G \) має цикл непарної довжини\( k \). Якщо\( x \) є вершиною на циклі, то повернення до\( x \), починаючи з\( x \), може відбуватися в 2 кроки або по\( k \) кроках, тому період\( x \) дорівнює 1.

Позитивні рекурренти та інваріантні розподіли

Припустимо ще раз, що\( \bs{X} \) це випадкова прогулянка на графіку\( G \), і припустимо, що\( G \)\( \bs{X} \) пов'язано так, що є незвідним.

Функція\( C \) є інваріантною для\( P \). Випадкова прогулянка\( \bs{X} \) є додатною рекуррентною тоді\[ K = \sum_{x \in S} C(x) = \sum_{(x, y) \in S^2} c(x, y) \lt \infty \] і лише тоді, коли інваріантна функція щільності ймовірності\( f \) задається\( f(x) = C(x) / K \) за допомогою for\( x \in S \).

Доказ

Бо\( y \in S \),\[ (C P)(y) = \sum_{x \in S} C(x) P(x, y) = \sum_{x \in N(y)} C(x) \frac{c(x, y)}{C(x)} = \sum_{x \in N(y)} c(x, y) = C(y) \] так\( C \) є інваріантним для\( P \). Інші результати випливають із загальної теорії.

Зверніть увагу, що\( K \) це загальна провідність по всіх краях в\( G \). Зокрема, звичайно, якщо\( S \) кінцевий, то\( \bs{X} \) позитивний рецидив, з\( f \) як інваріантна функція щільності ймовірності. Для симетричної випадкової ходьби це єдиний спосіб позитивного повторення:

Симетрична випадкова прогулянка на\( G \) є додатною рекуррентною тоді і лише тоді, коли множина вершин\( S \) скінченна, в цьому випадку інваріантна функція щільності ймовірності\( f \)\( d \) задається тим,\[ f(x) = \frac{d(x)}{2 m}, \quad x \in S \] де - функція ступеня, а де\( m \) - кількість неспрямованих ребер.

Доказ

Якщо взяти функцію провідності постійною 1 по краях, то\( C(x) = d(x) \) і\( K = 2 m \).

З іншого боку, коли\( S \) нескінченно, класифікація\( \bs{X} \) як рецидивна або минуща ускладнена. Нижче ми розглянемо цікавий особливий випадок, симетричну випадкову прогулянку далі\( \Z^k \).

оборотність

По суті, всі оборотні ланцюги Маркова можна інтерпретувати як випадкові прогулянки на графіках. Цей факт є однією з причин вивчення таких прогулянок.

Якщо\( \bs{X} \) є випадковою прогулянкою по зв'язковому графіку\( G \), то\( \bs{X} \) є оборотним щодо\( C \).

Доказ

Так як графік пов'язаний,\( \bs{X} \) є незведеним. Найважливіше спостереження полягає\( (x, y) \in E \) в тому, що\[ C(x) P(x, y) = C(y) P(y, x), \quad (x, y) \in S^2 \] Якщо ліва сторона є,\( c(x, y) \) а права -\( c(y, x) \). Якщо\( (x, y) \notin E \), обидві сторони дорівнюють 0. Потім випливає із загальної теорії, яка\( C \) є інваріантною для\( \bs{X} \) і яка\( \bs{X} \) є оборотною щодо\( C \).

Звичайно, якщо\( \bs{X} \) рецидивна, то\( C \) є єдиною позитивною інваріантною функцією, аж до множення на позитивні константи, і так\( \bs{X} \) просто оборотна.

І навпаки, припустимо, що\( \bs{X} \) це незведена ланцюжок Маркова на\( S \) з матрицею переходу\( P \) та додатною інваріантною функцією\( g \). Якщо\( \bs{X} \) є оборотним відносно\( g \) то\( \bs{X} \) є випадковою прогулянкою на графіку стану з функцією провідності,\( c \) заданою\( c(x, y) = g(x) P(x, y) \) for\( (x, y) \in S^2 \).

Доказ

Оскільки\( \bs{X} \) є оборотним щодо\( g \),\( g \) і\( P \) задовольняє\( g(x) P(x, y) = g(y) P(y, x) \) для кожного\( (x, y) \in S^2 \). Зверніть увагу, що граф\( G \) стану\( \bs{X} \) є двонаправленим, оскільки\( P(x, y) \gt 0 \) якщо і тільки якщо\( P(y, x) \gt 0 \), і що функція,\( c \) наведена в теоремі, симетрична, так що\( c(x, y) = c(y, x) \) для всіх\( (x, y) \in S^2 \). Нарешті, зверніть увагу, що\[ C(x) = \sum_{y \in S} c(x, y) = \sum_{y \in S} g(x) P(x, y) = g(x), \quad x \in S \] так\( P(x, y) = c(x, y) \big/ C(x) \) для\( (x, y) \in S^2 \), як потрібно.

Знову ж таки, у важливому особливому випадку, який\( \bs{X} \) є рецидивуючим, існує позитивна\( g \) інваріантна функція, яка є унікальною аж до множення на позитивні константи. У цьому випадку теорема стверджує, що незведена, рекурентна, оборотна ланцюг - це випадкова прогулянка на графі стану.

Приклади і застосування

Графік мосту Уїтстоуна

Графік нижче називається мостом Уїтстоун на честь Чарльза Уітстоуна.

Малюнок\(\PageIndex{1}\): Мережа мостів Уїтстона, зі значеннями провідності червоним кольором

У цьому підрозділі, нехай\( \bs{X} \) буде випадкова прогулянка по Уїтстоунському мосту вище, з заданими значеннями провідності.

За випадкову прогулянку\( \bs{X} \),

1. Явно наведіть матрицю ймовірності переходу\( P \).
2. Задано\( X_0 = a \), знайдіть функцію щільності ймовірності\( X_2 \).

Відповідь

Для матриці і вектора нижче використовуємо впорядкований простір стану\( S = (a, b, c, d) \).

1. \( P = \left[ \begin{matrix} 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{5} & \frac{2}{5} & \frac{2}{5} & 0 \end{matrix} \right] \)
2. \( f_2 = \left( \frac{9}{40}, \frac{1}{5}, \frac{13}{40}, \frac{1}{4} \right) \)

За випадкову прогулянку\( \bs{X} \),

1. Покажіть, що\( \bs{X} \) є аперіодичним.
2. Знайдіть інваріантну функцію щільності ймовірності.
3. Знайдіть середній час повернення до кожного стану.
4. Знайти\( \lim_{n \to \infty} P^n \).

Відповідь

Для матриці і векторів нижче ми використовуємо впорядкований простір стану\( (a, b, c, d) \).

1. Ланцюг є аперіодичним, оскільки графік не є двостороннім. (Зауважте, що графік має трикутники.)
2. \( f = \left(\frac{1}{7}, \frac{2}{7}, \frac{3}{14}, \frac{5}{14} \right) \)
3. \( \mu = \left(7, \frac{7}{2}, \frac{14}{3}, \frac{14}{5} \right) \)
4. \( P^n \to \left[ \begin{matrix} \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \end{matrix} \right] \)як\( n \to \infty \)

Графік куба

Графік нижче - це тривимірний граф куба. Вершини є бітовими рядками довжиною 3, а дві вершини з'єднуються ребром тоді і тільки тоді, коли бітові рядки відрізняються на один біт.

Малюнок\(\PageIndex{2}\): Графік куба зі значеннями провідності червоним кольором

У цьому підрозділі давайте\( \bs{X} \) позначимо випадкову прогулянку на графіку куба вище, з заданими значеннями провідності.

За випадкову прогулянку\( \bs{X} \),

1. Явно наведіть матрицю ймовірності переходу\( P \).
2. Припустимо, що початковий розподіл є рівномірним розподілом на\( \{000, 001, 101, 100\} \). Знайдіть функцію щільності ймовірності\( X_2 \).

Відповідь

Для матриці і вектора нижче використовуємо впорядкований простір стану\( S = (000, 001, 101, 110, 010, 011, 111, 101 ) \).

1. \( P = \left[ \begin{matrix} 0 & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{3}{9} & 0 & \frac{3}{8} \\ 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} & 0 \\ 0 & 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} \\ 0 & 0 & 0 & \frac{1}{4} & \frac{3}{8} & 0 & \frac{3}{8} & 0 \end{matrix} \right] \)
2. \( f_2 = \left(\frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}\right) \)

За випадкову прогулянку\( \bs{X} \),

1. Покажіть, що ланцюжок має період 2 і знайдіть циклічні класи.
2. Знайдіть інваріантну функцію щільності ймовірності.
3. Знайдіть середній час повернення до кожного стану.
4. Знайти\( \lim_{n \to \infty} P^{2 n} \).
5. Знайти\( \lim_{n \to \infty} P^{2 n + 1} \).

Відповідь

Для матриці і вектора нижче використовуємо впорядкований простір стану\( S = (000, 001, 101, 110, 010, 011, 111, 101) \).

1. Ланцюг має період 2, оскільки графік є двостороннім. Циклічні класи є\( \{000, 011, 110, 101\} \) (бітові рядки з парним числом 1) і\( \{010, 001, 100, 111\} \) (бітові рядки з непарним числом 1).
2. \( f = \left(\frac{1}{12}, \frac{1}{12}, \frac{1}{12}, \frac{1}{12}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}\right) \)
3. \( \mu = (12, 12, 12, 12, 6, 6, 6, 6) \)
4. \( P^{2 n} \to \left[ \begin{matrix} \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \end{matrix} \right] \)як\( n \to \infty \)
6. \( P^{2 n + 1} \to \left[ \begin{matrix} 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \end{matrix} \right] \)як\( n \to \infty \)

Спеціальні моделі

Нагадаємо, що базова ланцюг Ehrenfest з\( m \in \N_+ \) кульками оборотна. Інтерпретуючи ланцюг як випадкову прогулянку по графіку, накидайте графік і знайдіть функцію провідності.

Відповідь

Графік стану\( G \) базової ланцюжка Еренфест з\( m \) кульками - шлях від 0 до\( m \) без петель. Функція провідності\( c \) -\( c(x, x + 1) = \binom{m - 1}{x} \) для\( x \in \{0, 1, \ldots, m - 1\} \).

Нагадаємо, що модифікована ланцюг Ehrenfest з\( m \in \N_+ \) кульками оборотна. Інтерпретуючи ланцюг як випадкову прогулянку по графіку, накидайте графік і знайдіть функцію провідності.

Відповідь

Графік стану\( G \) зміненого ланцюжка Еренфеста з\( m \) кульками - шлях від 0 до\( m \) з петлями. Функція провідності\( c \) -\( c(x, x + 1) = \frac{1}{2}\binom{m - 1}{x} \) for\( x \in \{0, 1, \ldots, m - 1\} \) і\( c(x, x) = \frac{1}{2} \binom{m}{x} \) for\( x \in \{0, 1, \ldots, m\} \).

Нагадаємо, що ланцюг Бернуллі-Лапласа з\( j \in \N_+ \) кульками в урні 0,\( k \in \N_+\) кульками в урні 1, а з\( r \in \{0, \ldots, j + k\} \) кульок червоного кольору, є оборотною. Інтерпретуючи ланцюг як випадкову прогулянку по графіку, накидайте графік і знайдіть функцію провідності. Спростити функцію провідності в особливому випадку, що\( j = k = r \).

Відповідь

\( G \)Графік стану ланцюга Бернуллі-Лапаса з\( j \) кульками в урні 0,\( k \) кульками в урні 1, а з\( r \) кульок червоного кольору - шлях від\( \max\{0, r - j\} \) до\( \min\{k, r\} \) з петлями. Функція провідності\( c \) задається\ begin {align*} c (x, x + 1) & =\ binom {r} {x}\ binom {j + k - r} {k - x} (r - x) (k - x),\ quad x\ in\ {\ max\ {0, r - j\},\ ldots,\ min\ {k, r\} - 1\\\\ c (x, x) & =\ біном {r} {x}\ біном {j + k - r} {k - x} [(r - х) х + (j - r + x) (k - x)],\ квадрад х\ in\ {\ max\ {0, r - j \},\ ldots,\ min\ {k, r\}\ end {align*} В особливому випадку\( j = k = r \), що функцією провідності є\ begin {align*} c (x, x + 1) & =\ binom {k} {x} {k - x} (k - x) ^2,\ quad x\ in\ {0,\ ldots, k - 1\}\ c (x, x) & =\ binom {k} {x}\ binom {k} {k - x} 2 x (k - x),\ квадратний х\ in\ {0,\ ldots, k\}\ end {вирівнювання *}

Випадкові прогулянки на\( \Z \)

Випадкові прогулянки на цілих гратах особливо цікаві через їх класифікацію як перехідні або рекурентні. Розглянемо одновимірний випадок в цьому підрозділі, а більш високий розмірний - в наступному підрозділі.

\( \bs{X} = (X_0, X_1, X_2, \ldots) \)Дозволяти дискретно-часовий ланцюжок Маркова з простором стану\( \Z \) та матрицею ймовірностей переходу,\( P \) заданою\[ P(x, x + 1) = p, \; P(x, x - 1) = 1 - p, \quad x \in \Z \] де\( p \in (0, 1) \). Ланцюжок\( \bs{X} \) називається простою випадковою\( \Z \) прогулянкою по параметру\( p \).

Термін простий використовується, оскільки ймовірності переходу, починаючи з стану,\( x \in \Z \) не залежать від\( x \). Таким чином, ланцюг є просторово, а також тимчасово однорідною. В особливому випадку\( p = \frac{1}{2} \) ланцюг\( \bs{X} \) являє собою просту симетричну випадкову прогулянку далі\( \Z \). Основні властивості простої випадкової ходьби\( \Z \), зокрема, простої симетричної випадкової ходьби були вивчені в розділі про випробування Бернуллі. Звичайно, граф\( G \) стану\( \bs{X} \) має набір вершин\( \Z \), а\( x \in \Z \) сусіди -\( x + 1 \) і\( x - 1 \). Не відразу зрозуміло, що\( \bs{X} \) це випадкова прогулянка по\( G \) пов'язана з функцією провідності, яка врешті-решт, є темою цього розділу. Але цей факт і багато іншого випливають з наступного результату.

\( g \)Дозволяти бути функція на\( \Z \)\[ g(x) = \left(\frac{p}{1 - p}\right)^x, \quad x \in \Z \] визначена потім

1. \(g(x) P(x, y) = g(y) P(y, x)\)для всіх\( (x, y) \in \Z^2 \)
2. \( g \)є інваріантним для\( \bs{X} \)
3. \( \bs{X} \)є оборотним щодо\( g \)
4. \( \bs{X} \)- випадкова прогулянка\( \Z \) з функцією провідності,\( c \) заданою\( c(x, x + 1) = p^{x+1} \big/ (1 - p)^x \) for\(x \in \Z \).

Доказ

1. Для\( x \in \Z \), нам потрібно лише розглянути\( y = x \pm 1 \). \ почати {вирівнювати*} г (х) Р (х, х - 1) & =\ розриву {p^x} {(1 - р) ^ {x-1}} = г (х - 1) Р (х - 1, х)\ г (х) Р (х, х + 1) & =\ розриву {р^ {x+1}} {(1 - р) ^x} = г х + 1) Р (х + 1, х)\ кінець {вирівнювати*}
2. Це випливає з (а) і загальної теорії.
3. Це випливає з (а) і (б) і загальної теорії.
4. З наведеного вище результату\( \bs{X} \) - випадкова прогулянка на\( G \) пов'язана з функцією провідності,\( c \) заданою\( c(x, y) = g(x) P(x, y) \). За симетрії досить розглянути ребро\( (x, x + 1) \), і в цьому випадку,\( c \) дається в другому відображеному рівнянні вище.

Зокрема, проста симетрична випадкова ходьба - це симетрична випадкова прогулянка далі\( G \).

Ланцюг\( \bs{X} \) нескорочується і періодична з періодом 2. Більш того\[ P^{2 n}(0, 0) = \binom{2 n}{n} p^n (1 - p)^n, \quad n \in \N \]

Доказ

Ланцюг нескоротна, так як\( G \) з'єднана. Ланцюг є періодичним, оскільки не\( G \) має петель і є двостороннім, причому частини є непарними і парними цілими числами. Нарешті, зауважте, що починаючи з стану 0, ланцюжок повертається до 0 в той час\( 2 n \), коли і тільки якщо є\( n \) кроки праворуч і\( n \) кроки ліворуч.

Класифікація простої випадкової ходьби по\( \Z \).

1. Якщо\( p \ne \frac{1}{2} \) потім\( \bs{X} \) є тимчасовим.
2. Якщо\( p = \frac{1}{2} \) тоді\( \bs{X} \) є нульовим повторюваним.

Доказ

З попереднього результату і наближення Стірлінга,\[ P^{2 n}(0, 0) \approx \frac{[4 p (1 - p)]^n}{\sqrt{\pi \, n}} \text{ as } n \to \infty \] Нехай\( R(x, y) = \sum_{n=0}^\infty P^n(x, y) \) для\( (x, y) \in \Z^2 \), так що\(R\) потенційна матриця. Нагадаємо, що\( R(x, y) \) очікувана кількість візитів до\( y \) старту в\( x \) для\( (x, y) \in \Z^2 \). Якщо\( p \ne \frac{1}{2} \) то\( R(0, 0) \lt \infty \) і звідси\( \bs{X} \) є тимчасовим. Якщо\( p = \frac{1}{2} \) то\( R(0, 0) = \infty \) і звідси\( \bs{X} \) є рецидивуючим. У цьому випадку\( \bs{X} \) має бути нульовим повторюваним з наших загальних результатів вище, оскільки набір вершин нескінченний.

Таким чином\( \Z \), для одновимірної решітки випадкова прогулянка\( \bs{X} \) є перехідною в несиметричному випадку, а нульовий рекуррент в симетричному випадку. Повернемося до інваріантних функцій\( \bs{X} \)

Розглянемо ще раз випадкову\( \bs{X} \) прогулянку\( \Z \) з параметром\( p \in (0, 1) \). \(\bs{1} \)Постійна функція on\( \Z \) та функція,\( g\) задана\[ g(x) = \left(\frac{p}{1 - p}\right)^x, \quad x \in \Z \], є інваріантними для\( \bs{X} \). Всі інші інваріантні функції є лінійними комбінаціями цих двох функцій.

Доказ

Умова інваріантного\( h P = h \), призводить до наступного лінійного різницевого рівняння другого порядку:\[(1 - p) h(y + 1) - h(y) + (1 + p) h(y - 1), \quad y \in \Z\] Характеристичне рівняння,\( (1 - p) r^2 - r + (1 + p) = 0 \) яке має коріння\( r = 1 \) і\( r = p \big/ (1 - p) \).\( h \) Відповідні кореням розчини є\( \bs{1} \) і\( g \), відповідно. Звідси результат випливає із загальної теорії лінійних різницевих рівнянь.

Зверніть увагу, що коли\( p = \frac{1}{2} \), постійна функція\( \bs{1} \) є єдиною додатною інваріантною функцією, аж до множення на позитивні константи. Але ми знаємо, що це має бути так, оскільки ланцюг повторюється, коли\( p = \frac{1}{2} \). Більш того, ланцюг оборотна. У несиметричному випадку\( p \ne \frac{1}{2} \), коли ми маємо приклад перехідного ланцюга, який, тим не менш, має нетривіальні інваріантні функції — фактично двовимірний простір таких функцій. Крім того,\( \bs{X} \) є оборотним щодо\( g \), як показано вище, але\( \bs{X} \) розворотом щодо\( \bs{1} \) є ланцюг з перехідною матрицею,\( Q \) заданою\( Q(x, y) = P(y, x) \) for\( (x, y) \in \Z^2 \). Цей ланцюжок - це просто проста випадкова прогулянка\( Z \) з параметром\( 1 - p \). Тож несиметрична проста випадкова прогулянка є прикладом перехідного ланцюга, який є оборотним щодо однієї інваріантної міри, але не щодо іншої інваріантної міри.

Випадкові прогулянки на\( \Z^k \)

Більш загально, ми зараз розглянемо\( \Z^k \), де\( k \in \N_+ \). Для\( i \in \{1, 2, \ldots, k\} \), нехай\( \bs{u}_i \in \Z^k \) позначимо блок вектор з 1 в позиції\( i \) і 0 в іншому місці. \( k \)-Вимірна\( G \) ціла решітка має набір вершин\( Z^k \), а\( \bs{x} \in \Z^k \) сусіди -\( \bs{x} \pm \bs{u}_i \) для\( i \in \{1, 2, \ldots, k\} \). Так зокрема, кожна вершина має\( 2 k \) сусідів.

\( \mathscr{X} = (\bs{X}_1, \bs{X_2}, \ldots) \)Дозволяти ланцюжок Маркова на\( \Z^k \) з матрицею ймовірностей переходу,\( P \) заданої\[ P(\bs{x},\bs{x} + \bs{u}_i) = p_i, \; P(\bs{x}, \bs{x} - \bs{u}_i) = q_i; \quad \bs{x} \in \Z^k, \; i \in \{1, 2, \ldots, k\} \] де\( p_i \gt 0 \),\( q_i \gt 0 \) for\( i \in \{1, 2, \ldots, k\} \) і\( \sum_{i=1}^k (p_i + q_i) = 1 \). Ланцюг\( \mathscr{X} \) - це проста випадкова прогулянка по\( \Z^k \) параметрам\( \bs{p} = (p_1, p_2, \ldots, p_k) \) і\( \bs{q} = (q_1, q_2, \ldots, q_k) \).

Знову ж таки, термін простий означає, що ймовірності переходу, починаючи з,\( \bs{x} \in \Z^k \) не залежать від\( \bs{x} \), так що ланцюг є просторово однорідною, а також тимчасово однорідною. В особливому випадку, що\( p_i = q_i = \frac{1}{2 k} \) для\( i \in \{1, 2, \ldots, k\} \),\( \mathscr{X} \) це проста симетрична випадкова прогулянка далі\( Z^k \). Наступна теорема є природним узагальненням результату вище для одновимірного випадку.

Визначте функцію\( g: \Z^k \to (0, \infty) \) за допомогою\[ g(x_1, x_2, \ldots, x_k) = \prod_{i=1}^k \left(\frac{p_i}{q_i}\right)^{x_i}, \quad (x_1, x_2, \ldots, x_k) \in \Z^k \] Thend

1. \( g(\bs{x}) P(\bs{x}, \bs{y}) = g(\bs{y}) P(\bs{y}, \bs{x}) \)для всіх\( \bs{x}, \, \bs{y} \in \Z^k \)
2. \( g \)є інваріантним для\( \mathscr{X} \).
3. \( \mathscr{X} \)є оборотним по відношенню до\( g \).
4. \( \mathscr{X} \)- випадкова прогулянка\( G \) з функцією провідності,\( c \) заданою\( c(\bs{x}, \bs{y}) = g(\bs{x}) P(\bs{x}, \bs{y}) \) for\( \bs{x}, \, \bs{y} \in \Z^k \).

Доказ

1. Для\( \bs{x} = (x_1, x_2, \ldots, x_k) \in Z^k \), тільки цікаві випадки - це\( \bs{y} = \bs{x} \pm \bs{u}_i \) для\( i \in \{1, 2, \ldots, k\} \), так як у всіх інших випадках ліва і права сторони дорівнюють 0. Але\ почати {вирівнювати*} г (\ bs {x}) P (\ bs {x},\ bs {x} +\ bs {u} _i) & =\ prod_ {j\ ne i}\ ліворуч (\ frac {p_j} {q_j}\ праворуч) ^ {x_j}\ cdot\ frac {p_i^ {x_i + 1} {q_j} _i^ {x_i}} = г (\ bs {x} +\ bs {u} _i) Р (\ bs {x} +\ bs {u} _i,\ bs {x})\\ g (\ bs {x}) Р (\ bs {x} -\ bs {u} _i) & =\ prod_ {j\ ne}\ ліворуч (\ frac {p_j} {q_j}\ праворуч) ^ {x_j}\ cdot \ frac {p_i^ {x_i}} {q_i^ {x_i - 1}} = г (\ bs {x} -\ bs {u} _i) Р (\ bs {x} +\ bs {u} _i,\ bs {x})\ кінець {align*}
2. Це випливає з (а).
3. Це випливає з (а) і (b).
4. Це також випливає із загального результату вище.

Це терміни повторення і швидкоплинності, безумовно, здавалося б, що чим більше вимір\( k \), тим менше ймовірність того, що ланцюг буде повторюваним. Це взагалі так:

Класифікація простої випадкової ходьби по\( \Z^k \).

1. For\(k \in \{1, 2\} \),\( \mathscr{X} \) є нульовим рекуррентом в симетричному випадку і перехідним для всіх інших значень параметрів.
2. For\( k \in \{3, 4, \ldots\} \),\( \mathscr{X} \) є перехідним для всіх значень параметрів.

Доказ ескізу

Для деяких несиметричних випадків ми можемо використовувати результат для виміру 1. Припустимо,\( i \in \{1, 2, \ldots, k\} \) с\( p_i \ne q_i \). Якщо розглядати часи, коли\( \mathscr{X} \) змінюється\( i \) координата випадкової прогулянки, ми маємо вбудовану одновимірну випадкову прогулянку з параметром\( p = p_i \big/ (p_i + q_i) \) (ймовірність кроку в позитивному напрямку). Оскільки\( p \ne \frac{1}{2} \) ця вбудована випадкова прогулянка є перехідною і тому не зможе повернутися до 0, починаючи з 0, з позитивною ймовірністю. Але якщо ця вбудована випадкова прогулянка не повертається до 0, починаючи з 0, то батьківський випадкова\( \mathscr{X} \) прогулянка не може повернутися до\( \bs{0} \) початку\( \bs{0} \). Звідси\( \mathscr{X} \) є тимчасовим.

Для симетричного випадку загальний доказ схожий на доказ для розміру 1, але деталі значно складніші. Повернення до\( 0 \) може відбуватися лише в парний час і\[ P^{2 n}(\bs{0}, \bs{0}) \approx \frac{C_k}{n^{k/2}} \text{ as } n \to \infty \text{ where } C_k = \frac{k^{k/2}}{\pi^{k/2} 2^{k-1}}\] Таким чином, для потенційної матриці\( R \) ми маємо\( R(\bs{0}, \bs{0}) = \infty \) і ланцюг повторюється, якщо\( k \in \{1, 2\} \) while\( R(\bs{0}, \bs{0}) \lt \infty \) і ланцюг є перехідним якщо\( k \in \{3, 4, \ldots\} \).

Отже, для простої, симетричної випадкової ходьби на цілочисельній решітці\( \Z^k \) ми маємо наступний цікавий розмірний фазовий зсув: ланцюг є нульовим рекуррентом у розмірах 1 і 2 і перехідний в розмірах 3 або більше.

Повернемося до позитивних інваріантних функцій для\( \mathscr{X} \). Знову ж таки, результати узагальнюють результати для одновимірного випадку.

For\( J \subseteq \{1, 2 \ldots, k\} \), define\( g_J \) on\( \Z^k \) by\[ g_J(x_1, x_2, \ldots, x_k) = \prod_{j \in J} \left(\frac{p_j}{q_j}\right)^{x_j}, \quad (x_1, x_2, \ldots, x_k) \in \Z^k \]\( \mathscr{X}_J \) Let позначають просту випадкову прогулянку по\( \Z^k \) матриці переходу\( P_J \), що відповідає параметрам векторів\( \bs{p}^J \) і\( \bs{q^J} \), де\(p^J_j = p_j \),\(q^J_j = q_j \) for\( j \in J \), і\( p^J_j = q_j \),\(q^J_j = p_j \) для\( j \notin J \). Тоді

1. \( g_J(\bs{x}) P(\bs{x}, \bs{y}) = g_J(\bs{y}) P_J(\bs{y}, \bs{x}) \)для всіх\( \bs{x}, \, \bs{y} \in \Z^k \)
2. \( g_J \)є інваріантним для\( \mathscr{X} \).
3. \( \mathscr{X}_J \)це розворот\( \mathscr{X} \) по відношенню до\( g_J \).

Доказ

Частина (а) випливає з простої підміни. Частини (b) і (c) випливають з (а) і загальної теорії.

Зверніть увагу, що коли\( J = \emptyset \),\( g_J = \bs{1} \) і коли\( J = \{1, 2, \ldots, k\} \)\( g_J = g \), інваріантна функція введена вище. Таким чином, у абсолютно несиметричному випадку\( i \in \{1, 2, \ldots, k\} \), коли\( p_i \ne q_i \) для кожного випадкова прогулянка\( \mathscr{X} \) має\( 2^k \) позитивні інваріантні функції, які лінійно незалежні, і\( \mathscr{X} \) є оборотними щодо однієї з них.