a short understanding question. Consider a pile of $n$ cards. At every step we choose randomly 2 cards and transpose them. Now $X_n$ should be a Markov chain which describes the order of the pile at time $n$.
I think the transition probability is $P(x,y)=1/\binom{n}{2}$ for two adjacent states $x$ and $y$. But I read several solutions which say $P(x,y)=1/n^2$.
Can anybody describe to me whether and why I'm wrong?
Thanks!
Zitrone
It depends on whether the two chosen cards have to be distinct or not. If they have to be distinct, then your answer is correct. If they do not have to be distinct, then the other answer is correct. In any event, when you fix $x$ and consider transition probabilities to all possible $y$, they should sum to $1$.