Банк задач по математике

Задача 9.1

Доказать, что для любой стохастической матрицы $P$ существует вероятностное пространство и последовательность случайных величин на нем, образующих цепь Маркова с матрицей вероятностей перехода за один шаг $P$ .

?

Задача 9.2

Всякая ли стохастическая матрица может быть матрицей вероятностей перехода за два шага некоторой цепи Маркова?

?

Задача 9.3

Известно, что цепь Маркова полностью определяется начальным распределением и матрицей вероятностей перехода за один шаг. Определяется ли цепь Маркова начальным распределением и матрицей вероятностей перехода за два шага?

?

Задача 9.4

Доказать, что стохастическая матрица второго порядка является матрицей вероятностей перехода за два шага некоторой цепи Маркова тогда и только тогда, когда сумма ее диагональных элементов больше или равна единице.

?

Задача 9.5

Определить, при каких значениях с и $d$ цепь Маркова определяется однозначно начальным распределением и матрицей вероятностей перехода за два шага:

P^{\prime 2} =\left[\begin{smallmatrix} c & 1-c \\ 1-d & d \end{smallmatrix}\right] .

?

Задача 9.6

(а)(б)(в)

Доказать, что для цепи Маркова $\xi_{0}, \xi_{1}, \ldots$ при любых $0 \leqslant k \leqslant n-1$ :

?

(а)

$\mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{n-1} = i_{n-1}, \ldots , \xi_{k} = i_{k} \right) = \mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{n-1} = i_{n-1} \right)$ ;

(б)

$\mathbb {P}\left( \xi_{n} = i_{n}, \ldots , \xi_{k+1} = i_{k+1} \mid \xi_{k} = i_{k}, \ldots , \xi_{0} = i_{0} \right) =$

= \mathbb {P}\left( \xi _{n} = i_{n}, \ldots , \xi _{k+1} = i_{k+1} \mid \xi _{k} = i_{k} \right) ;

(в)

$\mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{k} = i_{k}, \ldots , \xi_{0} = i_{0} \right) = \mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{k} = i_{k} \right)$ .

Задача 9.7

Пусть $A$ — событие, зависящее только от состояний цепи Маркова на первых $n-1$ шагах, а $B$ — событие, зависящее от состояний на $(n+1)-м, \ldots ,(n+m)-м$ шагах. Доказать, что при фиксированном состоянии на $n$ -м шаге события $A$ и $B$ независимы.

?

Задача 9.8

Пусть $\xi_{0}, \xi_{1}, \ldots$ — цепь Маркова. Доказать, что для любых $0 \leqslant n_{i} \leqslant n$

\mathbb {P}\left( \xi _{n+1} = i_{n+1} \mid \xi _{n_{1}} = i_{n_{1}}, \ldots , \xi _{n_{k}} = i_{n_{k}} \right) = \mathbb {P}\left( \xi _{n+1} = i_{n+1} \mid \xi _{n_{s}} = i_{n_{s}} \right),

где $n_{s} = \max \left\{ n_{i}\right\}$ .

?

Задача 9.9

Пусть случайная величина $\tau$ не зависит от однородной цепи Маркова $\xi_{0}, \xi_{1}, \ldots$ и принимает целые неотрицательные значения. Доказать, что для любого $n \geqslant 1$ и любых $i_{0}, \ldots , i_{n+1}$

\mathbb {P}\left( \xi _{\tau +n+1} = i_{n+1} \mid \xi _{\tau +n} = i_{n}, \ldots , \xi _{\tau } = i_{0} \right) = \mathbb {P}\left( \xi _{\tau +n+1} = i_{n+1} \mid \xi _{\tau +n} = i_{n} \right) ;

Верны ли указанные равенства, если цепь Маркова $\xi_{0}, \xi_{1}, \ldots$ неоднородна?

?

Задача 9.10

Пусть $\tau_{1}, \tau_{2}, \ldots$ — последовательность независимых положительных целочисленных случайных величин, не зависящих от цепи Маркова $\xi_{0}, \xi_{1}, \ldots$ Доказать, что

\begin{aligned} \mathbb {P}\left( \xi _{\tau _{1}+\ldots +\tau _{n}} = i_{n} \mid \xi _{\tau _{1}+\ldots +\tau _{n-1}} = i_{n-1}, \ldots , \xi _{\tau _{1}} = i_{1} \right) & = \\ & = \mathbb {P}\left( \xi _{\tau _{1}+\ldots +\tau _{n}} = i_{n} \mid \xi _{\tau _{1}+\ldots +\tau _{n-1}} = i_{n-1} \right) . \end{aligned}

?

Задача 9.11

Цепь Маркова имеет матрицу вероятностей перехода за один шаг

P^{(1)} =\left[\begin{smallmatrix} 1-a & a \\ b & 1-b \end{smallmatrix}\right] .

Найти матрицу вероятностей перехода за $n$ шагов и предел при $n \rightarrow \infty$ .

?

Задача 9.12

Пусть в матрице вероятностей перехода за один шаг цепи Маркова с тремя состояниями

P_{i j} = \begin{cases} P_{1, i-j+1}, & i \geqslant j, \\ P_{1, j-i+1}, & j > i . \end{cases}

Найти матрицу вероятностей перехода за $n$ шагов и предел при $n \rightarrow \infty$ .

?

Задача 9.13

В матрице вероятностей перехода $P$ за один шаг

P_{i j} = \begin{cases} P_{1, j-i+1}, & j \geqslant i, \\ P_{i-j+1,1}, & j < i . \end{cases}

Доказать, что аналогичные соотношения выполняются для вероятностей перехода за $m$ шагов.

?

Задача 9.14

Пусть $P_{i j}^{(n)}$ — вероятность перехода за $n$ шагов из $i$ -го состояния в $j$ -е некоторой цепи Маркова,

\alpha _{j}(n) = \min _{i} P_{i j}^{(n)}, \quad \beta _{j}(n) = \max _{i} P_{i j}^{(n)} .

Доказать, что

\alpha _{j}(1) \leqslant \alpha _{j}(2) \leqslant \ldots \leqslant \alpha _{j}(n) \leqslant \ldots \leqslant \beta _{j}(n) \leqslant \ldots \leqslant \beta _{j}(2) \leqslant \beta _{j} . \tag {1}

?

Задача 9.15

Пусть последовательность случайных величин $\xi_{0}, \xi_{i}, \ldots$ образует цепь Маркова. Доказать, что любая подпоследовательность последовательности $\xi_{0}, \xi_{1}, \ldots$ также образует цепь Маркова.

?

Задача 9.16

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность независимых одинаково распределенных целочисленных случайных величин. Доказать, что она образует цепь Маркова. Найти матрицу вероятностей перехода за $n$ шагов.

?

Задача 9.17

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность случайных величин, образующих однородную цепь Маркова. Доказать, что для того, чтобы случайные величины $\xi_{0}, \xi_{1}, \ldots$ были независимы, необходимо и достаточно, чтобы все строки матрицы вероятностей перехода за один шаг были одинаковыми.

?

Задача 9.18

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность попарно независимых (не обязательно независимых в совокупности) случайных величин. Образуют ли $\xi_{0}, \xi_{1}, \ldots$ цепь Маркова?

?

Задача 9.19

(а)(б)(в)

Точки $A_{1}, \ldots , A_{n}$ представляют собой вершины правильного $n$ -угольника. Некоторая частица совершает случайное блуждание по точкам $A_{1}, \ldots , A_{n}$ . Определить, является ли последовательность положений частицы цепью Маркова, если

?

(а)

частица совершает детерминированное движение по часовой стрелке;

(б)

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

(в)

из любой точки $A_{i}, i \neq 1$ , частица с вероятностью $p$ сдвигается по часовой стрелке, а с вероятностью $q = 1-p$ — против часовой стрелки в соседнюю точку. Попадая в точку $A_{1}$ , частица возвращается в ту точку, из которой она пришла в $A_{1}$ .

Задача 9.20

(а)(б)(в)

Частица совершает случайное блуждание в плоскости по целочисленным точкам $(i, j)$ , таким, что $0 \leqslant i, j \leqslant n$ . Из любой внутренней точки указанного квадрата частица с равными вероятностями, независимо от ее предыдущего движения, переходит в одну из соседних (по вертикали или горизонтали) точек. При выходе на границу квадрата частица далее:

?

(а)

движется по границе квадрата детерминированно по часовой стрелке;

(б)

возвращается в ту точку, из которой она вышла на границу;

(в)

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

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

Задача 9.21

(а)(б)(в)

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

?

(а)

(б)

(в)

Задача 9.22

В начальный момент времени в урне $n_{0}$ белых и $m_{0}$ черных шаров. Через каждую единицу времени из урны по схеме выбора без возвращения извлекается один шар. Пусть $n_{k}$ — число белых, а $m_{k}$ — число черных шаров в урне в момент времени $k$ . Какие из указанных ниже последовательностей образуют цепь Маркова, а какие нет:

?

(а)

$n_{k}$ ,

(б)

$n_{k}-m_{k}$ ,

(в)

$n_{k}+m_{k}$ ,

(г)

пара ( $n_{k}, m_{k}$ ),

(д)

$n_{k}-m_{k} + 1 /\left(n_{k}+m_{k}+2\right) ?$

Задача 9.23

Пусть случайные величины $\xi_{0}, \ldots , \xi_{n}$ образуют цепь Маркова. Доказать, что случайные величины $\eta_{0}, \ldots , \eta_{n}$ , где $\eta_{i} = \xi_{n-i}$ , также образуют цепь Маркова. Образуют ли цепь Маркова случайные величины $\zeta_{0}, \ldots , \zeta_{n}$ , где $\zeta_{0}, \ldots , \zeta_{n}$ — произвольная перестановка $\xi_{0}, \ldots , \xi_{n}$ ?

?

Задача 9.24

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность независимых случайных величин. Образует ли цепь Маркова последовательность $\xi_{0}+\xi_{1}$ , $\xi_{1}+\xi_{2}, \xi_{2}+\xi_{3}, \ldots ?$

?

Задача 9.25

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность случайных величин, образующих цепь Маркова. Будет ли цепью Маркова последовательность $\xi_{0}+\xi_{1}, \xi_{2}+\xi_{3}, \xi_{4}+\xi_{5}, \ldots$ ?

?

Задача 9.26

Дана цепь Маркова с конечным числом состояний. Пусть $\xi_{i}$ — состояние цепи на $i$ -м шаге. Будет ли цепью Маркова последовательность $\eta_{0}, \eta_{1}, \ldots$ , где

\eta _{i} = \begin{cases} 1, & \text{ если } \xi _{i} = x_{1}, \\ 0, & \text{ если } \xi _{i} \neq x_{1} . \end{cases}

?

Задача 9.27

(а)(б)(в)

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность независимых одинаково распределенных случайных величин, принимающих значения -1 и +1 с вероятностями $p$ и $q = 1-p$ соответственно. Положим:

?

(а)

$\eta_{n} = \xi_{n} \xi_{n+1}$ ;

(б)

$\eta_{n} = \max_{0 \leqslant i \leqslant n} \xi_{i}$ ;

(в)

$\eta_{n} = \prod_{i = 0}^{n} \xi_{i}$ .

Будет ли последовательность $\eta_{0}, \eta_{1}, \ldots$ цепью Маркова?

Задача 9.28

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность независимых целочисленных случайных величин, причем

\mathbb {P}\left(\xi _{n} = k\right) = p_{k}, \quad k = 0, \pm 1, \pm 2, \ldots

Положим $\eta_{n} = \xi_{0}+\ldots +\xi_{n}$ . Доказать, что последовательность $\eta_{0}, \eta_{1}, \ldots$ образует цепь Маркова. Найти соответствующую матрицу вероятностей перехода за один шаг.

?

Задача 9.29

Пусть $\xi_{0}, \xi_{1}, \ldots$ и $\eta_{0}, \eta_{1}, \ldots$ — две цепи Маркова. Будет ли цепью Маркова последовательность $\xi_{0}+\eta_{0}, \xi_{1}+\eta_{1}, \ldots$ ?

?

Задача 9.30

Пусть $\left(\xi_{1}^{(i)}, \ldots , \xi_{n}^{(i)}\right), \quad i \geqslant 1$ ,- последовательность независимых одинаково распределенных случайных векторов, $\xi_{0}$ — случайная величина, не зависящая от $\left\{ \left(\xi_{1}^{(i)}, \ldots , \xi_{n}^{(i)}\right)\right\} , i = 1,2, \ldots$ . Пусть $\xi_{0}$ и $\xi_{j}^{(i)}$ принимают значения $1, \ldots , n$ . Построим последовательность случайных величин $\eta_{0}, \eta_{1}, \ldots$ следующим образом:

\eta _{0} = \xi _{0}, \quad \eta _{i} = \xi _{\eta _{i-1}}^{(i)}, \quad i \geqslant 1.

Доказать, что последовательность $\eta_{0}, \eta_{1}, \ldots$ образует цепь Маркова.

?

Задача 9.31

Для цепи Маркова, определенной в предыдущей задаче, найти число состояний, матрицу вероятностей перехода за один шаг и вектор начальных вероятностей, если

\mathbb {P}\left(\xi _{i}^{(1)} = j\right) = p_{i j}, \quad i = 0,1, \ldots , n ; \quad j = 1,2, \ldots , n .

?

Задача 9.32

Доказать, что любая цепь Маркова с конечным числом состояний может быть представлена как последовательность случайных величин $\eta_{0}, \eta_{1}, \ldots$ , определенных в задаче 9.30.

?

Задача 9.33

Пусть $\xi_{0}, \xi_{1}, \ldots$ — независимые случайные величины с дискретным распределением, $f_{0}, f_{1}, \ldots$ — некоторые функции. Доказать, что последовательность случайных величин $\eta_{1}, \eta_{2}, \ldots$ , где $\eta_{k+1} = f_{k}\left(\eta_{k}, \xi_{k+1}\right)$ , образует цепь Маркова.

?

Задача 9.34

Пусть $\xi_{0}, \xi_{1}, \ldots$ — последовательность случайных величин, образующих цепь Маркова, $f(x)$ — некоторая функция. Будет ли последовательность $f\left(\xi_{0}\right), f\left(\xi_{1}\right), \ldots$ цепью Маркова?

?

Задача 9.35

Пусть $\xi_{0}, \xi_{1}, \ldots$ — цепь Маркова со счетным множеством состояний $\left\{ 1,2, \ldots \right\}$ и матрицей вероятностей перехода за один шаг $P$ , причем состояния $1,2, \ldots , N$ возвратны. Положим

\begin{gathered} v_{0} = \min \left(i: \xi _{i} \leqslant N\right), \quad v_{n} = \min \left(i > v_{n-1}: \xi _{i} \leqslant N\right), \quad n \geqslant 1, \\ \eta _{j} = \xi _{v_{j}} . \end{gathered}

Доказать, что последовательность, $\eta_{0}, \eta_{1}, \ldots$ образует цепь Маркова. Найти матрицу вероятностей перехода за один шаг.

?

Задача 9.36

Для всякой ли цепи Маркова $\xi_{0}, \xi_{1}, \ldots$ со счетным числом состояний $\left\{ 1,2, \ldots \right\}$ можно выбрать последовательность независимых между собой и не зависящих от $\xi_{0}, \xi_{1}, \ldots$ случайных величин $\zeta_{0}, \zeta_{1}, \ldots$ со значениями в множестве $\left\{ 1,2, \ldots , N\right\}$ , таких, что последовательность $\eta_{0}, \eta_{1}, \ldots$ , где

\eta _{i} = I\left(\xi _{i} \leqslant N\right) \xi _{i}+I\left(\xi _{i} > N\right) \zeta _{i},

является цепью Маркова?

?

Задача 9.37

Пусть $\xi_{0}, \xi_{1}, \ldots$ — цифровая последовательность, в которой цифры появляются случайно, независимо друг от друга и равновероятно. Имеется счетчик, который в момент $n$ показывает, сколько различных цифр встретилось среди первых $n$ цифр последовательности $\xi_{0}, \xi_{1}, \ldots$ Доказать, что показания счетчика образуют цепь Маркова. Найти матрицу вероятностей перехода за один шаг. Указать существенные и несущественные состояния.

?

Задача 9.38

Частица случайным образом блуждает на прямой по целочисленным точкам $0,1, \ldots , n$ . Из любой внутренней точки частица передвигается с вероятностью $p$ на один шаг вправо или, с вероятностью $q = 1-p$ , на один шаг влево. Попадая в точки 0 и $n$ частица остается в них навсегда (поглощающие экраны). Найти матрицу вероятностей перехода за один шаг. Указать существенные и несущественные состояния.

?

Задача 9.39

Частица случайным образом блуждает на прямой по целочисленным точкам $0,1, \ldots , n$ . Из любой внутренней точки частица передвигается с вероятностью $p$ на один шаг вправо или, с вероятностью $q = 1-p$ , на один шаг влево. Попадая в точки 0 и $n$ частица в следующий момент времени с вероятностью 1 переходит соответственно в точки 1 или $n-1$ (отражающие экраны). Найти матрицу вероятностей перехода за один шаг. Указать существенные и несущественные состояния.

?

Задача 9.40

Указать существенные и несущественные состояния цепи Маркова с матрицей вероятностей перехода за один шаг

P =\left[\begin{smallmatrix} 1 / 4 & 1 / 4 & 0 & 0 & 1 / 2 \\ 1 / 3 & 0 & 1 / 3 & 1 / 3 & 0 \\ 1 / 2 & 0 & 0 & 0 & 1 / 2 \\ 0 & 0 & 0 & 1 / 2 & 1 / 2 \\ 0 & 0 & 0 & 1 & 0 \end{smallmatrix}\right] .

?

Задача 9.41

Могут ли все состояния цепи Маркова с конечным числом состояний быть несущественными?

?

Задача 9.42

Могут ли все состояния цепи Маркова со счетным числом состояний быть несущественными?

?

Задача 9.43

Матрица вероятностей перехода за один шаг цепи Маркова имеет вид

P =\left[\begin{smallmatrix} 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 1 & 0 & 0 & 0 \end{smallmatrix}\right] .

Указать все пары сообщающихся состояний.

?

Задача 9.44

(а)(б)

Цепь Маркова имеет $r$ состояний. Доказать, что:

?

(а)

если $j$ -е состояние достижимо из $i$ -го ( $i \neq j$ ), то оно может быть достигнуто меньше чем за $r$ шагов;

(б)

если вероятность возвращения в состояние $i$ положительна, то возвращение может произойти за $r$ или менее шагов.

Задача 9.45

(а)(б)(в)

Будет ли цепь Маркова с матрицей вероятностей перехода за один шаг $P$ периодической, если

?

(а)

$P = \left(\begin{array}{llll}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{array}\right)$ ,

(б)

$P = \left(\begin{array}{cccccc}0 & 1 / 2 & 0 & 1 / 2 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 / 2 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0\end{array}\right)$ ,

(в)

$P = \left(\begin{array}{cccc}1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 0 & 1 / 2\end{array}\right)$ .

Для периодических цепей указать период.

Задача 9.46

(а)(б)

?

(а)

Доказать, что неразложимая цепь, у матрицы переходных вероятностей которой хотя бы один диагональный элемент $P_{j j}$ положителен, не может быть периодической.

(б)

Может ли неразложимая цепь, у которой все диагональные элементы равны нулю, быть непериодической?

Задача 9.47

Доказать, что конечная неразложимая цепь Маркова является непериодической тогда и только тогда, когда существует $n$ такое, что $P_{i j}^{(n)} > 0$ для всех $i$ и $j$ .

?

Задача 9.48

Указать возвратные и невозвратные состояния цепи Маркова с матрицей вероятностей перехода за один шаг

P =\left[\begin{smallmatrix} 0 & 1 / 2 & 1 / 2 & 0 & 0 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 0 & 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 0 & 0 & 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 0 & 0 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{smallmatrix}\right] .

?

Задача 9.49

(а)(б)(в)(г)

Доказать, что все состояния цепи Маркова с матрицей переходных вероятностей $P$ возвратны, если

?

(а)

$P = \left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$ ;

(б)

$P = \left(\begin{array}{cccc}1 / 2 & 0 & 1 / 2 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2 \\ 1 / 2 & 0 & 1 / 2 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2\end{array}\right)$ ;

(в)

$P = \left(\begin{array}{cccc}1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 \\ 0 & 0 & 1 / 2 & 1 / 2\end{array}\right)$ ;

(г)

$P = \left(\begin{array}{cccccc}1 / n & 0 & 1 / n & 0 & \ldots & \ldots \\ 0 & 1 / n & 0 & 1 / n & \ldots & \ldots \\ 1 / n & 0 & 1 / n & 0 & \ldots & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots & .\end{array}\right)$ .

Задача 9.50

Доказать, что если $j$ -е состояние невозвратно, то для всех $i \sum_{n = 1}^{\infty } P_{i j}^{(n)} < \infty$ .

?

Задача 9.51

Доказать, что любая цепь Маркова с конечным числом состояний имеет по крайней мере одно возвратное состояние.

?

Задача 9.52

Могут ли все состояния цепи Маркова со счетным числом состояний быть невозвратными?

?

Задача 9.53

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

?

Задача 9.54

Имеется цепь Маркова со счетным числом состояний и матрицей вероятностей перехода за один шаг

P =\left[\begin{smallmatrix} p_{1} & 1-p_{1} & 0 & 0 & 0 & \ldots & \ldots \\ p_{2} & 0 & 1-p_{2} & 0 & 0 & \ldots & \ldots \\ p_{3} & 0 & 0 & 1-p_{3} & 0 & \ldots & \ldots \\ & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \end{smallmatrix}\right]

Доказать, что если ряд $\sum_{i = 1}^{\infty } p_{i}$ сходится, то все состояния этой цепи возвратны, в противном случае — невозвратны.

?

Задача 9.55

(а)(б)

Пусть все состояния цепей Маркова с матрицами вероятностей перехода за один шаг $A$ и $B$ возвратны. Доказать, что возвратны все состояния цепи Маркова с матрицей вероятностей перехода:

?

(а)

$\left(\begin{array}{ll}A & 0 \\ 0 & B\end{array}\right)$ ;

(б)

$\left(\begin{array}{cc}0 & A \\ B & 0\end{array}\right)$ .

Задача 9.56

Доказать, что для любого состояния $i$ цепи Маркова вероятность $Q_{i i}$ возвращения в него бесконечное число раз равна 0 или 1, причем в первом случае состояние невозвратно, а во втором возвратно.

?

Задача 9.57

Пусть цепь Маркова имеет $m < \infty$ состояний и пусть $k$ -е состояние возвратно. Доказать, что существует положительное число $q < 1$ , такое, что при $n \geqslant m$ вероятность того, что время возвращения в $k$ -е состояние превысит $n$ , меньше, чем $q^{n}$ .

?

Задача 9.58

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

u_{i} = \sum _{j = 0}^{\infty } u_{j} P_{i j}, \quad i = 1,2, \ldots

имела ограниченное решение, такое, что $u_{i} \not\equiv$ const, $i = 0,1, \ldots$

?

Задача 9.59

Доказать, что для того, чтобы неразложимая цепь со счетным числом состояний была возвратной, достаточно существования такой последовательности $u_{0}, u_{1}, \ldots$ , что $u_{i} \rightarrow \infty$ при $i \rightarrow \infty$ и для всех $i \neq 0$

u_{i} \geqslant \sum _{j = 0}^{\infty } u_{j} P_{i j}

?

Задача 9.60

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

u_{j} = \sum _{i = 0}^{\infty } u_{i} P_{i j}, \quad j = 0,1, \ldots

имела не равное тождественно нулю решение, для которого

\sum _{i = 0}^{\infty }\left|u_{i}\right| < \infty .

?

Задача 9.61

(а)(б)(в)(г)

Имеется цепь Маркова со счетным числом состояний и переходными вероятностями $P_{00} = r_{0}, P_{01} = p_{0} > 0$

P_{i j} = \begin{cases} p_{i} > 0, & j = i+1 \\ r_{i} \geqslant 0, & j = i \\ q_{i} > 0, & j = i-1 \\ 0, & \text{ в остальных случаях. } \end{cases}

Пусть

\rho _{0} = 1, \quad \rho _{m} = \frac{q_{1} \cdots q_{m}}{p_{1} \cdots p_{m}}

Доказать справедливость следующих утверждений:

?

(а)

цепь возвратна тогда и только тогда, когда

\sum _{m = 0}^{\infty } \rho _{m} = \infty ;

(б)

цепь невозвратна тогда и только тогда, когда

\sum _{m = 0}^{\infty } \rho _{m} < \infty ;

(в)

цепь положительна тогда и только тогда, когда

\sum _{m = 0}^{\infty } \rho _{m} = \infty , \quad \sum _{m = 0}^{\infty }\left[p_{m} \rho _{m}\right]^{-1} < \infty ;

(г)

цепь нулевая тогда и только тогда, когда

\sum _{m = 0}^{\infty } \rho _{m} = \infty , \quad \sum _{m = 0}^{\infty }\left[p_{m} \rho _{m}\right]^{-1} = \infty .

Задача 9.62

Пусть $\xi_{0}, \xi_{1}, \ldots$ — цепь Маркова,

\xi _{k+1} = \max \left\{ 0, \xi _{k}-1\right\} +\eta _{k+1}, \quad k \geqslant 0,

где $\eta_{1}, \eta_{2}, \ldots$ — последовательность независимых одинаково распределенных случайных величин с $\mathbb {P}\left(\eta_{k} = j\right) = p_{j}, j = 0,1, \ldots$ Найти матрицу вероятностей перехода за один шаг и доказать, что если $p_{0} > 0, p_{0}+p_{1} < 1$ , то цепь возвратна тогда и только тогда, когда

\sum _{k} k p_{k} \leqslant 1

?

Задача 9.63

Доказать, что если цепь Маркова имеет по крайней мере одно несущественное состояние, то она не является эргодической.

?

Задача 9.64

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

?

Задача 9.65

Доказать, что для конечной цепи Маркова всегда существует стационарное распределение.

?

Задача 9.66

(а)(б)

Матрица вероятностей перехода за один шаг цепи Маркова имеет вид:

?

(а)

$\left(\begin{array}{cccc}1 / 3 & 1 / 3 & 1 / 3 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 4 & 1 / 4 & 0 & 1 / 2 \\ 0 & 1 / 2 & 0 & 1 / 2\end{array}\right)$ ;

(б)

$\left(\begin{array}{ccccc}0 & 1 / 2 & 0 & 0 & 1 / 2 \\ 0 & 0 & 1 & 0 & 0 \\ 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 \\ 0 & 1 / 2 & 0 & 0 & 1 / 2 \\ 0 & 1 / 2 & 1 / 2 & 0 & 0\end{array}\right)$ .

Найти стационарное распределение.

Задача 9.67

Эргодичны ли цепи Маркова со следующими матрицами вероятностей перехода за один шаг:

?

(а)

$\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$ ,

(б)

$\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$ ,

(в)

$\left(\begin{array}{ll}1 & 0 \\ 1 & 0\end{array}\right)$ ,

(г)

$\left(\begin{array}{cc}1 / 2 & 1 / 2 \\ 1 & 0\end{array}\right)$ ,

(д)

$\left(\begin{array}{cc}1 / 2 & 1 / 2 \\ 0 & 1\end{array}\right)$ ,

(е)

$\left(\begin{array}{ccc}1 / 2 & 1 / 2 & 0 \\ 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 1 / 2\end{array}\right)$ ,

(ж)

$\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4\end{array}\right)$ .

Задача 9.68

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

?

Задача 9.69

(а)(б)(в)

Пусть цепь Маркова имеет два состояния. Доказать, что имеет место один из следующих трех случаев:

?

(а)

цепь эргодична;

(б)

состояния не сообщаются;

(в)

матрица вероятностей перехода за один шаг имеет вил $\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$ .

Задача 9.70

Эргодичная цепь Маркова с двумя состояниями имеет предельные вероятности $p$ и $q = 1-p$ . Найти матрицу вероятностей перехода за один шаг.

?

Задача 9.71

Доказать, что если все существенные состояния однородной цепи Маркова с конечным числом состояний образуют один непериодический класс, то существуют не зависящие от $i$ пределы

\lim _{n \rightarrow \infty } P_{i j}^{(n)} = \pi _{j}

?

Задача 9.72

Цепь Маркова имеет следующую матрицу вероятностей перехода за один шаг:

\mathbf{P} =\left[\begin{smallmatrix} p_{0} & p_{1} & p_{2} & \ldots & p_{m-1} \\ p_{m-1} & p_{0} & p_{1} & \ldots & p_{m-2} \\ \hdashline \cdot & 0 & . & . & . \\ p_{1} & p_{2} & p_{3} & \ldots & p_{0} \end{smallmatrix}\right],

где $0 < p_{i} < 1, \sum_{i = 0}^{m-1} p_{i} = 1$ . Доказать, что

\lim _{n \rightarrow \infty } \mathbb {P}\left(\xi _{n} = x_{i}\right) = 1 / m, \quad i = 1,2, \ldots , m

?

Задача 9.73

Пусть $\xi_{0}, \xi_{1}, \ldots$ и $\eta_{0}, \eta_{1}, \ldots$ — две цепи Маркова с конечным числом состояний, одинаковой матрицей вероятностей перехода за один шаг и начальными распределениями ( $p_{1}, \ldots , p_{m}$ ) и ( $q_{1}, \ldots , q_{m}$ ) соответственно. Доказать, что если

\min _{i, j} P_{i j} \geqslant \varepsilon > 0

то

\sum _{i = 1}^{m}\left|p_{i}^{(n)}-q_{i}^{(n)}\right| \leqslant 2(1-m \varepsilon )^{n}

где $p_{i}^{(n)} = \mathbb {P}\left(\xi_{n} = i\right), \quad q_{i}^{(n)} = \mathbb {P}\left(\eta_{n} = i\right)$ .

?

Задача 9.74

Пусть конечная цепь Маркова является эргодической и $\pi_{j} = \lim_{n \rightarrow \infty } P_{i j}^{(n)}$ . Доказать, что существуют $0 < \rho < 1$ и $C$ , такие, что

\left|P_{i j}^{(n)}-\pi _{j}\right| < C \rho ^{n}

для любых $i, j$ и $n$ .

?

Задача 9.75

Доказать, что если матрица вероятностей перехода цепи Маркова имеет два собственных значения, по модулю равных единице, то цепь неэргодична.

?

Задача 9.76

Рассмотрим цепь Маркова из задачи 9.62. Доказать, что при $p_{0} > 0, p_{0}+p_{1} < 1, \sum k p_{k} < 1$ она является эргодической. Найти производящую функцию стационарного распределения.

?

Задача 9.77

Найти стационарное распределение цепи Маркова из задачи 9.54 в случае сходимости ряда $\sum_{i = 1}^{\infty } p_{i}$ .

?

Задача 9.78

Рассмотрим цепь Маркова со счетным числом состояний и матрицей вероятностей перехода за один шаг

\left[\begin{smallmatrix} p_{0} & p_{1} & p_{2} & \ldots \\ 1 & 0 & 0 & \ldots \\ 0 & 1 & 0 & \ldots \\ 0 & 0 & 1 & \ldots \\ . & . & . & \ldots \end{smallmatrix}\right] .

Доказать, что при $p_{i} > 0, i = 0,1, \ldots , \sum i p_{i} < \infty$ цепь является эргодической. Найти производящую функцию стационарного распределения.

?

Задача 9.79

Рассмотрим цепь Маркова со счетным числом состояний $\left\{ \ldots -k,-k+1, \ldots ,-1,0,1, \ldots , k, \ldots \right\}$ и вероятностями перехода за один шаг

P_{i j} = \begin{cases} p, & j = i+1, \\ 1-p, & j = i-1, \\ 0, & \text{ для остальных } j . \end{cases}

Найти производящую функцию времени возвращения в состояние 0.

?

Задача 9.80

Пусть дана цепь Маркова с состояниями ( $0, \ldots , N$ ) и матрицей вероятностей перехода за один шаг

\begin{aligned} P_{i j} & = \begin{cases} p, & j = i+1 \\ 1-p, & j = i-1, \quad i = 1, \ldots , N-1, \end{cases} \\ P_{00} & = P_{N N} = 1. \end{aligned}

Найти математическое ожидание времени до поглощения, при условии, что начальное состояние $k$ .

?

Задача 9.81

Пусть цепь Маркова с состояниями $0,1, \ldots , N$ имеет матрицу вероятностей перехода за один шаг

P_{i j} = \begin{cases} b_{i}, & j = i-1, \\ a_{i}, & j = i+1, \\ 1-\left(a_{i}+b_{i}\right), & j = i, \\ 0, & \left|j-i\right| > 1, \end{cases}

где $\quad a_{0} = b_{0} = a_{N} = b_{N} = 0, a_{i} > 0, b_{i} > 0, i = 1, \ldots , N-1$ . Найти вероятность поглощения в состоянии 0 , исходя из состояния $k$ .

?

Задача 9.82

Пусть $\xi_{1}, \xi_{2}, \ldots$ — независимые, одинаково распределенные случайные величины, $\mathbb {P}\left(\xi_{1} = 1\right) = \mathbb {P}\left(\xi_{1} = -1\right) = 1 / 2, z_{0} = 0, z_{k} = z_{k-1}+\xi_{k}$ , $k = 1,2, \ldots$ Положим $\tau_{N} = \min \left\{ n \geqslant 1:\left|z_{n}\right| = N\right\}$ . Найти $\mathbb {E}\left[\tau_{N}\right]$ .

?

Задача 9.83

Матрица вероятностей перехода за один шаг цепи Маркова с множеством состояний ( $0,1, \ldots , N$ ) имеет вид

\left[\begin{smallmatrix} 0 & 1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 1 / 2 & 0 & 1 / 2 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2 & \ldots & 0 & 0 & 0 \\ . & . & . & . & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & 0 & \ldots & 1 / 2 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & \ldots & 0 & 1 & 0 \end{smallmatrix}\right] .

Найти матрицу вероятностей перехода за $n$ шагов.

?

Задача 9.84

Пусть $\xi_{0}, \xi_{1}, \ldots$ — неразложимая возвратная положительная цепь Маркова, $\mathbb {P}\left(\xi_{0} = i\right) = 1, N_{n}(i)$ — число возвращений в состояние $i$ за первые $n$ шагов. Доказать, что $\lim_{n \rightarrow \infty } \frac{\mathbb {E}\left[N_{n}(i)\right]}{n} = \frac{1}{\mu_{i}}$ , где $\mu_{i}$ — среднее время возвращения в состояние $i$ .

?

Задача 9.85

Пусть для неразложимой марковской цепи с состояниями $\left\{ 0,1,2, \ldots \right\}$ существует $\alpha > 0$ , такое, что $f_{i 0} \geqslant \alpha$ для всех $i \neq 0$ . Доказать, что все состояния цепи возвратны.

?

Дискретные цепи Маркова