Zero Tolerance for Bias
queue.acm.org
queue.acm.org
> Pseudo-random number generators are useful for many purposes, but unbiased shuffling isn't one of them.
A properly seeded CSPRNG is perfectly fine at this. And if it's not, then all of our cryptography is pretty much screwed. This is why in modern kernels, /dev/random and /dev/urandom are the same (minus differences in behavior when the initialization isn't complete). As D.J. Bernstein put it, it's superstition to not trust CSPRNGs. https://www.mail-archive.com/cryptography@randombit.net/msg0... And if it's good enough for crypto, it's good enough for card shuffling.
FYI I am not a cryptographer
Shuffling cards is a surprisingly demanding prng application.
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?
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).
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?
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.
• 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
Additionally, your analysis only considers when the permutation is reachable. You would also want to look at how likely each permutation is.
* 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.
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.
And a CSPRNG has to be robust to sharing every single bit so far with your adversary.
> 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.
Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?
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.
As to the idea that it's superstition not to trust CSPRNGs: sometimes, you want to eliminate the variable, and sometimes your CSPRNG is actually worth attacking. A lot of CSPRNGs also involve secret state, so if you are worried that this state might get exfiltrated, some paranoia is ok.
The post here recommends using Intel's RDSEED, which is ironically trusted far less than /dev/urandom by most people who have a secret to keep or a process to protect.
What? If security is a special consideration for some form of data, why would someone choose a non-physical noise source over a hardware-based noise source?
Intel has no published third-party audits of their silicon, and has a very close relationship with some three-letter agencies. Hence the concern.
By contrast, urandom is completely open, and is reseeded relatively frequently with entropy. If both are effectively acting as a CSPRNG, the one with public attention and no secret key that can be handed to a third party is better.
It isn't. Please don't do that! Mersenne Twister is fully reversible given its 624 consecutive outputs (see, for instance, this pretty good write-up: https://blog.ollien.com/posts/reverse-mersenne-twister). In other words, someone who can observe 624 outputs can reconstruct its entire output sequence forward and backward.
According to [1], you only need 4 outputs to predict xoshiro. Predicting PCG is a bit more difficult, but still on the level of "exercise for cryptography students" [2].
[1]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256....
However, "624 consecutive outputs" is not the way to think about it, because those outputs are truncated to narrow integers. A single shuffled deck leaks about 230 bits of information, and backing out the state of a Mersenne twister needs several thousand bits of information.
Suppose you want reproducible results from a seed, along with parallelism. Algorithmic random number generators are usually mutable and generate a sequence of results, limiting parallelism. Rather than a sequence, you want something tree-shaped where you can create an independent random stream for each child task. In higher-level API's, a jump or split operator can be useful.
Counter-based random number generators [1] seem pretty useful in that context. An immutable random number generator works like a hash algorithm that maps each input to an output that's difficult to predict. The problem with this is being careful to avoid using the same input twice. You can think of it as allocating random numbers from a very large address space in a reproducible way. How do you partition the address space, predictably, so that every address is used at most once, and nobody runs out?
Giving each child a unique ID and generating a stream from that is one way. If the tree is deeper, you'll want a unique seed for each path.
When a mutable random number generator is copied to a child task (or maybe just to an iterator), the same random numbers might be generated in two places. Avoiding this is the sort of thing that Rust's borrow checker can prevent - borrowing is okay, but you want to prevent multiple concurrent ownership.
[1] https://en.wikipedia.org/wiki/Counter-based_random_number_ge...
When you make a child task, the parent adds one to the internal state of the random number generator and advances the random sequence by one. The child adds two to the internal state and advances the random sequence by one.
Now you can make any arbitrary tree of tasks, and those tasks each get their own random stream, there is no shared-between-task state or locking needed, and the whole thing is reproducible, even if parent and child tasks are scheduled arbitrarily. fork-ing and use of random numbers can be arbitrarily intermingled.
I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
The SplitMix algorithm looks pretty useful. In Java, this is the built-in SplittableRandom class, and there seems to be an npm for it:
If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
The counter-based RNG I was looking at is an immutable API. It makes it easy to initialize generators in separate tasks by feeding each one a unique ID, but figuring out how to do a split operation is harder. Conceptually, the way to go is to multiply the key by 2 and add either 0 or 1 for each branch, to give them unique IDs. (This is called a pedigree.) However, for unbalanced trees, you will run out of bits. Figuring out how to do deal with that seems tricky?
The LXM generator paper (non-crypto) looks like good reading:
https://dl.acm.org/doi/pdf/10.1145/3485525
They initialize the new child with the next random values of the parent. There is an extra parameter that they use to add more input bits, to reduce the probability of overlap.
Another way things go wrong with the prng tree idea (assuming the implementation is correct and you actually have independent streams) is race conditions in other parts of your code. E.g., say you have two workers reading a queue and using fancy tree-based randomness. You don't have "race" conditions (data races) in safe Rust without a compiler bug, but the language doesn't define which worker will read which item from the queue. You wind up using a different part of the stream for different inputs.
An API that uses split or jump seems a little easier to screw up.
1. Randomly assign each element to list A or list B. 2. Recursively shuffle lists A and B. 3. Concatenate lists A and B.
To prove it's correct, note that assigning a random real number to each element and sorting based on that number is an unbiased shuffle. Then we note the above does in fact do that by considering the fractional base-2 expansion of the random numbers, and noting the above is in fact a base-2 radix sort of these numbers. We can sort these random real numbers even though they have an infinite amount of random bits, as we can stop expanding the digits when the prefix of digits is unique (which corresponds to the event that a list is down to a single element).
I call the above algorithm RadixShuffle. You can do it in base-2, but also in other bases. For base-2 you can make it in-place similar to how the partition for Quicksort is implemented in-place, for other bases you either have to do it out-of-place or in two passes (the first pass only counting how many elements go in each bucket to compute offsets).
The above can be combined with a fallback algorithm for small N such as Fisher-Yates. I believe even though the above is N log N it can be faster than Fisher-Yates for larger N because it is exceptionally cache-efficient as well as RNG-efficient whereas Fisher-Yates requires a call to the RNG and invokes an expected cache miss for each element.
---
Another fun fact: you can turn any biased memoryless coin into an unbiased one with a simple trick. Throw the coin twice, if it gives HH or TT you throw away the toss, if it's HT or TH you use the first toss as your unbiased coin.
This works because if p is the probability that heads comes up we have:
HH: p^2
HT: p(1-p)
TH: (1-p)p
TT: (1-p)^2
So for particular small choices of N there might be more clever schemes, but for large N you can't do a whole lot better.
How does this compare to a regular Knuth shuffle where, since you only have a 1-bit generator, when you need (for example) an integer between 0 and 23, you treat the bits you generate as the binary expansion of a real number in [0, 1), and generate them until floor(24*n) is unambiguous?
(Obviously, the random number generation is more conceptually complex, but aside from that.)
And it is better when N gets large. My implementation set the cutoff at 2^19 elements, although the effect isn't too big for a few more powers of two. Here's the main radix loop: https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysf...
It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.
This trick is mentioned in the article towards the end.
Divide the interval [0, 1) into M equal pieces, [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1).
Use the dM to generate a real number in [0, 1). If that real number is in the interval [(k-1)/N, k/N), your simulated dN roll is k.
To generate a real number in [0, 1) with the dM you simply roll the dM an infinite number of times, and take each roll as a successive base M digit in a base M fraction 0.abcd... where a, b, c, d, etc are base M digits.
You don't actually have to roll an infinite number of times. You can stop when you have enough digits to tell which interval the number is in. For example if you were trying to roll a d12 using a d10, and the first two d10 rolls are 0 and 7 you can stop, because all base 10 numbers that start with 0.07 are in [0, 1/12).
If the first two rolls had been 0 and 8 you would have to keep rolling, because although 0.08 is in [0, 1/12) subsequent rolls could change that because 1/12 = 0.083333(3).
For any particular N and M this can be turned into a state graph where you start at the start node and then select links to follow with your dM until you reach a terminal node labeled with the simulated dN value.
Here are such graphs for rolling a d7 with a d2 [1], a d7 with a d6 [2], and a d5 with a d8 [3].
[1] https://imgur.com/a/Qk2kexn
If it's implemented to run in the typical "depth-first sequential" manner of a recursive algorithm, in which each problem generates its own subproblems, solves them all, and then immediately continues execution until it is itself solved, then it is guaranteed to eventually terminate, since the only way to stall progress forever in this situation would be an infinite, uninterrupted sequence of one outcome (e.g., heads), and that would contradict the assumption that P(heads) = 0.5. OTOH, if a "breadth-first" computation was used, in which all subproblems at a given recursion depth are solved in sequence before any higher-level subproblems, the algorithm could run forever: The top-level problem could produce a mixed run, resulting in two equal-sized subproblems, each of which never makes any progress due to one subproblem always getting all-heads, the other always all-tails.
Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
Let's say we're generating some private key, and using the time as a source, and then writing the cert to a file, you'd probably be able to get a pretty good idea from the timestamp of that file what the system time was when the private key was generated.
Using the time is questionable, because an adversary can often estimate when the RNG was seeded, enabling brute-force attacks to reconstruct the seed.
* original Fisher-Yates is slow; Knuth's variation is what makes it fast
* Fisher-Yates relies on "generate integer in range", which is often implemented badly (with bias, or with unnecessary slowness). See the PCG blog for the best-known solution.
Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution
I wish this page showed some separate charts for fast and slow RNGs and some better slow options. If you actually care about proper shuffling and the minuscule bias you get from 2^64 % 52 then you should be using a CSPRNG, not a cheap method.
Avoiding the division can be faster, especially if you sample many numbers from the same range. But it depends on the use case.
But I agree that a CSPRNG should be the default.
There are N! permutations in a shuffle (no duplicates) and there's an algorithm where you pick one random number between 1->N! and then bring up that permutation (though I don't know how to do it better than N log N with an order-statistic tree). I like this because it requires exactly one random number.
A trivial solution in functional programming (for those of us who find this swap stuff really unreadable and error-prone) would be something like:
[1,2,3,4,5,6].map(x => {return {value: x, order: Math.random()}}).sort((a,b) => (a.order - b.order)).map(x => x.value)
Of course this is N-Log-N, but personally I think it's easy to forget how small logN grows. Like log10(number of atoms in universe) = 82, so if your dataset is smaller than the number of atoms in the universe you could think of it as less than the constant 82.
From a performance perspective it's negligible. Like when doing RSA for example the primes are usually 2^512 in length.
Also, I’m not really sure your nlog(n) algorithm claim is accurate - python’s itertools says that the time complexity to generate the Nth permutation is still N!. So for a 52 deck card on average you’re going to have to generate 2^88 permutations.
By comparison, shuffling is O(n) where your n is the number of items.
Writing the Nth-permutation is something I've done before as a leetcode challenge, here's example code [1]
Maybe python implements it poorly, but it can definitely be done in n-log(n), and also try researching a little more before you pick a disagreement. I'm sure a simple google search could have saved you the trouble.
---- 1 - https://stackoverflow.com/questions/7918806/finding-n-th-per...
If Math.random() is truly uniform, it has about 53 bits of entropy. We can find the likelyhood of a collision with the birthday paradox
... the post ends here because WolframAlpha keeps choking on computations with numbers very, very close to one. I'm not doing derivatives.
Fun fact: Math.random(a,b) always has about 53 bits of randomness, unless b/a is close to 1
From "Uniting the Linux random-number devices" (2022) https://news.ycombinator.com/item?id=30377944 :
> > In 2020, the Linux kernel version 5.6 /dev/random only blocks when the CPRNG hasn't initialized. Once initialized, /dev/random and /dev/urandom behave the same. [17]
From https://news.ycombinator.com/item?id=37712506 :
> "lock-free concurrency" [...] "Ask HN: Why don't PCs have better entropy sources?" [for generating txids/uuids] https://news.ycombinator.com/item?id=30877296
> "100-Gbit/s Integrated Quantum Random Number Generator Based on Vacuum Fluctuations" https://link.aps.org/doi/10.1103/PRXQuantum.4.010330
google/paranoid_crypto.lib.randomness_tests: https://github.com/google/paranoid_crypto/tree/main/paranoid...