Задачи

Классифицируйте состояния дискретных марковских цепей с пространством состояний $S = \left\{ 1,2,3,4\right\}$ и следующими матрицами переходных вероятностей:

Матрица переходных вероятностей называется дважды стохастической, если суммы всех её столбцов равны $1$, то есть если $\sum_{i} p_{i j} = 1$ для всех $j \in S$.

Докажите, что сообщающиеся между собой состояния марковской цепи имеют одинаковый период.

Предположим, что $\left\{ X_{n}: n \geq 0\right\}$ — дискретная марковская цепь с $X_{0} = i$. Пусть $N$ — общее число последующих посещений цепью состояния $j$. Покажите, что

и выведите отсюда, что $\mathbb {P}\left(N = \infty \right) = 1$ тогда и только тогда, когда $f_{i j} = f_{j j} = 1$.

Пусть $i$ и $j$ — два состояния дискретной марковской цепи. Покажите, что если $i$ сообщается с $j$, то существует положительная вероятность достичь $j$ из $i$, ни разу не вернувшись в $i$ по пути. Выведите отсюда, что если цепь неприводима и возвратна, то вероятность $f_{i j}$ когда-либо достичь $j$ из $i$ равна 1 для всех $i$ и $j$.

Пусть $\left\{ X_{n}: n \geq 0\right\}$ — возвратная неприводимая марковская цепь на пространстве состояний $S$ с матрицей переходных вероятностей $\mathbf{P}$, и пусть $\mathbf{x}$ — положительное решение уравнения $\mathbf{x} = \mathbf{x P}$.

Последовательность $u = \left\{ u_{n}: n \geq 0\right\}$ называется «последовательностью восстановления», если

для некоторого семейства $f = \left\{ f_{n}: n \geq 1\right\}$ неотрицательных чисел, суммирующихся в 1.

Рассмотрим симметричное случайное блуждание в трёх измерениях по множеству точек $\left\{ (x, y, z): x, y, z = 0, \pm 1, \pm 2, \ldots \right\}$; этот процесс представляет собой последовательность точек $\left\{ \mathbf{X}_{n}: n \geq 0\right\}$, такую что $\mathbb {P}\left(\mathbf{X}_{n+1} = \mathbf{X}_{n}+\vect {\epsilon }\right) = \frac{1}{6}$ для $\vect {\epsilon } = (\pm 1,0,0),(0, \pm 1,0),(0,0, \pm 1)$. Предположим, что $\mathbf{X}_{0} = (0,0,0)$. Покажите, что

и с помощью формулы Стирлинга выведите отсюда, что начало координат — невозвратное состояние.

Рассмотрим трёхмерную версию модели рака (6.12.12). Если $\kappa = 1$, неизбежны ли в этом случае империи из теоремы (6.12.14)?

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

Классифицируйте состояния цепи. Предположим, что $\alpha \beta > 0$ и $\alpha \beta \neq 1$. Найдите $n$-шаговые переходные вероятности и покажите непосредственно, что они сходятся к единственному стационарному распределению при $n \rightarrow \infty$. При каких значениях $\alpha$ и $\beta$ цепь обратима в равновесии?

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

Рассмотрим марковскую цепь на множестве $S = \left\{ 0,1,2, \ldots \right\}$ с переходными вероятностями $p_{i, i+1} = a_{i}$, $p_{i, 0} = 1-a_{i}, i \geq 0$, где $\left(a_{i}: i \geq 0\right)$ — последовательность постоянных, удовлетворяющих $0 < a_{i} < 1$ при всех $i$. Пусть $b_{0} = 1, b_{i} = a_{0} a_{1} \cdots a_{i-1}$ при $i \geq 1$. Покажите, что цепь

Пусть $X$ — марковская цепь с непрерывным временем, счётным пространством состояний $S$ и полугруппой $\left\{ \mathbf{P}_{t}\right\}$. Покажите, что $p_{i j}(t)$ — непрерывная функция $t$. Пусть $g(t) = -\log p_{i i}(t)$; покажите, что $g$ — непрерывная функция, $g(0) = 0$, и $g(s+t) \leq g(s)+g(t)$. Говорят, что $g$ «субаддитивна», и хорошо известная теорема даёт результат, что

Выведите отсюда, что предел $g_{i i} = \lim_{t \downarrow 0} t^{-1}\left\{ p_{i i}(t)-1\right\}$ существует.

Пусть $X$ — марковская цепь с непрерывным временем и генератором $\mathbf{G} = \left(g_{i j}\right)$. Покажите, что $X$ неприводима тогда и только тогда, когда для любой пары различных состояний $i, j$ существует последовательность различных состояний $i, k_{1}, k_{2}, \ldots , k_{n}, j$, такая что $g_{i, k_{1}} g_{k_{1}, k_{2}} \cdots g_{k_{n}, j} > 0$.

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

— матрица переходных вероятностей. Покажите, что полугруппа $\left\{ \mathbf{P}_{t}\right\}$ переходных вероятностей в непрерывном времени, такая что $\mathbf{P}_{1} = \mathbf{P}$, существует тогда и только тогда, когда $\frac{1}{2} < \alpha < 1$. В этом случае покажите, что $\left\{ \mathbf{P}_{t}\right\}$ единственна, и вычислите её через $\alpha$.

Рассмотрим процесс иммиграции-гибели $X(t)$ — процесс рождения и гибели с интенсивностями $\lambda_{n} = \lambda$, $\mu_{n} = n \mu$. Покажите, что его производящая функция $G(s, t) = \mathbb {E}\left[s^{X(t)}\right]$ задаётся формулой

где $\rho = \lambda / \mu$ и $X(0) = I$. Выведите отсюда предельное распределение $X(t)$ при $t \rightarrow \infty$.

Пусть $N$ — неоднородный пуассоновский процесс на $\mathbb {R}_{+} = [0, \infty )$ с функцией интенсивности $\lambda$.

Последовательные предложения за мой дом — независимые одинаково распределённые случайные величины $X_{1}$, $X_{2}, \ldots$ с плотностью $f$ и функцией распределения $F$. Пусть $Y_{1} = X_{1}$, пусть $Y_{2}$ — первое предложение, превышающее $Y_{1}$, и вообще пусть $Y_{n+1}$ — первое предложение, превышающее $Y_{n}$. Покажите, что $Y_{1}, Y_{2}, \ldots$ являются моментами поступлений в неоднородном пуассоновском процессе с функцией интенсивности $\lambda (t) = f(t) /(1-F(t))$. Величины $Y_{i}$ называются «рекордными значениями».

Теперь пусть $Z_{1}$ — первое полученное предложение, являющееся на данный момент вторым по величине, и пусть $Z_{2}$ — второе такое предложение, и так далее. Покажите, что $Z_{i}$ являются моментами поступлений неоднородного пуассоновского процесса с функцией интенсивности $\lambda$.

Пусть $N$ — пуассоновский процесс с постоянной интенсивностью $\lambda$, и пусть $Y_{1}, Y_{2}, \ldots$ — независимые случайные величины с общей характеристической функцией $\phi$ и плотностью $f$. Процесс $N^{*}(t) = Y_{1}+Y_{2}+\cdots +Y_{N(t)}$ называется сложным пуассоновским процессом. $Y_{n}$ — изменение значения $N^{*}$ при $n$-м поступлении пуассоновского процесса $N$. Представьте это так. «Случайный будильник» звонит в моменты поступлений пуассоновского процесса. При $n$-м звонке процесс $N^{*}$ накапливает дополнительную величину $Y_{n}$. Запишите прямое уравнение для $N^{*}$ и с его помощью найдите характеристическую функцию $N^{*}(t)$. Видите ли вы непосредственно, почему она имеет найденную вами форму?

Если функция интенсивности $\lambda$ неоднородного пуассоновского процесса $N$ сама является случайным процессом, то $N$ называется дважды стохастическим пуассоновским процессом (или процессом Кокса).

Покажите, что простой процесс рождения $X$ с параметром $\lambda$ является дважды стохастическим пуассоновским процессом с функцией интенсивности $\lambda (t) = \lambda X(t)$.

Марковская цепь $X = \left\{ X(t): t \geq 0\right\}$ — это процесс рождения, интенсивности $\lambda_{k}(t)$ которого зависят также от времени $t$ и задаются как

при $h \downarrow 0$. Покажите, что производящая функция вероятностей $G(s, t) = \mathbb {E}\left[s^{X(t)}\right]$ удовлетворяет

Отсюда найдите среднее и дисперсию $X(t)$, когда $X(0) = I$.

Найдите хорошее необходимое условие и хорошее достаточное условие для того, чтобы процесс рождения и гибели $X$ из задачи (6.15.25а) был честным.

Пусть $X$ — простой симметричный процесс рождения и гибели с $\lambda_{n} = \mu_{n} = n \lambda$, и пусть $T$ — время до вырождения. Покажите, что

и выведите отсюда, что вырождение достоверно, если $\mathbb {P}\left(X(0\right) < \infty ) = 1$. Покажите, что $\mathbb {P}\left(\lambda T / I \leq x \mid X(0\right) = I) \rightarrow e^{-1 / x}$ при $I \rightarrow \infty$.

Пусть $X$ — процесс иммиграции-гибели-катастроф, то есть процесс рождения и гибели с параметрами $\lambda_{i} = \lambda , \mu_{i} = i \mu$, с дополнительной возможностью «катастроф», сводящих популяцию к 0. Катастрофы происходят в моменты пуассоновского процесса интенсивности $\delta$, независимо от всех предшествующих рождений и гибелей.

С каждым достаточно «хорошим» (скажем, измеримым по Лебегу) подмножеством $B$ вещественной прямой $\mathbb {R}$ связана случайная величина $X(B)$, такая что

(a) $X(B)$ принимает значения в $\left\{ 0,1,2, \ldots \right\}$,

(b) если $B_{1}, B_{2}, \ldots , B_{n}$ не пересекаются, то $X\left(B_{1}\right), X\left(B_{2}\right), \ldots , X\left(B_{n}\right)$ независимы, и, кроме того, $X\left(B_{1} \cup B_{2}\right) = X\left(B_{1}\right)+X\left(B_{2}\right)$

(c) распределение $X(B)$ зависит от $B$ только через её меру Лебега («длину») $\left|B\right|$, и

Покажите, что $X$ — пуассоновский процесс.

Пусть $N$ — пуассоновский процесс на $\mathbb {R}^{2}$ с постоянной интенсивностью $\lambda$, и пусть $R_{(1)} < R_{(2)} <$... — упорядоченные расстояния от начала координат до точек процесса.

Пусть $X$ — $n$-мерный пуассоновский процесс с постоянной интенсивностью $\lambda$. Покажите, что объём наибольшего ($n$-мерного) шара с центром в начале координат, не содержащего ни одной точки $X$, имеет показательное распределение. Выведите отсюда плотность расстояния $R$ от начала координат до ближайшей точки $X$. Покажите, что $\mathbb {E}\left[R\right] = \Gamma (1 / n) /\left\{ n(\lambda c)^{1 / n}\right\}$, где $c$ — объём единичного шара в $\mathbb {R}^{n}$, а $\Gamma$ — гамма-функция.

Деревня из $N+1$ жителей охвачена эпидемией. Пусть $X(t)$ — число заболевших в момент времени $t$, и предположим, что $X(0) = 1$ и $X$ — процесс рождения с интенсивностями $\lambda_{i} = \lambda i(N+1-i)$. Пусть $T$ — время, необходимое для того, чтобы заболели все члены популяции. Покажите, что

и выведите отсюда, что

где $\gamma$ — постоянная Эйлера. Примечательно, что $\mathbb {E}\left[T\right]$ убывает с ростом $N$ при больших $N$.

Частица имеет скорость $V(t)$ в момент времени $t$, причём предполагается, что $V(t)$ принимает значения в $\left\{ n+\frac{1}{2}: n \geq 0\right\}$. Переходы в течение $(t, t+h)$ возможны следующим образом:

Первоначально $V(0) = \frac{1}{2}$. Пусть

Последовательность случайных целых чисел $X_{0}, X_{1}, \ldots$ строится следующим образом. Сначала $X_{0} = 0, X_{1} = 1$. При $n \geq 1$, при условии $X_{0}, X_{1}, \ldots , X_{n}$, следующее значение $X_{n+1}$ с равной вероятностью равно либо $X_{n}+X_{n-1}$, либо $\left|X_{n}-X_{n-1}\right|$.

Возьмём правильный шестиугольник и соединим противоположные углы прямыми линиями, пересекающимися в точке C. Частица совершает симметричное случайное блуждание по этим 7 вершинам, начиная из $\mathrm{A}( \neq \mathrm{C})$. Найдите:

Марковские цепи определяются следующими процедурами в произвольный момент времени $n$ :

Пусть $X$ — неприводимая марковская цепь с непрерывным временем на пространстве состояний $S$ с переходными вероятностями $p_{j k}(t)$ и единственным стационарным распределением $\vect {\pi }$, и запишем $\mathbb {P}\left(X(t\right) = j) = a_{j}(t)$. Если $c(x)$ — вогнутая функция, покажите, что функция $d(t) = \sum_{j \in S} \pi_{j} c\left(a_{j}(t) / \pi_{j}\right)$ возрастает до $c(1)$ при $t \rightarrow \infty$.

Относительная энтропия (или дивергенция Кульбака--Лейблера) двух строго положительных функций вероятностей $f, g$ на подмножестве $S$ целых чисел определяется как

Докажите, что если $X$ имеет конечное пространство состояний и стационарное распределение $\vect {\pi }$, то относительная энтропия $D(a(t) ; \vect {\pi })$ монотонно убывает до 0 при $t \rightarrow \infty$.

В обозначениях предыдущей задачи пусть $u_{k}(t) = \mathbb {P}\left(X(t\right) = k \mid X(0) = 0)$, и предположим, что цепь обратима в равновесии (см. задачу (6.15.16)). Покажите, что $u_{0}(2 t) = \sum_{j}\left(\pi_{0} / \pi_{j}\right) u_{j}(t)^{2}$, и выведите отсюда, что $u_{0}(t)$ убывает до $\pi_{0}$ при $t \rightarrow \infty$.

Пусть $\Pi$ — множество точек пуассоновского процесса на $\mathbb {R}^{d}$ с постоянной интенсивностью $\lambda$. Каждая точка смещается, причём смещения независимы и одинаково распределены. Покажите, что получившийся точечный процесс является пуассоновским процессом с интенсивностью $\lambda$.

Для удобства предположим в задаче (6.15.39), что смещения имеют непрерывную функцию распределения и конечное среднее, и что $d = 1$. Предположим также, что первоначально вы находитесь в начале координат, а в возмущённом процессе перемещаетесь в точку $a$. Пусть $\mathrm{L}_{\mathrm{R}}$ — число точек, ранее находившихся слева от вас, которые теперь находятся справа, а $\mathrm{R}_{\mathrm{L}}$ — число точек, ранее находившихся справа от вас, которые теперь находятся слева. Покажите, что $\mathbb {E}\left[\mathrm{L}_{\mathrm{R}}\right] = \mathbb {E}\left[\mathrm{R}_{\mathrm{L}}\right]$ тогда и только тогда, когда $a = \mu$, где $\mu$ — среднее смещение частицы.

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

Муравьи заходят на кухню в моменты пуассоновского процесса $N$ интенсивности $\lambda$; каждый из них посещает кладовую, а затем раковину, и уходит. $r$-й муравей проводит время $X_{r}$ в кладовой и $Y_{r}$ у раковины (и $X_{r}+Y_{r}$ на кухне в целом), причём векторы $V_{r} = \left(X_{r}, Y_{r}\right)$ и $V_{s}$ независимы при $r \neq s$. В момент времени $t = 0$ на кухне нет муравьёв. Найдите совместное распределение чисел $A(t)$ муравьёв в кладовой и $B(t)$ муравьёв у раковины в момент времени $t$.

Покажите, что при $t \rightarrow \infty$ число муравьёв на кухне сходится по распределению, при условии $\mathbb {E}\left[X_{r}+Y_{r}\right] < \infty$.

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

Пусть $\left\{ X_{r}: r \geq 1\right\}$ — независимые показательные случайные величины с параметром $\lambda$, и положим $S_{n} = \sum_{r = 1}^{n} X_{r}$. Покажите, что:

Пусть $X$ — дискретная марковская цепь с конечным числом состояний и матрицей переходных вероятностей $\mathbf{P} = \left(p_{i j}\right)$, где $p_{i j} > 0$ для всех $i, j$. Покажите, что существует $\lambda \in (0,1)$, такое что $\left|p_{i j}(n)-\pi_{j}\right| < \lambda^{n}$, где $\vect {\pi }$ — стационарное распределение.

В условиях задачи (6.15.43) пусть $V_{i}(n) = \sum_{r = 0}^{n-1} I_{\left\{ X_{r} = i\right\} }$ — число посещений цепью состояния $i$ до момента $n$. Покажите, что

Покажите далее, что если $f$ — произвольная ограниченная функция на пространстве состояний, то

Пусть $A$ и $\mathbf{B} = \left(B_{0}, B_{1}, \ldots , B_{n}\right)$ — дискретная случайная величина и вектор соответственно. Условная энтропия $A$ относительно $\mathbf{B}$ определяется как $H(A \mid \mathbf{B}) = \mathbb {E}\left[\mathbb {E}\left[-\log f(A \mid \mathbf{B}\right] \mid \mathbf{B}\right])$, где $f(a \mid \mathbf{b}) = \mathbb {P}\left(A = a \mid \mathbf{B} = \mathbf{b}\right)$. Пусть $X$ — апериодическая марковская цепь на конечном пространстве состояний. Покажите, что

и что

если $X$ апериодична с единственным стационарным распределением $\pi$.

Пусть $X$ и $Y$ — независимые возвратные процессы рождения и гибели с одинаковыми параметрами (и без взрывов). Не предполагается, что $X_{0} = Y_{0}$. Покажите, что:

Число птиц в лесу в момент времени $t$ — марковский процесс с непрерывным временем $X$. Пищевые ресурсы накладывают ограничение $0 \leq X(t) \leq n$. Конкуренция приводит к тому, что переходные вероятности подчиняются