CCCCCCCCCCCCC d::::::d SSSSSSSSSSSSSSS hhhhhhh ffffffffffffffff ffffffffffffffff lllllll
CCC::::::::::::C d::::::d SS:::::::::::::::Sh:::::h f::::::::::::::::f f::::::::::::::::f l:::::l
CC:::::::::::::::C d::::::d S:::::SSSSSS::::::Sh:::::h f::::::::::::::::::ff::::::::::::::::::fl:::::l
C:::::CCCCCCCC::::C d:::::d S:::::S SSSSSSSh:::::h f::::::fffffff:::::ff::::::fffffff:::::fl:::::l
C:::::C CCCCCC aaaaaaaaaaaaa rrrrr rrrrrrrrr ddddddddd:::::d S:::::S h::::h hhhhh uuuuuu uuuuuu f:::::f fffffff:::::f ffffff l::::l eeeeeeeeeeee
C:::::C a::::::::::::a r::::rrr:::::::::r dd::::::::::::::d S:::::S h::::hh:::::hhh u::::u u::::u f:::::f f:::::f l::::l ee::::::::::::ee
C:::::C aaaaaaaaa:::::ar:::::::::::::::::r d::::::::::::::::d S::::SSSS h::::::::::::::hh u::::u u::::u f:::::::ffffff f:::::::ffffff l::::l e::::::eeeee:::::ee
C:::::C a::::arr::::::rrrrr::::::rd:::::::ddddd:::::d SS::::::SSSSS h:::::::hhh::::::h u::::u u::::u f::::::::::::f f::::::::::::f l::::l e::::::e e:::::e
C:::::C aaaaaaa:::::a r:::::r r:::::rd::::::d d:::::d SSS::::::::SS h::::::h h::::::hu::::u u::::u f::::::::::::f f::::::::::::f l::::l e:::::::eeeee::::::e
C:::::C aa::::::::::::a r:::::r rrrrrrrd:::::d d:::::d SSSSSS::::S h:::::h h:::::hu::::u u::::u f:::::::ffffff f:::::::ffffff l::::l e:::::::::::::::::e
C:::::C a::::aaaa::::::a r:::::r d:::::d d:::::d S:::::S h:::::h h:::::hu::::u u::::u f:::::f f:::::f l::::l e::::::eeeeeeeeeee
C:::::C CCCCCCa::::a a:::::a r:::::r d:::::d d:::::d S:::::S h:::::h h:::::hu:::::uuuu:::::u f:::::f f:::::f l::::l e:::::::e
C:::::CCCCCCCC::::Ca::::a a:::::a r:::::r d::::::ddddd::::::dd SSSSSSS S:::::S h:::::h h:::::hu:::::::::::::::uuf:::::::f f:::::::f l::::::le::::::::e
CC:::::::::::::::Ca:::::aaaa::::::a r:::::r d:::::::::::::::::d S::::::SSSSSS:::::S h:::::h h:::::h u:::::::::::::::uf:::::::f f:::::::f l::::::l e::::::::eeeeeeee
CCC::::::::::::C a::::::::::aa:::ar:::::r d:::::::::ddd::::d S:::::::::::::::SS h:::::h h:::::h uu::::::::uu:::uf:::::::f f:::::::f l::::::l ee:::::::::::::e
CCCCCCCCCCCCC aaaaaaaaaa aaaarrrrrrr ddddddddd ddddd SSSSSSSSSSSSSSS hhhhhhh hhhhhhh uuuuuuuu uuuufffffffff fffffffff llllllll eeeeeeeeeeeeee
Have you ever experienced those poker nights where straights or higher appeared every other hand? On such occasions, I've walked away from the table cursing the dealer for not shuffling enough. But even so, how are four straights in a row statistically possible?
The goal of this project is to understand the phrase: "seven riffle shuffles are enough to perfectly shuffle a deck of cards." In the real world, expecting seven shuffles for every hand of poker is far too much. Furthermore, poor technique and alternative shuffling methods are all too common in home games.
This challenge is difficult to solve with combinatorics, but I will introduce some relevant equations to gauge the accuracy of the simulations. Some of the programs are written in C++, while others are in Python 3. These are all relatively simple simulations, but I got tired of writing boilerplate code in C++ and realized Jupyter Notebook was a better environment for this project.
Lets get started with some of the most common card shuffling techniques:
- Riffle: Interweave two packs of cards
- Hindu and Overhand: Move a packet from one hand, to the bottom of a new stack in the other.
- Cut: Split the deck and place one stack on the other.
- Faro: Resembles a riffle shuffle, but every card is interwoven perfectly.
Desktop: Hover links to see shuffle examples
Mobile: Click
Simulation Parameters, Sample Sizes and Optimization
A difficulty with this type of simulation is obtaining a large enough sample size. Because there are two parameters in this simulation—shuffle quality and number of shuffles—the total number of simulations becomes multiplicative and, consequently, costly. I've managed to keep all the runs under one hour in length, with the express goal of exceeding the number of samples needed to reach statistical significance. I will demonstrate how to calculate the statistically required number of runs, but to produce visually appealing graphs, I always surpass this.
A note on optimization: Every shuffle can be executed in O(deck = 52) time complexity. There might be some minor optimization possible for these functions, but is it worth the effort? Multithreading only yielded around a 6x speedup on 8 cores. Perhaps a clean 8x speedup would be achievable if locking/shared memory was eliminated.
I will discuss how the mechanics of card shuffling techniques impact the distribution of cards in the deck, the overall deck randomness, and how this results in skewed probabilities in real table games.
Riffle Analysis
1void riffle(int* arr,int maxpacket){
2 int left[n/2]; int right[n/2];int i=0;int li=0;int ri=0;bool swapdeck=rand()%2;
3 //split deck into two packets, left and right
4 for(int i = 0; i<n; i++){
5 if(i<n/2) left[li++] = arr[i];
6 else right[ri++] = arr[i];
7 }
8 i = 0; li = 0; ri = 0; int packet=rand()%maxpacket+1;
9 while(i<n){
10 //interweave next card in packet
11 if(swapdeck) arr[i++] = left[li++];
12 else arr[i++] = right[ri++];
13 if(--packet==0){
14 //make a new random packet, pulling from the other side
15 packet=rand()%maxpacket+1;
16 swapdeck = !swapdeck;
17 }
18 //if one packet has been exausted, pull from the other exclusively
19 //(packet size no longer matters)
20 if(li+1>n/2) swapdeck = false;
21 else if(ri+1>n/2) swapdeck = true;
22 }
23}Now we can run this simulation for a single deck 15 times, then repeat that simulation for a few hundred thousand runs to guarantee statistical significance.
A few notes about how the simulation and analysis are performed:
- Iteration: An individual deck after a certain number of shuffles
- X-Axis: number of shuffle iterations
- Y-Axis: average possition on a particular iteration
- Runs per iteration: ~210,000
- Total shuffles in simulation: 3.2 million
- Y1-Axis: number from range 0 to max entropy
- Entropy: information theory concept which measures the of randomness of a set. This is the standard method to measure randomness in a deck of cards.
1double getEntropy(int* arr){
2 int freq[n];
3 for(int i = 0; i<n; i++) freq[i] = 0;
4 double entropy = 0.0;
5 for(int i = n; i>0; i--){
6 //need to account for the wrapping of the list, setting previous 0 as n-1
7 int card = arr[i]; int pcard= -1;
8 if(i==0) pcard = arr[i-1+n];
9 else pcard= arr[i-1];
10 int diff = (card - pcard + n)%n;
11 freq[diff] = freq[diff] + 1;
12 }
13 for(int i = 0; i<n; i++){
14 //sum probabilities of x in X adjusted by entropy formula
15 if(freq[i]!=0){
16 //probability of selecting card i in the set of all N cards
17 double p = (double)freq[i]/(double)n;
18 //formula https://en.wikipedia.org/wiki/Entropy_(information_theory)
19 double x = -1*p*log(p);
20 entropy = entropy + x;
21 }
22 }
23 return entropy;
24}For a deck of 52 cards, a fully randomized deck using the fisher-yates shuffle will average around a 3.3 entropy score. This number does not have any units so its only scale is against 0 and itself.
For example, a larger deck naturally contains more information, so its entropy while shuffled is higher. With N=1000, maximum entropy increases to ~6.41, as the scale is logerithmic.
The average position of the first card to be a good approximator for how random the deck is, since it can also contain more information than a simple scalar value. Our large sample size allows us to utilize the law of large numbers and make inferences with high confidence when a particular pattern is found.
The next graph shows how the riffle shuffle impacts games based on two parameters: packet size, and iteration count.
- X-Axis: number of shuffle iterations
- Y-Axis: probability of a straight happening in game
- Notes: Lighter colors represent a high max packet parameter which represent 'looser' or 'worse' riffle shuffles. Darker colors are clean riffle shuffles, with a tighter spread, see the above example.
- Both Charts: 5 players, 5 card board, 2 card hands
- Chart 1: "New Deck Start", a completely fresh deck, new out of the box
- Example:
- [0, 1, 2, 3, 4, 5, 6, 7, ... 49, 50, 51]
- Notes: Unrealistic, but worst case scenario.
- Chart 2: "Rigged Start", There are 5 cards in a row, while the rest of the deck is random
- This situation more closely represents this common situation: a player who wins a hand with a straight may put their cards on the flop, and this pack of cards gets shuffled into the deck.
- Example:
- [7, 12,
0, 1, 2, 3, 4,
9, ... 12, 5, 2] - Notes: I am only keeping track of straights, only ranks need to be tracked.
- 1,000,000 runs per data point
The chart is interactive, click the "1" dataset in the legend to hide it.
Outliers and Quantum Wave Theory?
Notice how much of an outlier the shuffle with MaxPacket=1 is. This shuffle is equivalent to the Faro shuffle, where every card is interleaved perfectly, definitively showing that the Faro shuffle is deterministic and should not be used for real-world shuffling. A side note: closely observe card magicians, this shuffle appears frequently because it is deterministic and makes it easier to force cards.
The red line in this graph represents a perfectly shuffled deck, replacing a riffle shuffle with the Fisher-Yates algorithm. The first thing to notice is how the lighter, worse shuffles take much longer to converge to the expected value of straights. This is easily explained by the mechanics of the shuffle: with larger packet sizes, you may miss breaking up the straight, making it more likely in all subsequent runs.
One thing I have trouble explaining is the sudden dip in probability below the expected value. I don't understand the mechanics of why this happens, but it is repeated in all of the attempts I made.
Rationalizing Error with Waves (Conjecture)
The first thing to know is that this simulation is limited and has strict parameters. Real-world shuffles have a lot more variation that cannot be explained by "MinPackets" and "MaxPackets" as described in the implementations. For simulations that are bounded by strict rules, such as this one, wave functions could provide a mathematical grounding for the result.
Quantum waves are essentially probability distribution functions for fundamental particles such as photons. This theory has been applied to computational processes like terrain generation. Imagine one shuffle moves the cards around according to a sine wave, and multiple shuffles move cards based on the combinations of those waves. In theory, it would be possible to construct a wave function for a certain type of shuffle and use that function to predict the distribution of cards at a specific number of shuffles. This is more interesting because you could combine multiple types of shuffles in this fashion to predict the distribution of cards when combining Riffle and Hindu shuffles.
Hypothesis: Given a set of well defined shuffling algorithms, you can calculate the probility distribution for every element by multiplying the 'Wave fucntion' in a non-commutative operation.
Even in a "mostly" randomized deck, the deterministic nature of the Faro shuffle demonstrates that it distorts the asymptotic behavior of this shuffling algorithm.
Even with this outlier remved (interact with the legend), we still observe this strange dip in straight probability with Iterations=2. Comparing this to the entropy graph, we can see that all types of shuffles eventually converge to a probability of about 4% with no strange deviation. This is close to the expected for a 7-card poker hand which makes me believe this simulation is a good approximation for real games.
Hindu Analysis
1void hindu(int* arr,int maxpacket){
2 deque< deque<int> > decklist;
3 int i = 0;
4 while(i<n){
5 //set a packet length to be transfered
6 int p = rand()%maxpacket+1;
7 deque<int> deck;
8 for(int j = 0; j<p; j++){
9 if(i+j>=n) {
10 //all cards have been place in 'deck'
11 break;
12 }
13 deck.push_back(arr[i+j]);
14 }
15 i+=p;
16 //place correctly moved packet to the top of the new decklist
17 decklist.push_front(deck);
18 }
19 i = 0;
20 //copy the new shuffled deck to the existing deck array
21 while(!decklist.empty()){
22 deque<int> packet = decklist.front();
23 deque<int>::iterator pit = packet.begin();
24 while(pit != packet.end()){
25 arr[i++] = *pit++;
26 }
27 decklist.pop_front();
28 }
29}Keep in mind that the hindu and overhand shuffles are equivalent in terms of how the cards are being cycled. This simulation has 10,000,000 individual shuffles, with 1,000 iterations. This one took a while to run, and resulted in very large files as every result was saved. The representation of the results was quite challenging because of how much data was generated.
Pay attention to the 1st, 8th, and 16th cards and how their iteration numbers always maintain the same parity (even/odd). This can be explained by the mechanics of how the Overhand shuffle works. Since you are moving packets of cards to the bottom, the first shuffle slightly randomizes the order but absolutely reverses the typical ordering of the deck, only to be swapped back to a similar starting position on the next shuffle. This stratification effect is observed at all packet sizes but is most visible in low numbers. Simply adding more variability to the packet size results in faster convergence to a truly random deck.
There is no entropy field in this specific dataset, but the standard entropy calculation will not capture this detail about parity swapping.
To visually demonstrate why you should never use an Overhand or Hindu shuffle in any games where you care about randomness, take a look at how the first card travels through parts of the deck over the course of 15 shuffles:
Conclusion
It is save to say that the mathematicians were right in recommending 7 Riffle shuffles. What they didn't say was how that assumption can fall apart with mediocre technique. I will add more common shuffling techniques and more in depth analysis in the future.