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
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...
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.
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.)
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
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.
> 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.
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).
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?
Should this be 226 instead of 230, since 2**225 < 52! < 2**226 ?
And a CSPRNG has to be robust to sharing every single bit so far with your adversary.
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.
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.
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?
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.
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.
* 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.
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.
Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution
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.
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
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.
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...