Initially the deck is randomly ordered. The aim is to sort the deck in order. Now in each turn the deck is shuffled randomly. If any of the initial or last cards are in sorted order then they are kept aside, and the process is followed with rest of the cards. The question now is what is the expected number of shuffles for the entire deck to get sorted in this manner.
e.g. let's say initially the deck is $(3,5,6,2,7,1,4)$. After the first shuffle it becomes $(1,2,6,4,5,3,7)$, then the next shuffle will be done with $(6,4,5,3)$ as $(1,2)$ and $(7)$ are already in proper order. Check that even if $5$ in also at right place, but not in continuous order hence considered for shuffle.
What I know is that the expected number of shuffles to sort the deck in one attempt is $n!$. (Something known as bogo-sort). But can't think any further. Any help will be appreciated.
Probability – Expected Number of Shuffles to Sort Cards
permutationsprobabilitysorting
Best Answer
Let $r$ denote the number of cards that, after shuffling $n$ cards, remain unsorted (the middle portion of the deck, that is to be suffled again).
Let $t_n$ be the needed number or shuffles starting from $n$ cards till all cards are sorted. We want $E(t_n)$
Now, lets consider that expectation conditioned on the value of $r_n$, i.e. suppose we know exactly how many cards remain unsorted after the first try:
Then we can write: $E[t_n | r_n=r] = 1 + E[t_r]$
(note that this includes the extreme cases $r_n=0$ and $r_n = n$)
Applying the property $E[E[x|y]] = E[x]$ we have:
$\displaystyle E[t_n] = \sum_{r=0}^n (1 + E[t_r]) \; p(n,r) $
where $p(n,r) = Prob(r_n = r)$ (we'll compute it later)
We must take out the term $r=n$ for the sum, and by trivial manipulation we get the desired recursion:
$\displaystyle E[t_n] = \frac{1}{1-p(n,n)} \left( p(n,n) + \sum_{r=0}^{n-1} (1 + E[t_r]) \; p(n,r) \right) $
As initial values we have $E[t_0] = E[t_1] = 0$
To compute $p(n,r)$ (probability that after one shuffling of $n$ cards there remains -with the rules of our game- exactly $r$ cards to shuffle again) it's more simple (but more tedious), just combinatorial counting - i'll explain if you ask to.
My result is
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
if $r>1$. Elsewhere, $p(n,0) = 1/n!$ and $p(n,1)=0$.
Here are some values (in javascript) http://hjg.com.ar/varios/mat/cards.html
BTW: This problem can be seen as in between two problems, one simpler and one more complex/general: As compared to the Coupon Collector problem, this is more complicated, because we can't divide the road into "states" that will be visited sequentially - and hence we can simply express the desired expectation as a sum of expectations of those pieces. It can be consisdered as a Markov Model with one absorbing state; but the markovian formulation, though apt, is too general, and the desired result (expected numbers of iterations to reach the absorbing state) is less straigforward that the solution proposed here. That's because our problem has some special restrictions (in terms of a Markov chain, we'd say that its transition matrix is triangular)
ADDED: To compute $p(n,r)$ , for $r \ge 2$ : After shuffling $n$ cards, we get $r$ unsorted cards, say $(n1;r;n2)$ Lets count how many ways (with $n1$ $n2$ fixed) there are. They correspond to choose a permutation of the $r$ middle cards, with the condition that both extremes are "wrong". This is given by:
$r! - 2(r - 1)! + (r-2)! = (r^2 - 3 r + 3) (r-2)!$
(This is exclusion-inclusion counting: the first term counts all possibilities, the second count the cases where the first OR the last is right, the third count the cases where the first AND the last are right).
But, for a given $r$ there are several choices of $(n1;n2)$, they are only required to sum up $n-r$. Actually, there are $n - r +1$ alternatives. Then we get the total number of permutations that give $r$ unsorted cards, and divide over all the permutations:
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
UPDATED: An asymptotic can be guessed (theoretically and empirically):
$\displaystyle E(t_n) \approx \frac{n(n-1)}{4} \approx \frac{n^2}{4}$