Proving irreducibility of Markov chain I have a Markov chain:


*

*state: a permutation of n cards

*transition: taking the top-most card and randomly choose one of the n possible positions for the card


I know it is obviously irreducible because we can arrive at any permutation states from any starting permutation states. But I'm wondering how can I express it in mathematical way.
Thanks for any kind of help!

Look at the 'reverse' move, in which you pick a card from within the deck and move it to the top. These reverse moves can get you from starting state $(a_{\pi(1)},\ldots,a_{\pi(n)})$  to final state $(a_1,\ldots,a_n)$  by first locating card $a_n$ and moving it to the top, then locating card $a_{n-1}$ and moving it to the top, and so on, finally moving card $a_1$ to the top.
Now run the video backwards: you've got yourself an algorithm for getting from $(a_1,\ldots,a_n)$ to $(a_{\pi(1)},\ldots,a_{\pi(n)})$ by repeatedly taking the top card and moving it to a position deeper within the deck.
Example: You can get from DBCEA to ABCDE using moves-to-the-top via:
$${\rm DBCEA}\to{\rm EDBCA}\to{\rm DEBCA}\to{\rm CDEBA}\to{\rm BCDEA}\to{\rm ABCDE}$$
Therefore you can get from ABCDE to DBCEA using moves-from-the-top via:
$$
{\rm ABCDE}\to{\rm BCDEA}\to{\rm CDEBA}\to{\rm DEBCA}\to{\rm EDBCA}\to{\rm DBCEA}
$$
