Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a standard deck of 52 cards which you would like to sort in a particular order. The notorious algorithm Bogosort works like this:

  1. Shuffle the deck
  2. Check if the deck is sorted. If it's not sorted, goto 1. If it's sorted, you're done.

Let B(n) be the probability that Bogosort sorts the deck in n shuffles or less. B(n) is a monotonically increasing function which converges toward 1. What is the smallest value of n for which B(n) exceeds, say, 0.9?

If the question is computationally infeasible then feel free to reduce the number of cards in the deck.

share|improve this question
add comment

1 Answer

up vote 10 down vote accepted

An estimate. The probability that Bogosort doesn't sort the deck in a particular shuffle is $1 - \frac{1}{52!}$, hence $1 - B(n) = \left( 1 - \frac{1}{52}! \right)^n$. Since

$$\left( 1 - \frac{x}{n} \right)^n \approx e^{-x}$$

for large $n$, the above is is approximately equal to $e^{- \frac{n}{52!} }$, hence $B(n) \approx 0.9$ when

$$- \frac{n}{52!} \approx \log 0.1 \approx -2.30.$$

This gives

$$n \approx 2.30 \cdot 52! \approx 2.30 \cdot \sqrt{106\pi} \left( \frac{52}{e} \right)^{52} \approx 1.87 \times 10^{68}$$

by Stirling's approximation. By comparison, the current age of the universe is about $4.33 \times 10^{17}$ seconds, or about $4.33 \times 10^{32}$ flops if your computer runs at $1$ petaflops.

share|improve this answer
2  
Better go put the kettle on while I wait for this deck to get sorted then.. –  Sputnik Jun 4 '11 at 21:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.