It’s almost certainly still good enough since it’s unlikely to be biased in ways that matter. Most hand shuffling methods have nasty biases as well.

For standard riffle shuffling, there is often a bias in pulling from the pile opposite from the last pulled card (so alternating pairs of left and right). The model saying “7 shuffles is sufficient” as people like to quote presumes you pull from a pile only proportional to the size of the pile (so you get many fewer alternating runs).

There were a lot of practical attacks on poker PRNGs without enough internal state, where one could form a database of possible hands based on the first few cards.

I think the bare minimum requirement for a good shuffler is "all hands are possible." And then getting some more bits beyond that is good to debias it.

That is such an interesting idea! I wonder if someone has systematically studied hand shuffling biases and what consequences it has (or should have) for brick and mortar casinos

Yes. Card counters (advantage players at blackjack) studied shuffle tracking. I haven't seen much good material published on it, but I played on a team with a math whiz (physicist) who ran the numbers. For the casino we were playing at the time, the last 20 or so cards would be distributed over the bottom half of a six-deck shoe. A strategic cut would bring those three decks to the front, and you could play with a slight advantage.

Suppose you're at a full table and 12 of the last 20 cards are aces or tens (rare but possible). These get shuffled and cut into the first three decks, giving you a true count of four (12/3) for the first half of the shoe, which is significant.

We never really put it into practice, though, since: 1) you have to track the count for the last 20 cards in addition to the regular count, 2) shuffles change, 3) dealers are inconsistent, 3) casinos use different shuffles, 4) the typical advantage is likely to be much smaller.

My knowledge on this is at least 20 years out of date, though, so who knows?

The bias I saw would likely be difficult to exploit without studying the mathematics a lot more. It seems to pass several statistical tests, but the problem I found was more about independence.

Let's call the two splits L for left and R for right and consider the resulting deck to be defined as a sequence of these letters indicating whether that card was taken from the left or right pile so in theory you can specify a shuffle uniquely like "LRRLLLLLLRRR...". This method of labeling shuffles has the advantage of being extremely easy to record and also makes the bias I found apparent where there are way too many pairs of "LR" and "RL" compared to "LL" and "RR" like the "7 shuffles is enough" model suggests there should be.

For some reason, when I did all this analysis last year, I was mostly thinking about how to ensure my MTG decks are sufficiently shuffled. I didn't really think about the implications for card counting. However, normal riffle shuffling seems to have less bias (but still present) than the mash shuffling I looked at and I think most casinos use machines for shuffling these days.

This is tangental, but I believe Persi Diaconis recommended like 13 riffle shuffles* if national security is at stake. Who knows, maybe one day nuclear launch codes will depend on the Solitaire cipher.

* Depending on how chunky your shuffle is. A pro card dealer can do almost a perfectly alternating riffle, which is obviously no good for national security.

Yes, and the trouble I've seen is that MTG players assume they aren't shuffling like a pro card dealer when their shuffles are actually even more uniform. IIRC Diaconis' original study even mentioned that the number of required shuffles balloons out of control with these very uniform shuffles.

Yes. In particular, the cards that are never dealt out don't matter at all. So for example, in Texas Hold 'em with 9 players, you "only" deal out 23 cards, so we have overcounted the number of possible decks by 29!

It's not even obvious to me that repeated shuffles of this form

• Given a deck of 52 cards (C1, C2, ... C52) pick some k near 26 and split the deck into two piles, (C1, C2, ..., Ck) and (Ck+1, ..., C52). Call these piles P1 and P2,

• Make a new empty pile, and then repeatedly take cards from the front of P1 or P2 and append those cards to the new pile. Cards from the same source pile should be in the same relative order in the new pile. Continue until all the cards are in the new pile,

• When taking cards from P1 or P2 to append to the new pile, take about the same number each time,

are capable of resulting in all possible 52! permutations. That kind of shuffle preserves a lot of order so I wondered if there might be some order that it cannot remove.

It turns out that you can in fact reach all permutations. I don't know of any elegant way to prove this though. I have an ugly way to do so.

Let R be a perfect out riffle shuffle, where the deck is split exactly in half (k = 26), and cards are merged by pulling one at a time from alternate piles starting with P1. In other words the deck after one shuffle is (C1, C26, C2, C27, ..., C26, C52).

Let S(n) be a shuffle just like R with one exception: when the cards that would end up at positions n and n+1 from the bottom of the shuffled deck are the next two cards to be pulled from P1 and P2 switch the order you pull them.

The resulting shuffle is the same as if you did R and then swapped the cards at positions n and n+1 from the bottom.

Let O(X) be the "order" of a shuffle X. The order of a shuffle is how many times you have to do apply the shuffle consecutively to get back to where you started. O(R) for example is 8. Start with a new deck and do 8 perfect out riffle shuffles and you will be back to the original order.

It turns out that if you take a deck and do O(S(n))-1 shuffles using S(n) and then do an R you get back to where you started except the cards n and n+1 from the bottom are swapped.

A swap of any two cards can be accomplished using a series of swaps of adjacent cards and so this gives us a method to swap any two cards in the deck using only R and S shuffles. Since any permutation can be generated using only pair swaps this means any of the 52! possible permutations can be reached using only R and S shuffles.

This isn't very efficient. Just swapping n and n+1 in the deck this way takes at least 16 shuffles, and many more for some values of n. Here's a table:

      n           # of shuffles
   0, 50            72
   1, 49            56
  16, 17, 33, 34    40
  22, 28           120
   other            16

Remember, adjacent swaps are just one small step in getting to a given permutation. Actually reaching an arbitrary permutation using R and S shuffles this particular way would take tens of thousands or more shuffles. But it does show that all permutations are reachable using reasonably normal shuffles.

I think we really need to consider the efficiency of the shuffle as well when evaluating a shuffling technique. If it takes hundreds (much less tens of thousands) of lengthy steps to shuffle the deck, then no one is going to do it.

Additionally, your analysis only considers when the permutation is reachable. You would also want to look at how likely each permutation is.

Counterpoint, even if you only have 256 bits of entropy (which is common for many widely used PRNGs), you can prove that there's bias due to the pigeon hole principal, but finding a shuffle that is under-represented is computationally impossible.

Eventually, but long after the Sun has expanded into a red giant and burned the surface of the Earth off.

How many shuffled decks do you need to with 99% confidence determine if I used say Mersenne Twister or a hardware-based RNG?

edit: I know MT has a rather large state, but it has some issues. Alternatively what about say one of the 128bit state PCG generators?

> if you don’t have more than 230 bits of entropy

Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?

I did round, but you probably need more than 226. Because 52! does not divide into any power of 2.

Imagine if you had 5 possible hands, and 3 bits of entropy. Some hands are going to be twice as likely than others (pigeon hole principle).

So if you have 4 bits more, the least common hands will be 31/32 as common as the most common hands.

How fast things go badly is proportional to how well you can measure the bias, isn't it? If you need 2^200 hands to do so, good luck getting there.

And a CSPRNG has to be robust to sharing every single bit so far with your adversary.

Exactly.

> things go badly pretty quick.

Dealing 2^200 hands, assuming that one hand takes 1ns, is more than ... pretty much any conceivable physical quantity one can think of. (Technically, the heat death of the universe takes longer than that but all card decks will be long gone, having been consumed by black holes.)

This is a long-winded way of saying that cryptography with 2^256 security margin ought to be sufficient for all human-scale applications.