Стационарные распределения и предельная теорема

Корректурный экземпляр книги читает бесконечная последовательность редакторов, проверяющих его на наличие ошибок. При каждом прочтении каждая ошибка обнаруживается с вероятностью $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)$.