10001110100110101
GY told me about this interesting puzzle that took me a long time to figure out some sort of incomplete solution to.
Basically, here is the scenario:
Someone wrote a program to shuffle a deck of cards by taking the first card, and randomly inserting that card back into the deck. This also includes itself! It would then go to the next card, and then randomly insert that card into the deck. This will continue down to the end of the deck.
Will this algorithm properly randomize the deck? Please explain why or why not.
Does anyone have a quick answer?
Whoops! I explained it incorrectly! It is not a simple insert, but a swap!
Someone wrote a program to shuffle a deck of cards by taking the first card, and randomly SWAPPING that card with any card in the deck. This also includes itself! It would then go to the next card which will then be randomly swapped with any card in the deck. This will continue down to the end of the deck.
Will this algorithm properly randomize the deck? Please explain why or why not.
Forgiviness please!
Monday, July 21, 2008 at 19:17:31 (UTC)
Highlight to view my response:
Assuming that by "continue down to the end of the deck" means that only 52 inserts take place, this will not be very random at all. Cards in the latter half (or so) will often not get shuffled at all -- most of the actual shuffling will occur in the first half.
As such, you'll tend to get the latter half (or third or some chunk which I'm guessing to be about half) in order, with a few lower numbered cards inserted between them.
Hwan
Monday, July 21, 2008 at 20:00:34 (UTC)
A lot of this depends on what "continue down to the end of the deck" means.
Think of it this way: you've got a deck or cards represented by an array we'll call cards[]. (Actually, you'd use a linked list, but array notation makes my life easier). The description says you're getting a random number n, removing cards[0] from the list and inserting its value at cards[n]. But when do you stop? You'll always have cards[0].
Hwan assumes that you'd stop after 52 iterations, and he's right, that would suck.
If you kept iterating until cards[51] (ie., the last card) was inserted, then it seems good to me. You'd just have to keep track of what cards[51] was.
Why you'd do this instead of some other well-known shuffling algorithm, though, is beyond me.
Darcy
Tuesday, July 22, 2008 at 03:57:10 (UTC)
Ah ha! Well that IS quite the difference!
I'm pretty sure this is sufficiently random and thus a good shuffling technique. Unlike the insert scenario described above, each card is guaranteed to be considered to be moved to a random position at least once. So that's a very good start.
I'm too lazy to figure out a way to devise if this will give a uniform random distribution (though I have tried), but my gut says it will.
I found the first, mistaken scenario more interesting, at least from a "What's wrong here?" perspective.
Hwan
Friday, July 25, 2008 at 14:20:00 (UTC)
I was wrong. Do a three card sample to quickly see why.
Hwan
Friday, July 25, 2008 at 23:23:09 (UTC)
Correct! Now can you come up with a solution?
QYV
Monday, July 28, 2008 at 17:09:37 (UTC)
I don't have a solution, but I have an interesting pattern to share.
I ended up showing this problem to a couple of friends, and one of them built a little JS app to work out the distributions. It turns out that the ratio of the least likely shuffle order and the most likely shuffle order follows a near-Fibonnaci ratio (eg. 1,1,2,3,5,8 etc), suggesting that with 52 cards the ratio will be around 20 billion -- not very evenly distributed at all!
My friend started with the conjecture that this shuffle algorithm should give NxN shuffle outcomes, whereas a deck should have N! possibilities. The question then becomes one of whether the limited distributions are equal, which we can see that it is evident that they are not.
But why this is I'm not sure.
Hwan
Wednesday, July 30, 2008 at 21:04:20 (UTC)
I think you meant N^N instead of NxN.
There are N^N possible outcomes that have equal probability. However, there are only N! possible card combinations. So by just seeing that N^N is not divisible by N! indicates that there is no way to evenly distribute the N^N outcomes over the N! combinations. Thus there will be a bias.
QYV
Thursday, July 31, 2008 at 18:12:00 (UTC)
Hmm yes quite right sir.
Hwan