1

Consider the set of permutations (i.e. of a deck of cards). We can move from one permutation to another, by swapping two different cards in the permutation. let's assume $\mu$ is uniform distribution on those transpositions. Is $P_\mu$, the Markov Chain aperiodic? irreducible?

  • irreducible: Yes, It is easy to see that we can reach any permutation from any start point and therefore $P_\mu$ is strongly connected.
  • aperiodic: Yes, since after one transposition we can go back to the original one, so there are paths from any state to itself of any length.

I wish to know if I'm right and if my explanation is rigorous enough.

Thanks

Covvar
  • 257

1 Answers1

1

Irreducibility - correct explaination

BUT its period is $2$.

check that it always requires an even number of steps to returnto the original position.

Qwerty
  • 6,165
  • How can it be explained? I tried to use the fact that the hamming distance always changes by $2$. – Covvar Jun 05 '17 at 21:35