1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

Irreducibility - correct explaination

BUT its period is $2$.

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

$\endgroup$
1
  • $\begingroup$ How can it be explained? I tried to use the fact that the hamming distance always changes by $2$. $\endgroup$
    – Covvar
    Commented Jun 5, 2017 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .