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

Задача 6.1

Пусть $\left(P_{ij}; i, j \geq 0\right)$ — набор вероятностей перехода для марковской цепи со счётным числом состояний. Для каждых $i, j$ пусть $\mathsf{F}_{ij}(n)$ — вероятность того, что состояние $j$ встречается когда-либо между моментами времени 1 и $n$ включительно, при условии $X_{0} = i$ . Для некоторого заданного $j$ предположим, что $\left\{ x_{i}; i \geq 0\right\}$ — набор неотрицательных чисел, удовлетворяющих $x_{i} = P_{ij}+\sum_{k \neq j} P_{ik} x_{k}$ для всех $i \geq 0$ . Покажите, что $x_{i} \geq \mathsf{F}_{ij}(n)$ для всех $n$ и $i$ , а следовательно, что $x_{i} \geq \mathsf{F}_{ij}(\infty )$ для всех $i$ .

?

Задача 6.2

(a)(b)

Рассмотрим цепь Маркова, изображённую ниже. {#fig-1 width="60%"}

?

(a)

Для цепи Маркова, изображённой выше, покажите, что при $p \geq 1/2$ выполняется $\mathsf{F}_{00}(\infty ) = 2(1-p)$ , и покажите, что $\mathsf{F}_{i0}(\infty ) = [(1-p)/p]^{i}$ для $i \geq 1$ . Заметьте, что тем самым вы показали, что цепь транзиентна при $p > 1/2$ и рекуррентна при $p = 1/2$ .

(b)

При тех же условиях, что и в (а), покажите, что $\mathsf{F}_{ij}(\infty )$ равно $2(1-p)$ при $j = i$ , равно $[(1-p)/p]^{i-j}$ при $i > j$ и равно 1 при $i < j$ .

Задача 6.3

(a)(b)(c)

?

(a)

Покажите, что вероятности перехода $n$ -го порядка, начиная из состояния 0, для цепи Маркова из упражнения 6.2 удовлетворяют равенству

P_{0j}^{n} = p P_{0, j-1}^{n-1}+q P_{0, j+1}^{n-1} \quad j \neq 0; \qquad P_{00}^{n} = q P_{00}^{n-1}+q P_{01}^{n-1}.

(b)

Для $p = 1/2$ используйте это равенство, чтобы вычислить $P_{0j}^{n}$ итеративно для $n = 1, 2, 3, 4$ . Проверьте (6.3) для этих значений, а затем используйте индукцию, чтобы доказать (6.3) в общем случае. Замечание: для $p \neq 1/2$ это превращается в совершенно неподъёмную выкладку, поэтому не пытайтесь делать это в общем случае.

(c)

В качестве более интересного подхода, который проявляет связь между цепью Маркова из упражнения 6.2 и цепью Маркова на рисунке 6.1 (цепь Маркова со счётным пространством состояний, моделирующая процесс Бернулли; пространство состояний — целые числа, с вероятностью перехода $p$ из состояния $i$ в $i+1$ и $q = 1-p$ из состояния $i$ в $i-1$ , для всех $i$ ), заметьте, что (6.3) при чётном $j+n$ является вероятностью того, что $S_{n} = j$ для цепи на рисунке 6.1, а (6.3) при нечётном $j+n$ является вероятностью того, что $S_{n} = -j-1$ для цепи на рисунке 6.1. Рассматривая каждый переход по петле в состоянии 0 как смену знака для цепи на рисунке 6.1, объясните, почему этот удивительный результат верен. (Опять же, это не работает для $p \neq 1/2$ , поскольку смена знака также меняет местами переходы $+1, -1$ .)

Задача 6.4

Пусть $j$ — невозвратное состояние в цепи Маркова, и пусть $j$ достижимо из $i$ . Покажите, что $i$ также невозвратно. Истолкуйте это как форму закона Мёрфи (если что-то плохое может случиться, оно случится, где плохим является отсутствие возможного возврата).

?

Задача 6.5

В этой задаче рассматривается математическая деталь из доказательства леммы 6.2.4. Предположим, что $j$ возвратно, существует путь вероятности $\alpha > 0$ из $j$ в $i$ , и $n \geq 1$ — целое число. Пусть $T_{ji}$ — возможно, дефектная случайная величина, дающая время первого достижения из $j$ в $i$ . Проверьте следующие соотношения для любого целого $t > 0$ :

\begin{aligned} \mathbb {P}\left(T_{ji} > t\right) & = \mathbb {P}\left(T_{ji} > t, T_{jj}^{(n)} > t\right)+\mathbb {P}\left(T_{ji} > t, T_{jj}^{(n)} \leq t\right) \\ & \leq \mathbb {P}\left(T_{jj}^{(n)} > t\right)+\mathbb {P}\left(T_{ji} > T_{jj}^{(n)}\right) \\ & \leq \mathbb {P}\left(T_{jj}^{(n)} > t\right)+(1-\alpha )^{n}; \\ \mathbb {P}\left(T_{ji} > \infty \right) & \leq (1-\alpha )^{n}. \end{aligned}

?

Задача 6.6

(a)(b)(c)

Предположим, что состояние $j$ в счётной цепи Маркова возвратно и $i$ сообщается с $j$ . Точнее, предположим, что существует путь длины $m$ из $i$ в $j$ и путь длины $k$ из $j$ в $i$ .

?

(a)

Покажите, что для любого $n > 0$

P_{ii}^{m+n+k} \geq P_{ij}^{m} P_{jj}^{n} P_{ji}^{k}.

(b)

Суммируя по $n$ , покажите, что состояние $i$ также возвратно.

(c)

Объясните, почему это показывает, что все состояния класса либо возвратны, либо все невозвратны.

Задача 6.7

(a)(b)(c)(d)

Рассмотрим неприводимую положительно возвратную марковскую цепь. Вспомним технику нахождения ожидаемого времени первого достижения из $j$ в $i$ , то есть $\overline{T}_{ji}$ , использованную в разделе 4.5: состояние $i$ превращалось в поглощающее состояние путём замены всех переходов из $i$ на единственный переход $P_{ii} = 1$ . Здесь же, чтобы сохранить положительную возвратность, мы вместо этого заменяем все переходы из состояния $i$ на единственный переход $P_{ij} = 1$ .

?

(a)

Используя марковскую цепь из упражнения 6.2, покажите, что описанная выше стратегия может превратить неприводимую цепь в приводимую. Также объясните, почему состояния $i$ и $j$ остаются положительно возвратными и по-прежнему принадлежат одному и тому же классу.

(b)

Пусть $\left\{ \pi_{k}'; k \geq 0\right\}$ — стационарные вероятности положительно возвратного класса в изменённой марковской цепи. Покажите, что ожидаемое время первого достижения $\overline{T}_{ji}'$ из $j$ в $i$ в изменённой марковской цепи равно $(1/\pi_{i}')-1$ .

(c)

Покажите, что ожидаемое время первого достижения из $j$ в $i$ одинаково в изменённой и неизменённой цепях.

(d)

Покажите на примере, что после указанного выше изменения два состояния $i$ и $j$ , которые до изменения не были положительно возвратными, могут стать положительно возвратными, и указанную выше технику снова можно использовать для нахождения ожидаемого времени первого достижения.

Задача 6.8

(a)(b)

Пусть $\left\{ X_{n}; n \geq 0\right\}$ — ветвящийся процесс с $X_{0} = 1$ . Пусть $\overline{Y}$ и $\sigma^{2}$ — соответственно среднее значение и дисперсия числа потомков одной особи.

?

(a)

Обоснуйте, что $\lim_{n \rightarrow \infty } X_{n}$ существует с вероятностью 1 и принимает либо значение 0 (с вероятностью $\mathsf{F}_{10}(\infty )$ ), либо значение $\infty$ (с вероятностью $1-\mathsf{F}_{10}(\infty )$ ).

(b)

Покажите, что $\operatorname {Var}\left[X_{n}\right] = \sigma^{2} \overline{Y}^{n-1}(\overline{Y}^{n}-1)/(\overline{Y}-1)$ при $\overline{Y} \neq 1$ и $\operatorname {Var}\left[X_{n}\right] = n \sigma^{2}$ при $\overline{Y} = 1$ .

Задача 6.9

Имеется $n$ состояний, и для каждой пары состояний $i$ и $j$ задано положительное число $d_{ij} = d_{ji}$ . Частица перемещается из состояния в состояние следующим образом. Если частица находится в состоянии $i$ , она перейдёт в любое $j \neq i$ с вероятностью $P_{ij}$ , задаваемой формулой

P_{ij} = \frac{d_{ij}}{\sum _{j \neq i} d_{ij}}.

Предположим, что $P_{ii} = 0$ для всех $i$ . Покажите, что последовательность положений частицы является обратимой цепью Маркова, и найдите предельные вероятности.

?

Задача 6.10

Рассмотрим обратимую цепь Маркова с переходными вероятностями $P_{ij}$ и предельными вероятностями $\pi_{i}$ . Рассмотрим также ту же цепь, усечённую до состояний $0, 1, \ldots , M$ . То есть переходные вероятности $\left\{ P_{ij}'\right\}$ усечённой цепи задаются как

P_{ij}' = \begin{cases} \dfrac {P_{ij}}{\sum _{k=0}^{m} P_{ik}}, & 0 \leq i, j \leq M, \\ ]1ex] 0, & \text{иначе.} \end{cases} \[ Покажите, что усечённая цепь также обратима и имеет предельные вероятности, задаваемые формулой \] \overline{\pi }_{i} = \frac{\pi _{i} \sum _{j=0}^{M} P_{ij}}{\sum _{k=0}^{M}\left(\pi _{k} \sum _{m=0}^{M} P_{km}\right)}.

?

Задача 6.11

(a)(b)

Марковская цепь (с состояниями $\left\{ 0, 1, 2, \ldots , J-1\right\}$ , где $J$ конечно или счётно) имеет переходные вероятности $\left\{ P_{ij}; i, j \geq 0\right\}$ . Предположим, что $P_{0j} > 0$ для всех $j > 0$ и $P_{j0} > 0$ для всех $j > 0$ . Также предположим, что для всех $i, j, k$ выполняется $P_{ij} P_{jk} P_{ki} = P_{ik} P_{kj} P_{ji}$ .

?

(a)

Предполагая дополнительно, что все состояния положительно возвратны, покажите, что цепь обратима, и найдите стационарные вероятности $\left\{ \pi_{i}\right\}$ в простейшем виде.

(b)

Найдите условие на $\left\{ P_{0j}; j \geq 0\right\}$ и $\left\{ P_{j0}; j \geq 0\right\}$ , достаточное для того, чтобы все состояния были положительно возвратны.

Задача 6.12

(a)(b)(c)

?

(a)

Используя модель рождения и гибели, описанную на рисунке 6.4 (марковская цепь рождения--гибели: пространство состояний — неотрицательные целые числа, вероятность перехода $p_{i}$ из состояния $i$ в $i+1$ , $q_{i}$ из состояния $i$ в $i-1$ , и $1-p_{i}-q_{i}$ — вероятность самоперехода), найдите стационарное распределение вероятностей числа заявок в системе (очередь плюс прибор обслуживания) для следующих систем массового обслуживания:

M/M/1 с вероятностью прихода $\lambda \delta$ , вероятностью завершения обслуживания $\mu \delta$ ;
M/M/m с вероятностью прихода $\lambda \delta$ , вероятностью завершения обслуживания $i \mu \delta$ при $i$ занятых приборах, $1 \leq i \leq m$ ;
M/M/ $\infty$ с вероятностью прихода $\lambda \delta$ , вероятностью обслуживания $i \mu \delta$ при $i$ приборах. Предположите, что $\delta$ настолько мало, что $i \mu \delta < 1$ для всех интересующих нас $i$ . Предположите, что система положительно возвратна.

(b)

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

(c)

Для каждой из систем найдите:

$L =$ (стационарное) среднее число заявок в системе;
$L^{q} =$ (стационарное) среднее число заявок в очереди;
$W =$ (стационарное) среднее время ожидания в системе;
$W^{q} =$ (стационарное) среднее время ожидания в очереди.

Задача 6.13

(a)(b)(c)

?

(a)

Дано, что приход происходит в интервале $(n \delta , (n+1) \delta )$ для модели M/M/1 с дискретным временем на рисунке 6.5; найдите условное распределение вероятностей состояния системы в момент времени $n \delta$ (предположите, что $n$ произвольно велико, и предположите положительную возвратность).

(b)

Для той же модели, снова в стационарном режиме, но без условия прихода в интервале $(n \delta , (n+1) \delta )$ , найдите вероятность $Q(i, j)$ ( $i \geq j > 0$ ) того, что система находится в состоянии $i$ в момент $n \delta$ и что $i-j$ уходов происходит до следующего прихода.

(c)

Найдите ожидаемое число заявок, застигнутых в системе первым приходом после момента времени $n \delta$ .

Задача 6.14

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

?

Задача 6.15

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Задача 6.16

(a)(b)(c)

Пусть $\left\{ X_{n}, n \geq 1\right\}$ обозначает положительно возвратную марковскую цепь со счётным пространством состояний. Рассмотрим теперь новый случайный процесс $\left\{ Y_{n}, n \geq 0\right\}$ , который принимает только те значения марковской цепи, что лежат между 0 и некоторым целым числом $m$ . Например, если $m = 3$ и $X_{1} = 1, X_{2} = 3, X_{3} = 5, X_{4} = 6, X_{5} = 2$ , то $Y_{1} = 1, Y_{2} = 3, Y_{3} = 2$ .

?

(a)

Является ли $\left\{ Y_{n}, n \geq 0\right\}$ марковской цепью? Кратко объясните.

(b)

Пусть $p_{j}$ обозначает долю времени, которую $\left\{ X_{n}, n \geq 1\right\}$ проводит в состоянии $j$ . Если $p_{j} > 0$ для всех $j$ , какую долю времени $\left\{ Y_{n}, n \geq 0\right\}$ проводит в каждом из состояний $0, 1, \ldots , m$ ?

(c)

Предположим, что $\left\{ X_{n}\right\}$ нулевая возвратная, и пусть $p_{i}(m), i = 0, 1, \ldots , m$ обозначают долгосрочные доли для $\left\{ Y_{n}, n \geq 0\right\}$ . Покажите, что для $j \neq i$ выполняется $p_{j}(m) = p_{i}(m) \mathbb {E}\left[\text{время, проводимое процессом }X\text{ в состоянии }j\text{ между возвращениями в }i\right]$ .

Задача 6.17

Эта задача касается циклической (round-robin) системы массового обслуживания из раздела 6.8. Там состояние обозначается как $\mathbf{m} = (m, z_{1}, \ldots , z_{m})$ , где $m$ — число клиентов в системе, а $z_{i}$ , $1 \leq i \leq m$ , — объём обслуживания, уже полученного клиентом на позиции $i$ очереди (позиция 1 обслуживается, остальные ожидают); $\phi$ обозначает пустое состояние. Клиенты поступают согласно процессу Бернулли с интенсивностью $\lambda$ на шаг, каждому требуется целое число шагов обслуживания с ПМР $f(w)$ и дополнительной ФР $\overline{F}(w)$ ; клиент, находящийся на обслуживании, получает один шаг обслуживания за единицу времени и, если ещё не завершил обслуживание, перемещается в конец очереди (дисциплина обслуживания round-robin). Для этой системы выдвигается гипотеза о обратной марковской цепи, с угаданными обратными вероятностями перехода, подобранными так, чтобы удовлетворять уравнениям баланса для: перехода вращения (обозначен (6.56)), перехода ухода (обозначен (6.57)), перехода прибытия (обозначен (6.58)), и переходов в пустое состояние $\phi$ и из него (обозначены (6.59)). Подстановка угаданных обратных вероятностей в эти уравнения и их решение даёт гипотетическую стационарную вероятность

\pi _{\mathbf{s}} = \left(\frac{\lambda }{1-\lambda }\right)^{m}\left(\prod _{j=1}^{m} \overline{F}(z_{j})\right) \pi _{\phi }, \tag {6.62}

где состояние $\mathbf{s}$ равно $\mathbf{s} = (m, z_{1}, \ldots , z_{m})$ , а время нормировано так, что $\delta = 1$ — единица времени обслуживания. Проверьте, что (6.58) удовлетворяется гипотетическим решением для $\pi$ из (6.62). Также покажите, что уравнения, включающие простаивающее состояние $\phi$ , удовлетворяются.

?

Задача 6.18

(a)(b)(c)(d)

Замените состояние $\mathbf{m} = (m, z_{1}, \ldots , z_{m})$ в разделе 6.8 расширенным состоянием $\mathbf{m} = (m, z_{1}, w_{1}, z_{2}, w_{2}, \ldots , z_{m}, w_{m})$ , где $m$ и $\left\{ z_{i}; 1 \leq i \leq m\right\}$ такие же, как и раньше, а $w_{1}, w_{2}, \ldots , w_{m}$ — исходные требуемые объёмы обслуживания $m$ клиентов.

?

(a)

Предполагая ту же обратную циклическую (round-robin) систему, что была предположена в разделе 6.8, найдите обратные вероятности перехода и приведите уравнения, соответствующие (6.56)--(6.59), для расширенного описания состояния.

(b)

Решите получившиеся уравнения, чтобы показать, что

\pi _{\mathbf{m}} = \pi _{\phi }\left(\frac{\lambda \delta }{1-\lambda \delta }\right)^{m} \prod _{j=1}^{m} f(w_{j}).

(c)

Покажите, что вероятность того, что в системе находится $m$ клиентов и что исходные требуемые объёмы обслуживания этих клиентов равны $w_{1}, \ldots , w_{m}$ , равна

\mathbb {P}\left(m, w_{1}, \ldots , w_{m}\right) = \pi _{\phi }\left(\frac{\lambda \delta }{1-\lambda \delta }\right)^{m} \prod _{j=1}^{m}(w_{j}-1) f(w_{j}).

(d)

Дано, что клиент имеет исходный требуемый объём обслуживания $w$ ; найдите ожидаемое время, которое этот клиент проводит в системе.

Марковские цепи со счётным числом состояний