1 Simple card shuffling

Consider again the a Markov chain corresponding to the card shuffling procedure given at the end of the previous homework.
Consider the case \(n=4\), so that there are four cards labeled: \(1,2,3,4\).

2 Transition matrices

Let \(P\) be a transition matrix. Show that if \(P^n\) has all positive entries for some \(n\), then \(P^m\) has positive entries for all \(m \geq n\).

3 A Markov chain

Consider the Markov chain on five states \(\{1,2,3,4,5\}\) started at \(1\) with transition matrix given by

P <- matrix(c(1/4, 1/4, 1/2, 0,0, 
              1/4, 1/4,0,0,1/2, 
              1/4,0,0, 1/2, 1/4, 
              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.2500000 0.2500000  0.5  0.0 0.0000000
## [2,] 0.2500000 0.2500000  0.0  0.0 0.5000000
## [3,] 0.2500000 0.0000000  0.0  0.5 0.2500000
## [4,] 0.0000000 0.0000000  0.0  0.5 0.5000000
## [5,] 0.3333333 0.3333333  0.0  0.0 0.3333333

4 Gibbs sampler (Baby Markov chain Monte Carlo)

Often in Bayesian statistics one needs to able to sample from the joint density \(j\) of two random variables \((W,Z)\) but only has access to their conditional densities \(f(w|z)\) and \(g(z|w)\). One then considers the Markov chain defined in the following way. We start with an initial value \(X_0 = x_0\) and pretend that we have sampled from \(W\). Now we define \(Y_0=y_0\) to be a random variable with density \(g(\cdot|w)\) which we can simulate in R. Next, we simulate \(X_1\) using the density \(f(\cdot|y_0)\), and repeat. We obtain a Markov chain of pairs

\[ \Bigg( (X_0, Y_0), (X_1, Y_1), \ldots, (X_n, Y_n) \Bigg).\] A stationary distribution is \(j\), and we hope that when \(n\) is large \((X_n, Y_n)\) has a joint distribution that is close to \(j\).

In what follows we will play with a toy example. Suppose \(W\) and \(Z\) are given in the following way: we flip a fair coin \(W\), and if we get a heads, we flip a fair coin for \(Z\), otherwise, we flip a \(1/4\) coin for \(Z\).

5 Endnotes