Talk:Shuffling
From Wikipedia, the free encyclopedia
Do not delete this page because someone will say "This isn't an encyclopedia article", as it is useful. -- 67.20.29.3 22:03, 2 Apr 2004 (UTC)
I discovered (I'm sure I'm not the first) a constant time variation on the so-called Knuth shuffle. It is a specialized use, but I think it worth mentioning. This assumes a pre-existing permutation (which may or may not be sorted). Whatever card (or element or whatever) you are currently on, swap that card with itself or any card remaining. It is not necessary to apply the swaps to cards which have not been drawn. If one is starting a new game, it is NOT necessary to shuffle remaining cards.
Somebody who has a copy of Knuth handy should put his references in for who he got the "Knuth Shuffle" from. While it has his name attached, I distinctly recall that he cites other sources for it. I invented it independently :-) well before I knew about Knuth, so I imagine it has been invented a million times previously...
I submit'd the link on the main shuffle page for http://crystalpoker.net/securityreview.php I looked on the net for several hours trying to find a good article on shuffling algorithsm for real world scenarios. all the articles linked in external links didn't even give me any practical good data. so i figured that putting the link would be worth it to help others. so thats' why i put it on the page
And That article will probably be in print in dr.doobs and a few other tech magazines in a few weeks too i bet. Just checked the site, they just put the article up a few days ago.
Contents |
[edit] Fisher and Yates
The "Knuth shuffle" is something I've previously encountered as the Fisher-Yates shuffle, e.g. see [1], [2], [3]. The first of those links cites "R. A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938.", which obviously predates any algorithms invented by Knuth. I've added a mention of the name Fisher-Yates shuffle. Graue 01:02, 29 May 2005 (UTC)
[edit] imperfect shuffling
"concluding that it did not start to become random until five good riffle shuffles, and was truly random after seven. (You would need more shuffles if your shuffling technique is poor, of course.)"
In particular, I'd like to refer to the quoted sentence in brackets. It's quite untrue. In fact, the number seven in shuffling refers more to "perfect shuffles" than anything else. Imperfect shuffling, that is, when cards from each shuffling pile do not perfectly intertwine, produce more random results, if anything. While perfect, or close to perfect, shuffling produces predictable results, imperfect shuffing does not. So I think the bracket should be simply deleted from the article, since it's mathematically incorrect.
-- anonymous
I think it is true. Let's myopically focus on the card at the very top of the deck (say it's the ace of hearts). If the deck is "truly random", then there should be an equal probability that the AoH is in any location, right?
Let's say I always grab the top of the deck with my left hand, and then grab the bottom of the deck with my right hand. Say I always flip through the half-deck in my right hand faster than the half-deck in my left hand (poor riffle shuffling technique). Then once I've used up all the cards in my right hand, all the remaining cards in my left hand get thrown on top of the stack.
No matter how many times I riffle shuffle, that ace of hearts is thrown to the top of the stack. Not very random.
Say I *try* to make it more random by occasionally grabbing the top of the deck with my other hand. After 5 shuffles, the AoH is still likely to be somewhere in the top half of the deck. Better, but still not truly random. But after a few more riffle shuffles (occasionally switching which hand grabs the top of the deck), it gets closer to truly random.
On the other hand, I agree that "perfect" riffle shuffling isn't exactly random either.
--DavidCary 23:34, 11 January 2006 (UTC)
[edit] Speed rate for shuffling
Someone should add a section on performance issues associated with different shuffling algorithms ? Maybe have a diagram with real world data, and clock cycles used, approx milliseconds, etc.. Help the real world developers.. I actually might be able to come up with some data and sample code if I come up with some free time
- Have you seen http://c2.com/cgi/wiki?LinearShuffle ?
[edit] Riffle and Bridge
I disagree that the bridge "technique" after a riffle shuffle is just for showing off. On softer paper playing cards, the cards bend easily from a riffle shuffle, and the bridge bends them back, keeping them straight. 70.111.224.85 19:05, 11 January 2006 (UTC)
I also disagree with this business about the "bridge" being some kind of show-off technique. But it hardly matters whether I disagree or not; the important thing to consider here is that it's nothing but opinion, and therefore non-NPOV, and therefore doesn't belong on the Wikipedia. I've deleted the statement, along with the first sentence of the sub-section dealing with the pile shuffle, since it's not only misleading but also self-contradictory (it starts by saying the pile shuffle isn't a randomization procedure [the portion I've deleted] and then immediately goes on to say that the aim of it is to move formerly-adjacent cards apart--which, since adjacent cards tend to be adjacent because they formed runs or sets and the person holding the hands put them together, would clearly imply that it is a randomization procedure). Buck 01:32, 31 January 2006 (UTC)
I'm going to point out that pile shuffling is NONRANDOM. If the order is known before a pile shuffle, the order will be known afterwards. There's a card game called "magic: the gathering". In it, some people try to gain advantage by putting all 20 cards of one type first, then all 40 cards of another type, then pile shuffling in 3 stacks to get it into 1-2-1-2 order. It's cheating because it's not random.
[edit] Pile shuffle
The pile shuffle section contains the statement: "This is the only method of human shuffling approved in bridge when four piles are used (each pile is then assigned to the four players in this game)". This can't possibly be correct; as is correctly pointed out above, the pile "shuffle" is hopelessly non-random and wholly inadequate. Please provide a reference or remove. --LDC 14:38, 1 June 2006 (UTC)
- Is it just me, or is the pile shuffle as described for use in bridge ("each pile is then assigned to the four players in this game") just a description of dealing the cards? --VinceBowdren 18:35, 21 November 2006 (UTC)
[edit] Speed
Someone changed my "five seconds" claim for the speed of a good casino shuffle to fifteen; I can't imagine any experienced poker dealer that slow being able to keep a job for long. --LDC 22:19, 3 June 2006 (UTC)
[edit] Proposed move
Per Wikipedia:Naming conventions, shouldn't this article be at Shuffling? If there are no objections filed within a week or so, I'll move it there. howcheng {chat} 23:19, 2 October 2006 (UTC)
[edit] Knuth shuffle
- "Notice that great care needs to be taken in implementing the Knuth shuffle; even slight deviations from the correct algorithm will produce biased shuffles. For example, working your way through the pack swapping each card in turn with a random card from any part of the pack is an algorithm with nn different possible execution paths, yet there are only n! permutations. A counting argument based on the pigeonhole principle will clearly show that this algorithm cannot produce an unbiased shuffle, unlike the true Knuth shuffle, which has n! execution paths which match up one-to-one with the possible permutations."
Is this at all true? Obviously if there are fewer execution paths than permutations, an unbiased shuffle is impossible per the pigeonhole principle. But "overshuffling" with an algorithm that has more execution paths than permutations surely need not be biased.
In fact, I contend that this supposedly defective algorithm is in fact unbiased and equivalent to the Knuth shuffle. After operating on each card position, that position is equally likely to be any of the n cards from the deck. Subsequent operations are independent and cannot affect this. So after the algorithm is complete, every card position is totally randomized, just as in the vanilla Knuth algorithm. The only difference is that no "excess entropy" is wasted in the Knuth algorithm, which may be theoretically elegant but irrelevant in implementation.
So unless anyone can show otherwise, I propose that this entire section be removed, because it is misguided and incorrect. NTK 03:03, 26 October 2006 (UTC)
- The pigeonhole argument is useful precisely because it's hard to reason about shuffling, because it does an end-run around all possible arguments involving tracking the state of the pack as it travels through its configuration space, and considers only apportioning outcomes to execution paths at the end of the shuffle.
- For an example of how the pigeonhole argument works on the n^n shuffle, first try the simpler case of shuffling three cards, so that n=3. Then there are n^n = 27 different possible execution paths (these are the 27 things to put in the pigeonholes). But there are only 6 ways to permute three cards (these are the 6 pigeonholes to put the things in). 27 is odd, and 6 is even, so 27 things cannot be divided evenly into 6 pigeonholes. Therefore, if we assume that the execution paths are equiprobable, then the outcomes cannot be, since at least two of the different outcomes must have different probabilities. Therefore the n^n shuffle cannot be unbiased for n=3.
- Now consider the full pack of playing cards. For n=52, there are 170676555274132171974277914691501574771358362295975962674353045737940041855191232907575296 possible execution paths, but only 80658175170943878571660636856403766975289505440883277824000000000000 ways to permute 52 cards. Now consider prime factors: just looking at the last digit tells you that the former number is not divisible by 5, but that the second is. Therefore the larger number cannot be divided evenly by the smaller, and so the shuffle must be biased, by the same reasoning as in the n=3 case. QED.
- By the way, the argument above only provides a non-zero lowerbound to the bias of the n^n shuffle algorithm, not an estimate of the level actual level of bias in that algorithm.
- -- The Anome 09:52, 26 October 2006 (UTC)
- Just as a postscript to the above: if I had to implement a shuffling system, I'd use the attach-random-numbers-then-sort method, with retries if two of my random numbers collided, since it is far easier to understand, (almost) a one-liner in most decent programming languages [*], and avoids both the above issue and the modulo bias issue. While the Knuth shuffle method is cleaner and better if implemented correctly, unless computational cost was at a premium, I'd prefer to use an algorithm that is harder to get wrong, at a computational cost ratio of O(log n), than risk coding the Knuth algorithm wrongly. -- The Anome 13:03, 26 October 2006 (UTC)
- [*] For example, in Python: [x[1] for x in sorted([(random(), y) for y in seq])], if you ignore the check for duplicate random numbers, and random() yields true random numbers.
-
- Wonderful explanation! Somewhere in the mathematical portion of my brain a Rigor Alarm was going off as I typed "Subsequent operations are independent and cannot affect this." Clearly a year of law school has induced this Monty Hallesque blunder. NTK 03:24, 28 October 2006 (UTC)
