Midterm Classwork: Examples

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

Exercises

Exercise 1 I have $3$ umbrellas, and each of them may be at home or at the office. Each time I go from home to office, or from the office to home, I take an umbrella with me iff it rains. However, if there are no umbrellas available and it rains, I get wet. The probability that it rains during a given trip office/home or home/office is $p$. Find the probability that I get wet on a given trip.

Solution

The time $t$ here represents the number of places (office/home) visited. We let $X_t$ be the number of umbrellas that are in the place where I am. This is a Markov chain with state space $S=\{0,1,2,3\}$. If $x=0$, then $p_{0,3}=1$, since once I change place, all the umbrellas will be at the new place. $p_{1,3}=p$ (since I will bring with me the only available umbrella iff it rains), $p_{1,2}=1-p$; and similarly $p_{2,2}=p=1-p_{2,1}$; finally $p_{3,1}=p=1-p_{3,0}$. In other words, for $x\ge 1$, $p_{x,y}=p$ if $y=4-x$ (since I will bring the umbrella with me), and $p_{x,y}=1-p$ if $y=3-x$.

The transition probabilities matrix is then \[ P = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1-p & p \\ 0 & 1-p & p & 0 \\ 1-p & p & 0 & 0 \end{pmatrix} \]

Figure 1

This is an irreducible Markov chain, with unique invariant probability. It is easy to see that $m_3=m_2=m_1$. So using $mP=m$ we get $m=(\tfrac{1-p}{4-p},\tfrac{1}{4-p},\tfrac{1}{4-p},\tfrac{1}{4-p})$. The probability that I get wet is then $m_0 p = \tfrac{p(1-p)}{4-p}$.

This probability is maximized for $p = 2(2-\sqrt{3}) \approx 0.54$, aka Moscow weather. Notice also that, if I get $N$ umbrellas, the probability of getting wet just becomes $p(1-p)/(N+1-p) \le 1/(4N)$.

Exercise 2 Damocles was a courtier at the court of the tyrant Dionysius of Syracuse. Dionysius gives him a task to complete every now and then and, depending on the outcome, the consideration the tyrant has for Damocles changes. However over time there are only two possible outcomes:

Damocles becomes a favorite at the court and given a high title. This earns him $a$ drachmas.
Damocles is banished and deprived of anything he has, worth $b$ drachmas.

We can model the reputation of Damocles as a finite state homogeneous Markov chain, which sooner or later will hit either the set $A$ (achieving the high title) or $B$ (banishment). E.g. we can think the reputation is an integer numerical value $x$, ranging from $0$ (banishment) to $100$ (high title).

Assuming we know the transition probabilities, write a linear problem to determine the expected amount of drachmas earned by Damocles when starting his service with a given reputation $x\in S$.

At some point, Dionysius famously hangs a sword on the head of Damocles, held by a single horsehair. Before he completes each task, the sword has a probability $p>0$ of falling on the head of Damocles (killing him).

Write a linear problem to determine the expected amount of drachmas earned by Damocles when starting his service with a given reputation $x\in S$, with the sword hanging on his head.

Solution

Let $\tau$ be the first time when Damocles reputation is decided (meaning he gets a high title or is banished). Conditioning on the first step, the function $h(x)= \mathbb{E}[a \mathbf{1}_{X_{\tau}\in A}- b\mathbf{1}_{X_{\tau}\in B} ]$ solves \[ \begin{aligned} & (I-P)h= 0 \qquad \text{on $(A\cup B)^c$} \\ & h=a \qquad \text{on $A$} \\ & h=-b \qquad \text{on $B$} \end{aligned} \]

If we add the Damocles’ sword, for instance we can think that we add an extra point $\xi$ to the state space, say $S'=S \cup \{\xi\}$. If $(p_{x,y})$ are the original transition probabilities, the new Markov chain has transition probabilities given by \[ \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} \] We have the same formula for $h$, just $\tau$ is now the first time where the chain hits $A\cup B \cup \{\xi\}$. $h(x)$ now satisfies, for $x\in S \setminus (A\cup B)$, $h(x)= \sum_{y\in S} q_{x,y} h(y)+0 q_{x,\xi}$. Namely, again as an equation on $S$ ($\xi$ was just auxiliary): \[ \begin{aligned} & (I-(1-p)P)h= 0 \qquad \text{on $(A\cup B)^c$} \\ & h=a \qquad \text{on $A$} \\ & h=-b \qquad \text{on $B$} \end{aligned} \]

Exercise 3 For a homogeneous Markov Chain, explain why each point in a non-closed communicating class $C$ is transient.

Solution

Since $C$ is not closed, there is $y\in C$, $z\not \in C$ such that $p_{y,z}>0$. But $x \leftrightarrow y$ and $z \not \rightarrow x$. Let $t$ be the smallest time such that $p^{(t)}_{x,y}>0$. Then $q:=p^{(t+1)}_{x,z}\ge p^{(t)}_{x,y} p_{y,z}>0$. Then each time the chain touches $x$, it has probability at least $q>0$ to never return. Thus it will only return finitely many times.

Exercise 4 An irreducible Markov chain on $\mathbb{N}$ has the following feature. For each $x\in S$, $p_{x,0}\ge p$ for some $p>0$.

Prove that $\mathbb{E}_x[\tau_x^+]<\infty$.
Deduce (using known results) that there exists a unique invariant probability $m$.
Estimate \[ \sup_x | \mathbb{P}_y(X_t=x) - m_x| \le ? \]

Solution

Fix $x$. By irreducibility, for some $t$, we have $p^{(t)}_{0,x}>0$. Thus at every step we have probability at least $p$ of jumping to $0$ in one step, and then going back to $x$ in $t$ steps: \[ \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_x > 0 \\ & \mathbb{P}_x(\tau_x^+ \ge k(t+1)) \le (1- q_x)^k \end{aligned} \] and therefore its expectation is finite.
Every irreducible, positive-recurrent Markov chain admits a unique invariant probability $m$.
Let $Y_t$ be an independent chain, started with initial distribution $m$. Let $\tau$ be the first time where $X_t=Y_t$. We have that \[ | \mathbb{P}_y(X_t=x) - m_x| \le \mathbb{P}(\tau > t) \le (1-p^2)^t \] With more care, we can construct a coupling $(X_t, Y_t)$ where both chains jump to $0$ simultaneously with probability $p$ at each step. To achieve this, we flip a coin with probability $p$ of landing on heads. If it lands on heads, both $X_t$ and $Y_t$ move to $0$. If it lands on tails, they proceed independently with modified transition probabilities (specifically, from state $x$, the chain jumps to $0$ with probability $(p_{x,0}-p)/(1-p)$). This construction yields the improved bound $(1-p)^t$.