Incremental Random Sort

A deck of cards numbered from $1$ to $n$ is shuffled randomly such that each permutation is equally likely.

The cards are to be sorted into ascending order using the following technique:

Look at the initial sequence of cards. If it is already sorted, then there is no need for further action. Otherwise, if any subsequences of cards happen to be in the correct place relative to one another (ascending with no gaps), then those subsequences are fixed by attaching the cards together. For example, with $7$ cards initially in the order 4123756, the cards labelled 1, 2 and 3 would be attached together, as would 5 and 6.

The cards are ‘shuffled’ by being thrown into the air, but note that any correctly sequenced cards remain attached, so their orders are maintained. The cards (or bundles of attached cards) are then picked up randomly. You should assume that this randomisation is unbiased, despite the fact that some cards are single, and others are grouped together.

Repeat steps 1 and 2 until the cards are sorted.

Let $S(n)$ be the expected number of shuffles needed to sort the cards. Since the order is checked before the first shuffle, $S(1) = 0$. You are given that $S(2) = 1$, and $S(5) = 4213/871$.

Find $S(52)$, and give your answer rounded to $8$ decimal places.

To solve this tricky problem, we need to use some advanced techniques in mathematics, particularly those pertaining to combinatorics and probability.

The expected shuffling E[n] for a deck of n cards can be calculated using the recursive equation,

E[n] = 1 + Σ { i * P_i * E[n-i] }, with Σ P_i = 1,

where P_i is the probability that the longest properly sequenced subsequence contains precisely i cards.

Starting from the given values S[1]=0 and S[2]=1,

S[3] = 1 + 1/6 * S[2] + 1/2 * S[1] + 1/3 * S[0]

= 1 + 1/6 * 1 + 1/2 * 0 + 1/3 * 0 = 1 + 1/6 = 1.16666667.

Continuing this method up to S[52] is quite complicated and inefficient by hand calculations. It is more practical to use a computer program to iterate through this formula until we reach S[52]. This is due to the recursive nature of the sequence, and the fact that finding the exact probabilities for the longest properly sequenced subsequence P_i for larger n is nontrivial.

Here it is important to note that although we are required to give an answer up to 8 decimal places, any method that involves rounding at the intermediate steps could potentially introduce errors that would affect the 8th decimal place.

However, if you insist to do it by hand, you need to follow these steps:
1. Determine P_i for each i from 1 to n.
2. Use the recursive formula to calculate E[n].
3. Repeat for increasing values of n until you reach 52.

S[52], rounded to 8 decimal places, is computationally complex to be done by hand, and it requires a program to run this sequence.

More Answers: