expected number of shuffles to sort the cards

Question

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.

Answer 1

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

Answer 2

Some thoughts: there will be a recurrence. The idea is to find the expected time to reduce the number of cards in the deck, then to find the probability that if you reduce it, what is the chance that you reduce it by 1, 2, ... First the probability that at least one of the ends is in proper position is 2/n, as I claim the fact that the top card is not right doesn't change the chance that the bottom card is right-there is 1/n chance that the top card should be on the bottom, then of the 1-1/n=(n-1)/n chance it isn't there is 1/(n-1) chance the right one is on the bottom. So the expected time to reduction is n/2. Then sort out $P_k(n)$, the probability that if there is a reduction it is exactly k. By the previous argument, $P_1(n)=\frac{n-3}{n-1}$ Then, as in the coupon collector problem you have N(n) (the number of shuffles of n cards)=n/2(probability of reduction of 1 given that there is a reduction)*N(n-1)+probability of reduction of 2 given that there is a reduction)*N(n-2)+...)

Added: 2 is special because if one card is right, so is the other. This chance is 1/2 and you are done. So the expected number of shuffles is 2. For 3, you have 1/3 chance of nothing correct, 1/6 chance of all correct, and 1/2 chance of 1 correct. So N(3)=(1/3)(N(3)+1)+(1/2)(N(2)+1)+(1/6)(N(0)+1) As you know N(2)=2 and N(0)=0 you can solve for N(3)

Answer 3

One gets the recurrence as follows. Let $N(n)$ denote the mean number of shuffles needed to sort a deck of $n$ cards and $p_n(k)$ the probability to fix exactly $k$ cards by shuffling once a deck of $n$ cards. Then $N(1)=0$ (the deck is already ordered) and, for every $n\ge2$, $$ N(n)=1+\sum_{k=0}^{n-2}p_n(k)N(n-k). $$ Let $T_n$ and $B_n$ denote the random numbers of cards fixed at the top and at the bottom of the deck by one shuffle, thus $$ p_n(k)=P(T_n+B_n=k). $$ The event $[T_n\ge i,B_n\ge j]$ corresponds to the fact that $i+j$ cards have their position imposed and the remaining $n-i-j$ cards are shuffled freely. Hence $$ P(T_n\ge i,B_n\ge j)=(n-k)!/n!=r_n(n-k) $$ for every $(i,j)$ such that $i+j=k$. Now $[T_n=i,B_n=j]$ is $$ [T_n\ge i,B_n\ge j]-[T_n\ge i+1,B_n\ge j]-[T_n\ge i,B_n\ge j+1]+[T_n\ge i+1,B_n\ge j+1], $$ hence $$ P(T_n=i,B_n=j)=r_n(n-k)-2r_n(n-k-1)+r_n(n-k-2). $$ Since $p_n(k)$ is $(k+1)$ times this, one gets $$ N(n)=1+\sum_{k=0}^{n-2}(k+1)(r_n(n-k)-2r_n(n-k-1)+r_n(n-k-2))N(n-k), $$ that is, $$ n!N(n)=n!+\sum_{k=2}^{n}(n-k+1)\left(k!-2(k-1)!+(k-2)!\right)N(k). $$ The rest should be a story of generating functions techniques, as explained here.