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

Задача 6.3.1

Пусть $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$ . Классифицируйте состояния цепи и найдите их средние времена возврата.

?

Задача 6.3.2

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

?

Задача 6.3.3

(a)(b)

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

?

(a)

\left[\begin{smallmatrix} 1-2 p & 2 p & 0 \\ p & 1-2 p & p \\ 0 & 2 p & 1-2 p \end{smallmatrix}\right]

(b)

\left[\begin{smallmatrix} 0 & p & 0 & 1-p \\ 1-p & 0 & p & 0 \\ 0 & 1-p & 0 & p \\ p & 0 & 1-p & 0 \end{smallmatrix}\right]

В каждом случае вычислите $p_{i j}(n)$ и средние времена возврата состояний.

Задача 6.3.4

(a)(b)(c)

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

?

(a)

среднее число шагов до первого возвращения в $v$ ,

(b)

среднее число шагов до первого посещения $w$ ,

(c)

среднее число посещений $w$ до первого возвращения в $v$ .

Задача 6.3.5

(a)(b)

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

?

(a)

если $i \rightarrow j$ и $i$ возвратно, то $\eta_{i j} = \eta_{j i} = 1$ ,

(b)

$\eta_{i j} = 1$ тогда и только тогда, когда $\mathbb {P}_{i}\left(T_{j} < \infty \right) = \mathbb {P}_{j}\left(T_{j} < \infty \right) = 1$ .

Задача 6.3.6

Пусть $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)$ . Покажите, что

\eta _{j} = \begin{cases} 1 & \text{ если } j \in A \\ \sum _{k \in S} p_{j k} \eta _{k} & \text{ если } j \notin A\end{cases}

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

?

Задача 6.3.7

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

\rho _{j} = \begin{cases} 0 & \text{ если } j \in A \\ 1+\sum _{k \in S} p_{j k} \rho _{k} & \text{ если } j \notin A\end{cases}

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

?

Задача 6.3.8

Пусть $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$ ?

?

Задача 6.3.9

(a)(b)(c)

?

(a)

Покажите, что для каждой пары состояний $i, j$ неприводимой апериодической цепи существует $N = N(i, j)$ такое, что $p_{i j}(r) > 0$ при всех $r \geq N$ .

(b)

Покажите, что существует функция $f$ такая, что если $\mathbf{P}$ — матрица переходных вероятностей неприводимой апериодической марковской цепи с $n$ состояниями, то $p_{i j}(r) > 0$ для всех состояний $i, j$ и всех $r \geq f(n)$ .

(c)

Покажите далее, что $f(4) \geq 6$ и $f(n) \geq (n-1)(n-2)$ . [Указание: лемма о почтовой марке утверждает, что для взаимно простых $a, b$ наименьшее $n$ , такое что все целые числа, строго превосходящие $n$ , представимы в виде $\alpha a+\beta b$ при некоторых целых $\alpha , \beta \geq 0$ , равно $(a-1)(b-1)$ .]

Задача 6.3.10

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

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

?

Классификация цепей