Card Shuffling

Suppose you have a deck of 4 cards. Let X0 denote the original ordering of the cards and be 1, 2, 3, 4. Suppose I shuffle the cards in the following way. I pick a pair of positions (i, j) {1, 2, 3, 4} uniformly randomly among the (24) possible pairs of positions and I swap the cards at those positions. For example, if the ordering of the cards is 2, 3, 1, 4 at any particular stage and I choose the 1, 2 th pair of positions then the next ordering of the cards would be 3, 2, 1, 4. Let X_n denote the ordering of the cards after I shuffle the cards n times.

(a) Show that X₀, X₁, . . . is a Markov Chain and write down the state space.

(b) Which states are transient if any and which states are recurrent if any?

(c)What is the period of any given state?

*Hint: This will follow from a (rather nice) fact about orderings or permutations. You cannot get back a permutation or ordering from an odd number of swaps. For example, if you start with the ordering 1234 you cannot make an odd number of swaps and get back to this ordering.

(d)Write down the transition matrix Q.

*Hint: Just writing one row is sufficient. You can say the other rows follow a similar pattern.

(e) What happens to the n step transition matrix Qⁿ? Calculate it on a computer and then interpret what this possibly means.

*Hint: This will require coding. You can first when the number of cards is 3 so the state space is small. You can then make an educated guess when the number of cards is 4 and extrapolate it to 52.