Контрольная Работа

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

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

Задачи

Упражнение 1 Пусть $\mathbf{X}=(X_t)_{t\ge 0}$ — однородная цепь Маркова на конечном (или счётном) пространстве состояний $S$ с переходными вероятностями $(p_{x,y})_{x,y \in S}$ и начальным распределением $\mu \in \mathcal{P}(S)$, то есть $\mathbb{P}(X_0=x)=\mu_x$. Зафиксируем $T\ge 0$ и определим $Y_t=X_{T-t}$.

а. Докажите, что $\mathbf{Y}=(Y_t)_{t\in \{0,\ldots,T\}}$ обладает марковским свойством. [Вычислите $\mathbb{P}\left(Y_t = y_t | Y_{t-1} = y_{t-1}, \ldots, Y_0 = y_0 \right)$.] b. Предположим, что $\mu=m$ является инвариантной вероятностью для $\mathbf{X}$ и $m_x>0$ для всех $x\in S$. Проверьте, что $\mathbf{Y}$ является однородной цепью Маркова.

Решение

Чтобы доказать марковское свойство для $\mathbf{Y}$, мы должны показать, что вероятность состояния в момент времени $t$ зависит только от состояния в момент времени $t-1$, а не от каких-либо более ранних состояний. Пусть $y_0, y_1, \ldots, y_T$ — последовательность состояний, для которой $p_{y_{t-i},y_t}, \mu_{y_T}>0$ для всех $t\le T$. Зафиксируем $t\le T$; вычислим условную вероятность: \[ \begin{aligned} \mathbb{P}\left(Y_t = y_t | Y_{t-1} = y_{t-1}, \ldots, Y_0 = y_0\right) & = \frac{\mathbb{P}(Y_t=y_t, Y_{t-1} = y_{t-1}, \ldots, Y_0=y_0)}{\mathbb{P}(Y_{t-1}=y_{t-1}, \ldots, Y_0=y_0)} \\ & = \frac{\mathbb{P}(X_{T-t}=y_t, X_{T-t+1}=y_{t-1}, \ldots, X_T=y_0)}{\mathbb{P}(X_{T-t+1}=y_{t-1}, \ldots, X_T=y_0)} \\ & = \frac{\mathbb{P}(X_{T-t}=y_t) p_{y_t, y_{t-1}} p_{y_{t-1}, y_{t-2}} \cdots p_{y_1, y_0} }{ \mathbb{P}(X_{T-t+1}=y_{t-1}) p_{y_{t-1}, y_{t-2}} \cdots p_{y_1, y_0} } = \frac{\mathbb{P}(X_{T-t}=y_t) p_{y_t, y_{t-1}}}{\mathbb{P}(X_{T-t+1}=y_{t-1})} \end{aligned} \tag{1}\] Это конечное выражение зависит только от $y_t$ и $y_{t-1}$ (и от индекса времени $t$), а не от $y_{t-2}, \ldots, y_0$. Следовательно, $\mathbf{Y}$ обладает марковским свойством. Переходная вероятность $q_{x,y}^{(t)}$ для $\mathbf{Y}$ перейти из состояния $x$ в состояние $y$ в момент времени $t$ равна: \[ q_{x,y}^{t-1} = \mathbb{P}(Y_t = y | Y_{t-1}=x) = p_{y,x} \frac{\mathbb{P}(X_{T-t}=y)}{\mathbb{P}(X_{T-t+1}=x)} \tag{2}\] Поскольку переходные вероятности зависят от $t$ через распределения $X_{T-t}$ и $X_{T-t+1}$, обращённая цепь $\mathbf{Y}$, в общем случае, не является однородной.
Если начальное распределение $\mu$ является инвариантной вероятностью $m$, то цепь стационарна. Это означает, что для любого момента времени $t \ge 0$ распределение $X_t$ также равно $m$. То есть, $\mathbb{P}(X_t = x) = m_x$ для всех $t$. Мы можем подставить это в предыдущие формулы (либо Уравнение 1, либо Уравнение 2) и получить \[ q_{x,y} = p_{y,x} \frac{m_y}{m_x} \] Это новое выражение для переходных вероятностей, которое мы можем обозначить $p_{x,y}^\dagger$, зависит только от состояний $x$ и $y$ и стационарного распределения $m$. Оно больше не зависит от индекса времени $t$. Следовательно, когда исходная цепь стационарна, обращённая цепь $\mathbf{Y}$ является однородной цепью Маркова.

Упражнение 2 Игрок играет в повторяющуюся игру. На каждом ходу он выигрывает с вероятностью $p \in (0, 1)$ и проигрывает с вероятностью $1-p$. Чтобы поощрить игру, казино дарит бесплатную ночь в своем роскошном номере любому игроку, который одержит серию из $3$ последовательных побед. Игрок решает играть до тех пор, пока не выиграет приз (бесплатную ночь).

Смоделируйте этот процесс как цепь Маркова $(X_t)_{t \ge 0}$ на конечном пространстве состояний с поглощающим состоянием, представляющим выигрыш. Определите пространство состояний $S$, нарисуйте граф, представляющий цепь, найдите сообщающиеся классы и определите, какие из них являются замкнутыми, а какие — нет.
Для произвольной цепи Маркова с марковским оператором $P$ пусть $A$ — непустое подмножество пространства состояний $S$ («целевое множество»), и пусть $\tau_A = \inf\{t \ge 0 : X_t \in A\}$ — первый момент времени, когда цепь попадает в множество $A$. Для любого состояния $x \in S$ пусть $u(x) = \mathbb{E}_x[\tau_A \mathbf{1}_{\tau_A<\infty}]$ — математическое ожидание времени достижения $A$ при старте из $x$¹. Покажите, что $u$ является решением задачи для неизвестной функции $v$: \[ \begin{cases} (I-P)v=1 & \text{на $A^c$} \\ v=0 & \text{на $A$} \end{cases} \]
Предположим, что $p=1/2$. Казино может установить стоимость одной игры для игрока (скажем, она составляет $d$ долларов, независимо от того, выигрывает игрок или проигрывает). Бесплатная ночь обходится казино в $100$ долларов. При каких значениях $d$ казино в среднем будет получать прибыль?

Решение

Состояние системы должно отражать прогресс игрока на пути к цели, то есть количество последовательных выигрышей. Пусть $X_t$ — количество выигрышей после последнего проигрыша (длина текущей выигрышной серии) после $t$-го хода. Так, $X_0=0$. После первого хода $X_1=1$, если был выигрыш, и $X_1=0$, если был проигрыш, и так далее. Возможные значения являются элементами пространства состояний $S=\{0,1,2,3\}$. Состояние $X_t=0$ означает, что игрок только что проиграл, $1$ — что игрок одержал одну победу после проигрыша, и так далее. Когда $X_t=3$, игрок выигрывает бесплатную ночь и прекращает играть. Это можно визуализировать с помощью следующего графа:

Рисунок 1

$\{0, 1, 2\}$ — незамкнутый сообщающийся класс. $\{3\}$ — замкнутый сообщающийся класс, который поглощает цепь с вероятностью $1$, $\mathbb{P}(\tau_3<\infty)=1$.
Пусть $u$ — функция, определённая в условии задачи. Если $x\in A$, то $\tau_A=0$ $\mathbb{P}_x$-п.н., поэтому $u=0$. Рассмотрим случай $x\notin A$. Заметим, что в этом случае \[ \tau_A = \sum_{t=0}^{\tau_A} \mathbf{1}_{X_t \notin A}= \mathbf{1}_{X_0 \notin A} +\sum_{t=1}^{\tau_A} \mathbf{1}_{X_{t} \notin A}=1+\sum_{t=0}^{\tau_A-1} \mathbf{1}_{X_{t+1} \notin A} \] Заметим, что в тонком случае, когда $\mathbb{P}(\tau_A<\infty)<1$, это равенство всё ещё верно, просто обе части уравнения могут быть равны $+\infty$. В частности, они совпадают на событии $\{\tau_A<\infty\}$, то есть на траекториях $\mathbf{X}$, которые в конечном итоге достигают $A$.

Также, для $X_0\notin A$, имеем $\tau_A(\mathbf{X})-1=\tau_A(\mathbf{\theta_1 X})$ (что также верно, когда обе части равны $+\infty$), где $\theta_1$ — оператор сдвига времени. Тогда, обусловливая по первому шагу, для $x\notin A$ имеем \[ \begin{aligned} u(x) & =\mathbb{E}_x[\tau_A \mathbf{1}_{\tau_A<\infty}] = 1+ \sum_y \mathbb{E}_x\left[\sum_{t=0}^{\tau_A-1} \mathbf{1}_{X_{t+1} \mathbf{1}_{\tau_A<\infty} \notin A}|X_1=y\right] \\ & =1+ \sum_y p_{x,y} \mathbb{E}_y\left[\sum_{t=0}^{\tau_A} \mathbf{1}_{X_{t} \mathbf{1}_{\tau_A<\infty} \notin A}\right]= 1+ (Pu)(x) \end{aligned} \]
Нам нужно найти математическое ожидание числа ходов до выигрыша, начиная из состояния $0$. Это в точности величина $u(0)$, где целевое множество — $A=\{3\}$. Нам дано, что $p=1/2$. Система уравнений, представляя $v$ как вектор $(v_0,\ldots,v_3)$, имеет вид: \[ \begin{cases} & \tfrac{1}{2} v_0 = 1+ \tfrac{1}{2} v_1 \\ & v_1= 1+ \tfrac{1}{2} v_0 + \tfrac{1}{2} v_2 \\ & v_2 = 1+ \tfrac{1}{2} v_0 + \tfrac{1}{2} v_3 \\ & v_3=0 \end{cases} \] $v_0=2+v_1$, отсюда $v_1= 4+v_2$, тогда $v_2= 1+1+\tfrac{1}{2}(1+v_1)=4+v_2/2$. А именно, $v_2=8$, $v_1=12$, $v_0=14$. Математическое ожидание числа игр, которые игрок сыграет, чтобы выиграть приз, равно $14$. Следовательно, казино будет получать прибыль в среднем, если $14 d>100$ долларов: плата не менее $\$7.15$ за ход гарантирует положительную среднюю прибыль.

Упражнение 3 Алиса и Боб играют в игру против своего друга Криса. Алиса начинает с капиталом $x_0=100$ долларов, Боб начинает с $y_0=200$ долларов. Начинает Алиса, затем ход Боба, затем снова Алисы, и так далее. Мы предполагаем, что Крис принимает долги от Алисы и Боба, то есть они могут продолжать играть бесконечно, даже если их капитал отрицателен. На каждом ходу, когда они играют, игроки могут либо выиграть, либо проиграть один доллар с вероятностью $1/2$. Пусть $X_t$ ($Y_t$) — количество долларов, которое имеет Алиса (соответственно, Боб) после $t$ ходов. Так, например, $X_0=100$, и $X_1$ может быть либо $101$, либо $99$, $X_2=X_1$, в то время как $Y_0=Y_1=200$, $Y_2$ может быть либо $201$, либо $199$, и так далее. Конечно, $Y_{2t+1}$ и $X_{2t}$ имеют разную чётность, поэтому имеет смысл сравнивать их распределения только после того, как оба игрока сыграли одинаковое количество раз: в моменты времени $2t$ для $t\in \mathbb{N}$.

Докажите, что для $z\in \mathbb{Z}$ \[ |\mathbb{P}(X_{2t}=z)-\mathbb{P}(Y_{2t}=z)| \le q_{2t,y_0-x_0} \] где $q_{t,x}$ — это вероятность того, что случайное блуждание, начавшееся в $x$, достигнет $0$ после момента времени $t$. [Используйте метод coupling, как в доказательстве сходимости для апериодических положительно-возвратных цепей. Будьте осторожны с чётностью $t$.]

Примечание: Напомним, что для больших $t$ и $x\neq 0$ имеем $q_{t,x} \approx |x|/{\sqrt{\pi t}}$ (мы делали это вычисление для $x=0$, что аналогично случаю $|x|=1$), таким образом, мы получаем, что \[ \lim_{t\to \infty} \sup_{z} |\mathbb{P}(X_{2t}=z)-\mathbb{P}(Y_{2t}=z)| =0 \]

Решение

Определим $Z_t=Y_t-X_t$. $Z_t$ — простое симметричное случайное блуждание на $\mathbb{Z}$, начинающееся в точке $y_0-x_0$. Пусть $\tau:= \inf\{t \ge 0 \st X_t=Y_t\}$. $\tau$ — момент остановки (момент первого достижения $0$ для $Z_t$). Определим цепь Маркова $\mathbf{Y}'$ следующим образом \[ \begin{cases} Y_t & \text{если $t\le \tau $ или $t>\tau$ и $t$ нечётно} \\ X_{t-1} & \text{если $t> \tau$ и $t$ чётно} \end{cases} \] Тогда $\mathbf{Y}'$ имеет тот же закон распределения, что и $\mathbf{Y}$ (изменяется на $\pm 1$ в каждый чётный момент времени). Более того, в момент времени $2t$ \[ \mathbb{P}(X_{2t}=z, \tau < 2t)= \mathbb{P}(X_{2t-1}=z, \tau < 2t)= \mathbb{P}(Y'_{2t}=z, \tau < 2t)=\mathbb{P}(Y_{2t}=z, \tau < 2t) \] Следовательно \[ |\mathbb{P}(X_{2t}=z)-\mathbb{P}(Y_{2t}=z)| \le \mathbb{P}(\tau<2t)=q_{2t,y_0-x_0} \]

Сноски

Вы можете предположить, что $\mathbb{P}_x(\tau_A<\infty)=1$ для всех $x\in A$, если хотите упростить обозначения. В этом случае $u(x)=\mathbb{E}_x[\tau_A ]$.↩︎