Контрольная Работа: Примеры

\[\newcommand{\st}{\, : \:} \newcommand{\ind}[1]{\mathbf{1}_{#1}} \newcommand{\dd}{\mathrm{d}}\]

У вас есть 1 час 50 минут.
Вы можете проверить свои записи, книги и конспекты лекций на общем планшете.
Вы не можете использовать свои собственные электронные устройства.

Задачи

Упражнение 1 У меня есть $3$ зонта, и каждый из них может быть либо дома, либо в офисе. Каждый раз, когда я иду из дома в офис или из офиса домой, я беру с собой зонт, только если идёт дождь. Однако, если доступных зонтов нет, а на улице дождь, я промокаю. Вероятность того, что во время похода из офиса домой или из дома в офис идёт дождь, равна $p$. Найдите вероятность того, что я промокну во время произвольного похода.

Решение

Здесь время $t$ представляет собой количество посещённых мест (офис/дом). Пусть $X_t$ — количество зонтов в том месте, где я нахожусь. Это цепь Маркова с пространством состояний $S=\{0,1,2,3\}$. Если $x=0$, то $p_{0,3}=1$, так как после смены места все зонты окажутся в новом месте. $p_{1,3}=p$ (поскольку я возьму с собой единственный доступный зонт, только если идёт дождь), $p_{1,2}=1-p$; аналогично, $p_{2,2}=p=1-p_{2,1}$; и, наконец, $p_{3,1}=p=1-p_{3,0}$. Другими словами, для $x\ge 1$, $p_{x,y}=p$, если $y=4-x$ (поскольку я возьму зонт с собой), и $p_{x,y}=1-p$, если $y=3-x$.

Тогда матрица переходных вероятностей имеет вид \[ P = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1-p & p \\ 0 & 1-p & p & 0 \\ 1-p & p & 0 & 0 \end{pmatrix} \]

Рисунок 1

Это неразложимая цепь Маркова с единственной инвариантной вероятностью. Легко видеть, что $m_3=m_2=m_1$. Тогда, используя $mP=m$, получаем $m=(\tfrac{1-p}{4-p},\tfrac{1}{4-p},\tfrac{1}{4-p},\tfrac{1}{4-p})$. Вероятность промокнуть тогда равна $m_0 p = \tfrac{p(1-p)}{4-p}$.

Эта вероятность максимальна при $p = 2(2-\sqrt{3}) \approx 0.54$, что соответствует погоде в Москве. Заметим также, что если у меня будет $N$ зонтов, вероятность промокнуть станет равной $p(1-p)/(N+1-p) \le 1/(4N)$.

Упражнение 2 Дамокл был придворным при дворе тирана Дионисия Сиракузского. Время от времени Дионисий даёт ему задание, и в зависимости от результата отношение тирана к Дамоклу меняется. Однако со временем возможны только два исхода:

Дамокл становится фаворитом при дворе и получает высокий титул. Это приносит ему $a$ драхм.
Дамокла изгоняют и лишают всего, что у него есть, стоимостью в $b$ драхм.

Мы можем смоделировать репутацию Дамокла как однородную цепь Маркова с конечным числом состояний, которая рано или поздно попадёт либо в множество $A$ (достижение высокого титула), либо в множество $B$ (изгнание). Например, мы можем считать, что репутация — это целое числовое значение $x$ в диапазоне от $0$ (изгнание) до $100$ (высокий титул).

а. Предполагая, что мы знаем переходные вероятности, сформулируйте линейную задачу для определения ожидаемого количества драхм, заработанных Дамоклом, если он начинает свою службу с репутацией $x\in S$.

В какой-то момент Дионисий, как известно, подвешивает над головой Дамокла меч, удерживаемый одним конским волосом. Перед выполнением каждого задания меч с вероятностью $p>0$ может упасть на голову Дамокла (убив его).

б. Сформулируйте линейную задачу для определения ожидаемого количества драхм, заработанных Дамоклом, если он начинает свою службу с репутацией $x\in S$, когда над его головой висит меч.

Решение

Пусть $\tau$ — первый момент времени, когда репутация Дамокла определяется (то есть он получает высокий титул или его изгоняют). Обусловливая по первому шагу, функция $h(x)= \mathbb{E}[a \mathbf{1}_{X_{\tau}\in A}+ b\mathbf{1}_{X_{\tau}\in B} ]$ является решением задачи \[ \begin{aligned} & (I-P)h= 0 \qquad \text{на $(A\cup B)^c$} \\ & h=a \qquad \text{на $A$} \\ & h=b \qquad \text{на $B$} \end{aligned} \]

Если мы добавим Дамоклов меч, мы можем, например, считать, что добавляем дополнительную точку $\xi$ в пространство состояний, скажем, $S'=S \cup \{\xi\}$. Если $(p_{x,y})$ — исходные переходные вероятности, то новая цепь Маркова имеет переходные вероятности, задаваемые формулами \[ \begin{aligned} & q_{x,\xi}=p, \qquad x\in S \\ & q_{x,y}= (1-p) p_{x,y} \qquad x,y\in S \\ & q_{\xi,\xi}=1 \end{aligned} \] Мы имеем ту же формулу для $h$, только теперь $\tau$ — это первый момент времени, когда цепь попадает в $A\cup B \cup \{\xi\}$. $h(x)$ теперь удовлетворяет, для $x\in S \setminus (A\cup B)$, уравнению $h(x)= \sum_{y\in S} q_{x,y} h(y)+0 q_{x,\xi}$. А именно, снова как уравнение на $S$ ($\xi$ было лишь вспомогательным): \[ \begin{aligned} & (I-(1-p)P)h= 0 \qquad \text{на $(A\cup B)^c$} \\ & h=a \qquad \text{на $A$} \\ & h=b \qquad \text{на $B$} \end{aligned} \]

Упражнение 3 Для однородной цепи Маркова объясните, почему каждая точка в незамкнутом сообщающемся классе $C$ является транзитной.

Решение

Поскольку $C$ не является замкнутым, существуют $y\in C$, $z\not \in C$ такие, что $p_{y,z}>0$. Но $x \leftrightarrow y$ и $z \not \rightarrow x$. Пусть $t$ — наименьшее время такое, что $p^{(t)}_{x,y}>0$. Тогда $q:=p^{(t+1)}_{x,z}\ge p^{(t)}_{x,y} p_{y,z}>0$. Тогда каждый раз, когда цепь попадает в $x$, она с вероятностью не менее $q>0$ никогда не вернётся. Следовательно, она вернётся лишь конечное число раз.

Упражнение 4 Неразложимая цепь Маркова на $\mathbb{N}$ обладает следующей особенностью. Для каждого $x\in S$ выполняется $p_{x,0}\ge p$ для некоторого $p>0$.

а. Докажите, что $\mathbb{E}_x[\tau_x^+]<\infty$. б. Выведите (используя известные результаты), что существует единственная инвариантная вероятность $m$. в. Оцените \[ \sup_x | \mathbb{P}_y(X_t=x) - m_x| \le ? \]

Решение

а. Зафиксируем $x$. В силу неразложимости, для некоторого $t$ имеем $p^{(t)}_{0,x}>0$. Таким образом, на каждом шаге мы с вероятностью не менее $p$ переходим в $0$ за один шаг, а затем возвращаемся в $x$ за $t$ шагов: \[ \begin{aligned} & \mathbb{P}_0(\tau_x^+ \le t) \ge p^{(t)}_{0,x} \\ & \mathbb{P}_y(\tau_x^+ \le t+1) \ge p p^{(t)}_{0,x}:=q \\ & \mathbb{P}_x(\tau_x^+ \ge k(t+1)) \le (1- q)^k \end{aligned} \] и, следовательно, её математическое ожидание конечно.

б. Каждая неразложимая, положительно возвратная цепь Маркова допускает единственную инвариантную вероятность $m$.

в. Пусть $Y_t$ — независимая цепь, запущенная с начальным распределением $m$. Пусть $\tau$ — первый момент времени, когда $X_t=Y_t$. Мы имеем, что \[ | \mathbb{P}_y(X_t=x) - m_x| \le \mathbb{P}(\tau > t) \le (1-p^2)^t \] При некоторой осторожности мы можем построить $(X,Y)$ так, чтобы на каждом шаге они оба с вероятностью $p$ достигали $0$. С тем же рассуждением мы получаем границу $(1-p)^t$.