wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Bogosort
        
(Message started by: ThudnBlunder on May 30^th, 2011, 6:53am)

Title: Bogosort
Post by ThudnBlunder on May 30^th, 2011, 6:53am

A normal pack of 52 playing cards is to be sorted into a particular order using Bogosort (http://en.wikipedia.org/wiki/Bogosort). Let S(n) be the probability that Bogosort correctly sorts the deck in n shuffles or less. Seeing as S(n) is a monotonically increasing function which converges to 1, derive an estimate for the smallest value of n for which S(n) exceeds 0.95, say.

Title: Re: Bogosort
Post by towr on May 30^th, 2011, 9:18am

[hide]I'd say n is about 3*52!
because n=52! should give about 1/e probability that it's not been sorted yet.[/hide]

Title: Re: Bogosort
Post by Grimbal on May 30^th, 2011, 9:55am

To be precise, [hide] replace 3 by ln(0.05)/ln(1/e) = 2.9957.
You get n = 2.4163E+68.

Uh... subtract one if you check the order already before the first shuffle. ;)[/hide]

Title: Re: Bogosort
Post by towr on May 30^th, 2011, 10:40am

The approximation is already [hide]290525338444092531665930133786805491212286891737748022440[/hide]* off, so I wouldn't worry about that extra 1 too much.

* which isn't too bad on a number like [hide]241630298485567771500540396514677414298531351035230182511744601484973[/hide]; it's accurate to about 1 in 10¹²

Title: Re: Bogosort
Post by Grimbal on May 31^st, 2011, 1:57am

Yeah.... That's why I added a ";)".

Title: Re: Bogosort
Post by ThudnBlunder on May 31^st, 2011, 2:48am

Of course, many readers will not understand why your smart asswers are correct (1/e?) and hate maths even more. ::)

Title: Re: Bogosort
Post by towr on May 31^st, 2011, 9:07am

If it makes them resentful rather than curious, then, frankly, they're already beyond help. ::)

But if they are curious, then they'd probably be best helped by asking about any parts they don't understand, in as far as the following doesn't cover it.
[hide]There are 52! possible permutations of the cards, and only one gives the right order. So with each reshuffle there is a probability of (52!-1)/52! that the cards are still out of order. Since the shuffles are independent, we can multiply them together, which gives us a probability of [(52!-1)/52!]ⁿ that after n shuffles the deck has never once been in the right order.
At this point it's helpful to know that if we consider ([k-1]/k)^k, then as k grows it's value comes ever closer to 1/e (~= 0.36787944). Because 52! is a very large number, for all practical purposes we can assume that [(52!-1)/52!]^52! equals 1/e. This simplifies things, because now we just need to solve 1/e^r = 0.05, which gives r = ln(0.05)/ln(1/e) = -ln(0.05) ~= 2.9957 and so we can say n~=2.9957*52![/hide]