1 Gambler’s ruin

Recall the Gambler’s ruin problem from the last session. Suppose someone plays the following gambling game. They bet \(1\) pound on a fair flip of a coin and win \(1\) pound if it comes up heads, and lose if come up tails. They start with \(1\) pound, and stop playing once they have reached \(5\) pounds or have no money left. Express this problem up as a Markov chain. In particular:

Specify the state space and transition matrix.
Take high powers of the transition matrix in R; comment on what you see.

2 Anything is possible

Consider the transition matrix \(P\) on the states \(\{1,2,3,4\}\) given by:

P <- matrix(c(0, 1/2, 1/2, 0, 0, 1/2, 0,0,0,1/2, 1/2,0,0, 1/2, 0, 0,0,0,1/2, 1/2, 1/3, 1/3, 0, 0, 1/3), nrow =5)
P <-t(P)
P

##           [,1]      [,2] [,3] [,4]      [,5]
## [1,] 0.0000000 0.5000000  0.5  0.0 0.0000000
## [2,] 0.5000000 0.0000000  0.0  0.0 0.5000000
## [3,] 0.5000000 0.0000000  0.0  0.5 0.0000000
## [4,] 0.0000000 0.0000000  0.0  0.5 0.5000000
## [5,] 0.3333333 0.3333333  0.0  0.0 0.3333333

Compute powers of \(P\) until you see that all the entries are positive.
What does it mean if all the entries are positive?

3 Convex combinations

Let \(\lambda\) and \(\mu\) be probability measures on \(\Omega\) with events \(\mathcal{F}\).

Recall that \(\lambda\) is a probability measure if

\(\lambda(\Omega) =1\)
\(\lambda(A ) \in [0,1]\) for all events \(A \in \mathcal{F}\)
\(\lambda( \bigcup_{i=1} ^{\infty} A_i) = \sum_{i=1}^{\infty} \lambda(A_i)\) for any countable number of pairwise disjoint events \(A_1, A_2, \ldots\).

Show that \[\rho = (1-t)\lambda + t \mu\] is a probability measure on \(\Omega\) for all \(t \in [0,1]\).

Let \(P\) be a transition matrix on a state space \(S\). Show that if \(\lambda\) and \(\mu\) are stationary measures of \(P\), then any convex combination of \(\lambda\) and \(\mu\) is a stationary measure for \(P\).
Consider the transition matrix on four states given by \[ \left( \begin{array}{cccc} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/3 & 2/3 \\ 0 & 0 & 1/2 & 1/2 \\ \end{array} \right) \]
Find three stationary measures for \(P\).
Does \(P\) have finitely many stationary measures?

4 Periodicity

Consider the transition matrix \(P\) on the states \(\{1,2,3\}\) given by:

P <- matrix( c( 0,0,1,0, 0,0,0,1, 1/2,1/2,0,0, 1,0,0,0), nrow =4)
P <- t(P)
P

##      [,1] [,2] [,3] [,4]
## [1,]  0.0  0.0    1    0
## [2,]  0.0  0.0    0    1
## [3,]  0.5  0.5    0    0
## [4,]  1.0  0.0    0    0

Take powers of \(P\), what do you observe?
Does \(P\) have any stationary distributions? Explain.
Consider the transition matrix \(Q = P^2\). Does \(Q\) have any stationary distributions. Explain.

5 Maximal coupling

Let \(X\) and \(Y\) be discrete random variables taking values on the space \(S\), with probability mass functions \(p\) and \(q\). Show that there exists a coupling of \((X', Y')\) of \(X\) and \(Y\) such that \[d_{TV}(X, Y) = d_{TV}(X', Y') = 2 \mathbb{P}(X' \not = Y'),\]

so that equality is obtained in the usual coupling inequality.

Hint: consider a joint distribution for \(X'\) and \(Y'\), where maximize the probability that \(X'=Y'\) and you spread out the rest of the remaining probability as equally as possible.

6 A triangle inequality

Let \(X_1, \ldots, X_n\) be independent integer-valued random variables. Also let \(Y_1, \ldots, Y_n\) be independent integer-valued random variables. Set \(S=X_1 + \cdots + X_n\) and \(W = Y_1 + \cdots + Y_n\). Show that

\[d_{TV}(S, W) \leq \sum_{i=1}^n d_{TV}(X_i, Y_i).\]

Hint: Use a maximal coupling, along with independence.

7 Endnotes

Version: 20 October 2021
Rmd Source