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} $$