If you shuffle n cards as follows: Go through the deck one card at a time and at each card, flip a fair coin. If the coin comes up head, then leave the card where it is, and if it comes up tails move that card to the end of the deck. For example, if n =4, and the initial ordering is 1,2,3,4, and outcome of the successive flips is h,t,t,h, then the ordering at the end of the round is 1,4,2,3. Assuming all possible outcomes of the coin flips are equally likely, what is the probability that the ordering after one round is the same as the initial ordering?
Attempt:
If the ordering after n flips is the same as the initial ordering, then you would have to roll all heads since rolling heads doesn't change the ordering. So the answer would be (1/2)^n?
Best Answer
To see what head-tail-sequences give the identity permutation, see that if you obtain one head, you leave the corresponding card to its place, and the described process continues only for the following cards. What you're doing is applying to the array $[1,\dots,n]$ the permutation $(n\ n\!-\!1 \ \cdots\ 2\ 1)$ as long as you're obtaining tails; after one head you continue applying to you're vector the permutation $(n\ n\!-\!1 \ \cdots\ 3\ 2)$, and after $m$ heads the permutation $(n\ n\!-\!1 \ \cdots\ m\!+\!2\ m\!+\!1)$. Than all sequences beginning with all heads and, at some poing, starting and continuing with all tails give the identity, for example
To see that no other head-tail-sequence gives the identity, assume you're on the card $7$ (lucky number!), if you obtain a tail you put that number to the end, and now you move on number $8$, and if you obtain head you leave it there and pass over... than your final string will have the $8$ occurring before the $7$!! In general, having a head after a tail, do not preserve the ordering. So the probability to end the process with the same string is $(n+1)/2^n$ where $n+1$ is the number of the strings (described above) of the form all-heads followed by all-tails.
PS I have to point out that by $(n\ n\!-\!1 \ \cdots\ 2\ 1)$ I'm referring to the positions, I mean $n$ in that notation mean the $n$th card in the cards-array, and not the actual card of value $n$.