Consider the following method for shuffling a deck of cards. Pick two cards from the deck uniformly at random and then switch their positions. If the same two cards are chosen, the deck does not change. This is called the random transpositions shuffle.
(b) Exhibit a $6\times 6$ transition matrix for a three-card deck.
I'm confused on how to do this. I have my $6\times 6$ matrix with state space,
$S = \{ABC, ACB, BAC, BCA, CAB, CBA\}$
Can someone give me some advice on how to start filling the transition matrix? E.g., if my order of cards is $ABC$ how do I decide the probability of going to $ABC$>+?
Thank you in advance.
From the second observation about when the deck does not change, I assume that we choose two cards uniformly and independently at random, so that we might end up choosing the same card twice.
In that case, from every state, there are $9$ equally likely possibilities: we can choose to swap the card in position $i \in \{1,2,3\}$ with the card in position $j \in \{1,2,3\}$, for any pair of positions $(i,j)$.
For example, starting from state ABC:
The probability of transitioning from state $x$ to state $y$ is $\frac19$ of the number of pairs $(i,j)$ that produce state $y$ out of state $x$. For example, if $x$ is ABC and $y$ is CBA, then there are two pairs that work: $(1,3)$ and $(3,1)$. So we transition from ABC to CBA with probability $\frac29$.