Цепи Маркова

Покажите, что любая последовательность независимых случайных величин, принимающих значения в счётном множестве $S$, является марковской цепью. При каком условии эта цепь однородна?

Игральная кость подбрасывается многократно. Какие из следующих последовательностей являются марковскими цепями? Для тех, которые являются, укажите матрицу переходных вероятностей.

Пусть $\left\{ S_{n}: n \geq 0\right\}$ — простое случайное блуждание с $S_{0} = 0$; покажите, что $X_{n} = \left|S_{n}\right|$ определяет марковскую цепь, и найдите переходные вероятности этой цепи. Пусть $M_{n} = \max \left\{ S_{k}: 0 \leq k \leq n\right\}$; покажите, что $Y_{n} = M_{n}-S_{n}$ определяет марковскую цепь. Что произойдёт, если $S_{0} \neq 0$?

Пусть $X$ — марковская цепь, и пусть $\left\{ n_{r}: r \geq 0\right\}$ — неограниченная возрастающая последовательность натуральных чисел. Покажите, что $Y_{r} = X_{n_{r}}$ образует (возможно, неоднородную) марковскую цепь. Найдите матрицу переходных вероятностей $Y$, когда $n_{r} = 2 r$, а $X$ является:

Пусть $X$ — марковская цепь на $S$, и пусть $I: S^{n} \rightarrow \left\{ 0,1\right\}$. Покажите, что распределение $X_{n}, X_{n+1}, \ldots$ при условии $\left\{ I\left(X_{1}, \ldots , X_{n}\right) = 1\right\} \cap \left\{ X_{n} = i\right\}$ совпадает с распределением $X_{n}, X_{n+1}, \ldots$ при условии $\left\{ X_{n} = i\right\}$.

Пусть $X$ — марковская цепь на $S$, и пусть $T$ — случайная величина, принимающая значения в $\left\{ 0,1,2, \ldots \right\}$, обладающая тем свойством, что индикаторная функция $I_{\left\{ T = n\right\} }$ события $T = n$ является функцией величин $X_{1}, X_{2}, \ldots , X_{n}$. Такая случайная величина $T$ называется моментом остановки, и приведённое выше определение требует, чтобы вопрос о том, выполняется ли $T = n$, был разрешим при знании лишь прошлого и настоящего, $X_{0}, X_{1}, \ldots , X_{n}$, без какой-либо дополнительной информации о будущем.

Покажите, что

при $m \geq 0, i, j \in S$ и любых последовательностях состояний $\left(x_{k}\right)$.

Пусть $X$ — марковская цепь с пространством состояний $S$, и предположим, что $h: S \rightarrow T$ — взаимно однозначное отображение. Покажите, что $Y_{n} = h\left(X_{n}\right)$ определяет марковскую цепь на $T$. Обязано ли это быть так, если $h$ не является взаимно однозначным?

Пусть $X$ и $Y$ — марковские цепи на множестве $\mathbb {Z}$ целых чисел.

Пусть $X$ — марковская цепь. Какие из следующих последовательностей являются марковскими цепями?

Пусть $X$ — марковская цепь. Покажите, что при $1 < r < n$

Пусть $\left\{ X_{n}: n \geq 1\right\}$ — независимые одинаково распределённые целочисленные случайные величины. Пусть $S_{n} = \sum_{r = 1}^{n} X_{r}$, причём $S_{0} = 0$, $Y_{n} = X_{n}+X_{n-1}$ с $X_{0} = 0$, и $Z_{n} = \sum_{r = 0}^{n} S_{r}$. Какие из следующих последовательностей образуют марковские цепи:

Стохастическая матрица $\mathbf{P}$ называется дважды стохастической, если $\sum_{i} p_{i j} = 1$ для всех $j$. Она называется субстохастической, если $\sum_{i} p_{i j} \leq 1$ для всех $j$. Покажите, что если $\mathbf{P}$ стохастична (соответственно, дважды стохастична, субстохастична), то $\mathbf{P}^{n}$ стохастична (соответственно, дважды стохастична, субстохастична) при всех $n$.

Пусть $X$ — марковская цепь на конечном пространстве состояний $S$ с матрицей переходных вероятностей $\mathbf{P}$, и пусть $\mathcal{C} = \left\{ C_{j}: j \in J\right\}$ — разбиение $S$. Положим $Y_{n} = j$, если $X_{n} \in C_{j}$. Цепь $X$ называется $\mathcal{C}$-укрупняемой, если $Y$ является марковской цепью.

Покажите, что $X$ является $\mathcal{C}$-укрупняемой тогда и только тогда, когда при $a, b \in J$ величина $\mathbb {P}\left(X_{n+1} \in C_{b} \mid X_{n} = i\right)$ постоянна для $i \in C_{a}$.

Пусть $l_{i j}(n) = \mathbb {P}\left(X_{n} = j, X_{k} \neq i \text{ при } 1 \leq k < n \mid X_{0} = i\right)$ — вероятность того, что цепь переходит из $i$ в $j$ за $n$ шагов, ни разу не вернувшись в $i$. Положив

покажите, что $P_{i j}(s) = P_{i i}(s) L_{i j}(s)$ при $i \neq j$. Выведите отсюда, что времена первого достижения и времена последнего выхода имеют одинаковое распределение для любой марковской цепи, для которой $P_{i i}(s) = P_{j j}(s)$ при всех $i$ и $j$. Приведите пример такой цепи.

Пусть $X$ — марковская цепь, содержащая поглощающее состояние $s$, с которым сообщаются все остальные состояния $i$ в том смысле, что $p_{i s}(n) > 0$ при некотором $n = n(i)$. Покажите, что все состояния, кроме $s$, невозвратны.

Покажите, что состояние $i$ возвратно тогда и только тогда, когда среднее число посещений цепью состояния $i$ при старте из $i$ бесконечно. Иными словами, $i$ возвратно тогда и только тогда, когда $\sum_{n} p_{i i}(n) = \infty$.

Пусть $V_{j} = \left|\left\{ n \geq 1: X_{n} = j\right\} \right|$ — число посещений марковской цепью $X$ состояния $j$, и определим $\eta_{i j} = \mathbb {P}_{i}\left(V_{j} = \infty \right)$. Покажите, что:

Различные состояния $i, j$ марковской цепи называются симметричными, если

где $T_{i} = \min \left\{ n \geq 1: X_{n} = i\right\}$. Покажите, что если $X_{0} = i$ и пара $i, j$ симметрична, то ожидаемое число посещений $j$ до того, как цепь снова попадёт в $i$, равно 1. [Ср. с цитатой, следующей за теоремой (3.10.18).]

Пусть $X$ — марковская цепь, и пусть $T$ — геометрическая случайная величина с $\mathbb {P}\left(T > n\right) = s^{n}$ при $n \geq 0$, независимая от $X$. Рассматривая ожидаемое число посещений цепью $X$ заданного состояния до момента $T$, докажите теорему (6.2.3).

Пусть $X$ — эргодическая марковская цепь, начинающаяся из $a$, и предположим, что $X$ неприводима (в том смысле, что для состояний $i, j$ найдётся $m \geq 0$ такое, что $p_{i j}(m) > 0$). Пусть $a, b, c$ — различные состояния, и пусть $T(a, b, \neg c)$ — время до первого посещения $X$ состояния $b$ без промежуточного посещения $c$. То есть, если $X$ посещает $b$ раньше $c$, то $T(a, b, \neg c)$ равно этому времени, а если $X$ посещает $c$ раньше $b$, то полагаем $T(a, b, \neg c) = \infty$. Пусть

Покажите, что

где, например, $F_{a b}(s)$ — производящая функция вероятностей времени первого достижения $T_{a b}$ из $a$ в $b$ независимо от промежуточных посещений $c$. Покажите далее, что

где, например, $\mu_{a b} = \mathbb {E}_{a}\left[T_{a b}\right]$.

Пусть $X$ — марковская цепь на $\left\{ 0,1,2, \ldots \right\}$ с матрицей переходных вероятностей, заданной как $p_{0 j} = a_{j}$ при $j \geq 0$, $p_{i i} = r$ и $p_{i, i-1} = 1-r$ при $i \geq 1$. Классифицируйте состояния цепи и найдите их средние времена возврата.

Определите, является ли возвратным случайное блуждание по целым числам с переходными вероятностями $p_{i, i+2} = p, p_{i, i-1} = 1-p$ при всех $i$.

Классифицируйте состояния марковских цепей с матрицами переходных вероятностей

Частица совершает случайное блуждание по вершинам куба. На каждом шаге она остаётся на месте с вероятностью $\frac{1}{4}$ либо переходит в одну из соседних вершин, каждая с вероятностью $\frac{1}{4}$. Пусть $v$ и $w$ — две диаметрально противоположные вершины. Если блуждание начинается в $v$, найдите:

В обозначениях упражнения (6.2.4) покажите, что

Пусть $T_{A} = \min \left\{ n \geq 0: X_{n} \in A\right\}$, где $X$ — марковская цепь, а $A$ — подмножество пространства состояний $S$, и пусть $\eta_{j} = \mathbb {P}_{j}\left(T_{A} < \infty \right)$. Покажите, что

Покажите далее, что если $\mathbf{x} = \left(x_{j}: j \in S\right)$ — произвольное неотрицательное решение этих уравнений, то $x_{j} \geq \eta_{j}$ при всех $j$.

В обозначениях упражнения (6.3.6) положим $\rho_{j} = \mathbb {E}_{j}\left[T_{A}\right]$. Покажите, что

и что если $\mathbf{x} = \left(x_{j}: j \in S\right)$ — произвольное неотрицательное решение этих уравнений, то $x_{j} \geq \rho_{j}$ при всех $j$.

Пусть $X$ — неприводимая марковская цепь, и пусть $A$ — подмножество пространства состояний. Пусть $S_{r}$ и $T_{r}$ — последовательные моменты, в которые цепь входит в $A$ и посещает $A$ соответственно. Являются ли последовательности $\left\{ X_{S_{r}}: r \geq 1\right\} ,\left\{ X_{T_{r}}: r \geq 1\right\}$ марковскими цепями? Что можно сказать о моментах, в которые цепь покидает $A$?

Урна первоначально содержит $n$ зелёных шаров и $n+2$ красных шаров. Наугад выбирается шар: если он зелёный, то дополнительно удаляется красный шар, и оба они выбрасываются; если он красный, то он возвращается в урну вместе с ещё одним красным и ещё одним зелёным шаром. Это повторяется, пока в урне не останется зелёных шаров. Покажите, что вероятность того, что процесс завершится, равна $1 /(n+1)$.

Теперь поменяем правила местами: если шар зелёный, он возвращается вместе с ещё одним зелёным и ещё одним красным шаром; если он красный, он выбрасывается вместе с зелёным шаром. Покажите, что ожидаемое число итераций до тех пор, пока не останется зелёных шаров, равно $\sum_{j = 1}^{n}(2 j+1) = n(n+2)$. [Таким образом, небольшое возмущение простого симметричного случайного блуждания может быть положительно возвратным, тогда как исходное блуждание нуль-возвратно.]

Корректурный экземпляр книги читает бесконечная последовательность редакторов, проверяющих его на наличие ошибок. При каждом прочтении каждая ошибка обнаруживается с вероятностью $p$; между прочтениями типография исправляет обнаруженные ошибки, но вносит случайное число новых ошибок (ошибки могут вноситься, даже если ни одна ошибка не была обнаружена). Предполагая обычную независимость и то, что числа новых ошибок после разных прочтений одинаково распределены, найдите выражение для производящей функции вероятностей стационарного распределения числа $X_{n}$ ошибок после $n$-го цикла «редактор--типография», если оно существует. Найдите его в явном виде, когда типография вносит на каждом этапе пуассоновски распределённое число ошибок.

Проделайте заново соответствующие части упражнений (6.3.1)--(6.3.4), используя новые доступные вам методы. В частности, для упражнения (6.3.3):

Пусть $X_{n}$ — количество воды в водохранилище в полдень дня $n$. В течение суток, начинающихся в этот момент, в водохранилище поступает количество воды $Y_{n}$, а непосредственно перед полуднем каждого дня из него забирается ровно одна единица воды (если такое количество может быть найдено). Максимальная ёмкость водохранилища равна $K$, а избыточный приток воды переливается и теряется. Предположим, что $Y_{n}$ — независимые одинаково распределённые случайные величины, и что при округлении до какой-то смехотворно малой единицы объёма все числа в этом упражнении являются неотрицательными целыми. Покажите, что $\left(X_{n}\right)$ — марковская цепь, и найдите её матрицу переходных вероятностей и выражение для её стационарного распределения через производящую функцию вероятностей $G$ величин $Y_{n}$.

Найдите стационарное распределение, когда $Y$ имеет производящую функцию вероятностей $G(s) = p(1-q s)^{-1}$.

Покажите на примере, что цепи, не являющиеся неприводимыми, могут иметь много различных стационарных распределений.

Пусть $\left(x_{i}(n): i, n \geq 1\right)$ — ограниченное семейство вещественных чисел.

Случайное блуждание на графе. Частица совершает случайное блуждание по множеству вершин связного графа $G$, который для простоты мы считаем не имеющим ни петель, ни кратных рёбер. На каждом шаге она переходит к соседу своей текущей позиции, причём каждый такой сосед выбирается с равной вероятностью. Если $G$ имеет $\eta ( < \infty )$ рёбер, покажите, что стационарное распределение задаётся формулой $\pi_{v} = d_{v} /(2 \eta )$, где $d_{v}$ — степень вершины $v$.

Покажите, что случайное блуждание на бесконечном бинарном дереве невозвратно.

В каждый момент времени $n = 0,1,2, \ldots$ в камеру попадает $Y_{n}$ частиц, где $\left\{ Y_{n}: n \geq 0\right\}$ независимы и имеют распределение Пуассона с параметром $\lambda$. Времена жизни частиц независимы и имеют геометрическое распределение с параметром $p$. Пусть $X_{n}$ — число частиц в камере в момент времени $n$. Покажите, что $X$ — марковская цепь, и найдите её стационарное распределение.

Случайная последовательность выпуклых многоугольников строится следующим образом: наугад выбираются два ребра текущего многоугольника, их середины соединяются, и один из двух получившихся меньших многоугольников наугад выбирается в качестве следующего члена последовательности. Пусть $X_{n}+3$ — число рёбер $n$-го построенного таким образом многоугольника. Найдите $\mathbb {E}\left[X_{n}\right]$ через $X_{0}$ и найдите стационарное распределение марковской цепи $X$.

Пусть $s$ — состояние неприводимой марковской цепи на неотрицательных целых числах. Покажите, что цепь возвратна, если существует решение $\mathbf{y}$ уравнений $y_{i} \geq \sum_{j: j \neq s} p_{i j} y_{j}, i \neq s$, удовлетворяющее условию $y_{i} \rightarrow \infty$.

Частица совершает случайное блуждание по «галстуку-бабочке» ABCDE, изображённому ниже слева, где C — узел. Из любой вершины её следующий шаг с равной вероятностью ведёт в любую соседнюю вершину. Первоначально она находится в A. Найдите ожидаемое значение:

Частица стартует из $A$ и совершает симметричное случайное блуждание по графу, изображённому выше справа. Найдите ожидаемое число посещений $B$ до возвращения в $A$.

Колода содержит 52 карты с метками $1,2, \ldots , 52$, и первоначально они расположены в возрастающем порядке сверху вниз. На каждом шаге тасования верхняя карта перекладывается на одно из 52 возможных мест, определяемых остальными 51 картами, причём это место выбирается равномерно случайно, независимо от всех предыдущих шагов. Найдите среднее число шагов до того момента, когда карта 52 впервые окажется наверху.

Покажите, что после момента, в который карта с меткой 52 случайно вкладывается сверху, порядок карт в колоде равномерно распределён по 52! возможностям.

Колода содержит 52 карты с метками $1,2, \ldots , 52$, и первоначально они расположены в возрастающем порядке сверху вниз. На каждом шаге из колоды равномерно случайно выбирается карта и кладётся наверх, независимо от всех предыдущих шагов. Найдите среднее число шагов до того момента, когда каждая карта была выбрана хотя бы один раз.

Покажите, что после момента, в который последняя выбранная случайным образом карта кладётся наверх, порядок карт в колоде равномерно распределён по 52! возможностям.

Дик и Джим по очереди пишут упражнения для включения в учебник. Дик их пишет, а Джим проверяет. Каждое упражнение содержит ошибку с вероятностью $p$, независимо от остальных упражнений. У Джима есть два режима работы. В режиме A он проверяет каждое упражнение по мере его написания. В режиме B он проверяет каждое упражнение с вероятностью $1 / r$, где $r > 1$, независимо от всех прочих событий.

Пусть $N \geq 1$. Джим работает в режиме A до тех пор, пока не обнаружит $N$ подряд идущих упражнений без ошибок, после чего переходит в режим B. В режиме B он работает до тех пор, пока не будет найдено первое упражнение с ошибкой, после чего возвращается в режим A.

Пусть $X$ — марковская цепь, находящаяся в состоянии $i$, если Джим работает в режиме A и последние $i$ подряд идущих упражнений с момента перехода в режим A оказались без ошибок, и находящаяся в состоянии $N$, если Джим находится в режиме B.

11.39), продолжение. Частица совершает случайное блуждание по неотрицательным целым числам следующим образом. Находясь в позиции $k \geq 0$, она переходит в следующую позицию, равномерно распределённую на множестве $\left\{ 0,1, \ldots , k, k+1\right\}$. Покажите, что последовательность позиций образует апериодическую положительно возвратную марковскую цепь, и найдите её стационарное распределение.

Найдите среднее число шагов $\mu$, необходимых для первого достижения позиции 0, начиная с позиции 1.

Пусть $\left\{ X_{n}: n \geq 0\right\}$ — неприводимая марковская цепь с пространством состояний $S$ и матрицей переходных вероятностей $\mathbf{P}$ (цепь может быть как невозвратной, так и возвратной). Пусть $k \in S$, и пусть $\mathbf{x}$ — стационарная мера, такая что $x_{k} = 1$. Докажите, что $\mathbf{x} \geq \rho (k)$, где $\rho (k)$ задаётся уравнением (6.4.5). Если цепь возвратна, покажите, что $\mathbf{x} = \rho (k)$.

Случайное блуждание на множестве $\left\{ 0,1,2, \ldots , b\right\}$ имеет матрицу переходных вероятностей, заданную как $p_{00} = 1-\lambda_{0}, p_{b b} = 1-\mu_{b}, p_{i, i+1} = \lambda_{i}$ и $p_{i+1, i} = \mu_{i+1}$ для $0 \leq i < b$, где $0 < \lambda_{i}, \mu_{i} < 1$ для всех $i$, и $\lambda_{i}+\mu_{i} = 1$ для $1 \leq i < b$. Покажите, что этот процесс обратим в равновесии.

Пусть $X$ — неприводимая, положительно возвратная, апериодическая марковская цепь на пространстве состояний $S$.

Пусть $X$ — обратимая марковская цепь, и пусть $C$ — непустое подмножество пространства состояний $S$. Определим марковскую цепь $Y$ на $S$ матрицей переходных вероятностей $\mathbf{Q} = \left(q_{i j}\right)$, где

для $i \neq j$, и где $\beta$ — постоянная, удовлетворяющая $0 < \beta < 1$. Диагональные элементы $q_{i i}$ подобраны так, что $\mathbf{Q}$ является стохастической матрицей. Покажите, что $Y$ обратима в равновесии, и найдите её стационарное распределение. Опишите ситуацию в пределе при $\beta \downarrow 0$.

Может ли обратимая цепь быть периодической?

Модель «собака и блохи» из примера (6.5.5) — это марковская цепь $X$ на пространстве состояний $\left\{ 0,1, \ldots , m\right\}$ с переходными вероятностями

Покажите, что если $X_{0} = i$, то

Какие из следующих (стационарных) цепей являются обратимыми марковскими цепями?

Пусть $X_{n}, Y_{n}$ — независимые простые случайные блуждания. Пусть $Z_{n}$ — пара $(X_{n}, Y_{n})$, урезанная так, чтобы лежать в области $X_{n} \geq 0, Y_{n} \geq 0, X_{n}+Y_{n} \leq a$, где $a$ — целое число. Найдите стационарное распределение $Z_{n}$.

Покажите, что неприводимая марковская цепь с конечным пространством состояний и матрицей переходных вероятностей $\mathbf{P}$ обратима в равновесии тогда и только тогда, когда $\mathbf{P} = \mathbf{D S}$ для некоторой симметричной матрицы $\mathbf{S}$ и диагональной матрицы $\mathbf{D}$ со строго положительными диагональными элементами. Покажите далее, что для обратимости в равновесии необходимо, но не достаточно, чтобы $\mathbf{P}$ имела вещественные собственные значения.

Случайное блуждание на графе. Пусть $G$ — конечный связный граф без петель и кратных рёбер, и пусть $X$ — случайное блуждание на $G$, как в упражнении (6.4.6). Покажите, что $X$ обратимо в равновесии.

Рассмотрим случайное блуждание по строго положительным целым числам с переходными вероятностями

и $p_{11} = \frac{3}{4}, p_{12} = \frac{1}{4}$. Покажите, что это блуждание положительно возвратно, и найдите среднее время возврата состояния $i$.

Случайный жук совершает случайное блуждание по пяти вершинам, состоящим из главных точек компаса (обозначенных $n, e, s, w$) и центра (обозначенного $c$), с переходными вероятностями

Прочие переходы имеют вероятность 0. Покажите, что среднее время возврата центра равно $\mu_{c} = \frac{11}{2}$.

Пусть $X$ — неприводимая (но не обязательно апериодическая) марковская цепь на счётном пространстве состояний $S$ с матрицей переходных вероятностей $\mathbf{P}$ и инвариантным распределением $\pi$. Пусть $a \in (0,1)$, и пусть $\mathbf{L} = a \mathbf{P}+(1-a) \mathbf{I}$, где $\mathbf{I}$ — единичная матрица.

Теорема Маркова--Какутани утверждает, что для любого выпуклого компактного подмножества $C$ пространства $\mathbb {R}^{n}$ и любого линейного непрерывного отображения $T$ множества $C$ в себя $T$ имеет неподвижную точку (в том смысле, что $T(x) = x$ для некоторого $x \in C$). Используя это, докажите, что конечная стохастическая матрица обладает неотрицательным ненулевым левым собственным вектором, соответствующим собственному значению 1.

Пусть $\mathbf{T}$ — матрица размера $m \times n$, и пусть $\mathbf{v} \in \mathbb {R}^{n}$. Теорема Фаркаша утверждает, что выполняется ровно одно из следующих условий:

(i) существует $\mathbf{x} \in \mathbb {R}^{m}$, такое что $\mathbf{x} \geq \mathbf{0}$ и $\mathbf{x} \mathbf{T} = \mathbf{v}$,

(ii) существует $\mathbf{y} \in \mathbb {R}^{n}$, такое что $\mathbf{y v}^{\prime } < 0$ и $\mathbf{T y}^{\prime } \geq \mathbf{0}$.

Используя это, докажите, что конечная стохастическая матрица обладает неотрицательным ненулевым левым собственным вектором, соответствующим собственному значению 1.

Предположим, что вы делаете ставки на скачки с $m$ возможными исходами. Имеется $n$ букмекеров, и единичная ставка у $i$ го букмекера приносит $t_{i j}$, если наступает $j$ й исход скачек. Вектор $\mathbf{x} = \left(x_{1}, x_{2}, \ldots , x_{n}\right)$, где $x_{r} \in (-\infty , \infty )$ — ваша ставка у $r$ го букмекера, называется схемой ставок. Покажите, что выполняется ровно одно из (a) и (b):

(a) существует функция вероятностей $\mathbf{p} = \left(p_{1}, p_{2}, \ldots , p_{m}\right)$, такая что $\sum_{j = 1}^{m} t_{i j} p_{j} = 0$ при всех значениях $i$,

(b) существует схема ставок $\mathbf{x}$, при которой вы наверняка выигрываете, то есть $\sum_{i = 1}^{n} x_{i} t_{i j} > 0$ при всех $j$.

Пусть $X$ — марковская цепь с пространством состояний $S = \left\{ 1,2,3\right\}$ и матрицей переходных вероятностей

где $0 < p < 1$. Докажите, что

где $a_{1 n}+\omega a_{2 n}+\omega^{2} a_{3 n} = (1-p+p \omega )^{n}$, а $\omega$ — комплексный кубический корень из 1.

Пусть $\mathbf{P}$ — матрица переходных вероятностей марковской цепи с конечным пространством состояний. Пусть $\mathbf{I}$ — единичная матрица, $\mathbf{U}$ — матрица размера $\left|S\right| \times \left|S\right|$, все элементы которой равны единице, а $\mathbf{1}$ — вектор-строка длины $\left|S\right|$, все элементы которой равны единице. Пусть $\mathbf{\pi }$ — неотрицательный вектор с $\sum_{i} \pi_{i} = 1$. Покажите, что $\mathbf{\pi } \mathbf{P} = \mathbf{\pi }$ тогда и только тогда, когда $\mathbf{\pi }(\mathbf{I}-\mathbf{P}+\mathbf{U}) = \mathbf{1}$. Выведите отсюда, что если $\mathbf{P}$ неприводима, то $\mathbf{\pi } = \mathbf{1}(\mathbf{I}-\mathbf{P}+\mathbf{U})^{-1}$.

Шахматная фигура совершает случайное блуждание по шахматной доске; на каждом шаге она с равной вероятностью делает любой из доступных ходов. Чему равно среднее время возврата угловой клетки, если фигура — это:

Ладья и слон совершают независимые симметричные случайные блуждания с синхронными шагами по доске $4 \times 4$ (16 клеток). Если они начинают вместе в угловой клетке, покажите, что ожидаемое число шагов до их повторной встречи в той же угловой клетке равно $448 / 3$.

Найдите $n$-шаговые переходные вероятности $p_{i j}(n)$ для цепи $X$ с матрицей переходных вероятностей

Страницы всемирной сети образуют ориентированный граф $W$ с $n$ вершинами (представляющими страницы), соединёнными ориентированными рёбрами (представляющими ссылки). Наличие ссылки из $i$ в $j$ обозначается $i \rightarrow j$, и граф задаётся своей матрицей смежности $L = \left(l_{i j}\right)$, где $l_{i j} = 1$, если $i \rightarrow j$, и $l_{i j} = 0$ в противном случае. Исходящая степень $d_{i}$ (соответственно, входящая степень $c_{i}$) вершины $i$ — это число ссылок, исходящих из $i$ (соответственно, ведущих в $i$). Говорят, что вершина $i$ является тупиковой, если $d_{i} = 0$.