4 ms·

There are 52! possible decks of cards— if you don’t have more than 230 bits of entropy in your prng per deck shuffled things go badly pretty quick. You also te

by mlyle 2y ago

There are 52! possible decks of cards— if you don’t have more than 230 bits of entropy in your prng per deck shuffled things go badly pretty quick. You also tend to share deck state so far with the adversary. Shuffling cards is a surprisingly demanding prng application.

magicalhippo 2y ago
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?
adgjlsfhk1 2y ago
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.
- pvillano 2y ago
  I can say, infalsifiably, it will be computationally possible eventually
  - SAI_Peregrinus 2y ago
    Eventually, but long after the Sun has expanded into a red giant and burned the surface of the Earth off.
- deleted 2y ago
  [deleted]
slaymaker1907 2y ago
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).
- Harmohit 2y ago
  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
  - Zanni 2y ago
    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?
    - slaymaker1907 2y ago
      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.
Dylan16807 2y ago
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.
- ilya_m 2y ago
  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.
omoikane 2y ago
> if you don’t have more than 230 bits of entropy Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?
- mlyle 2y ago
  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.

by mlyle 2y ago

magicalhippo 2y ago

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?

adgjlsfhk1 2y ago

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.

pvillano 2y ago
I can say, infalsifiably, it will be computationally possible eventually
- SAI_Peregrinus 2y ago
  Eventually, but long after the Sun has expanded into a red giant and burned the surface of the Earth off.
deleted 2y ago
[deleted]

slaymaker1907 2y ago

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).

Harmohit 2y ago
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
- Zanni 2y ago
  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?
  - slaymaker1907 2y ago
    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.

Dylan16807 2y ago

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.

ilya_m 2y ago
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.

omoikane 2y ago

> if you don’t have more than 230 bits of entropy Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?

mlyle 2y ago
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.