10 ms·

Zero Tolerance for Bias

190 points by Harmohit 2y ago

tbrownaw 2y ago
Trusting a broken library seems like a different kind of error than implementing an algorithm that isn't quite the algorithm you meant to implement.
zug_zug 2y ago
Kinda interesting. 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.
- vlovich123 2y ago
  The number of permissions of a deck of cards is 2^225 according to the article. Permissions grow quite quick
  - zug_zug 2y ago
    Yeah. So something like a 50-digit number. I guess your point is this would require a BigInt? From a performance perspective it's negligible. Like when doing RSA for example the primes are usually 2^512 in length.
    - vlovich123 2y ago
      Your algorithm will never shuffle a deck of cards because randomly selecting a 64 digit means your N(logN) algorithm will need to generate on average the 2^63th or larger permutation. It’ll be several millennia for every deck shuffle. If you don’t believe me try to write it. 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.
      - zug_zug 2y ago
        I don't know what you're talking about, and that makes two of us. 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-permutation-without-computing-others https://stackoverflow.com/questions/7918806/finding-n-th-per...
- pvillano 2y ago
  A real pendant would handle collisions 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
  - whyever 2y ago
    You can calculate the probabilities and expected number of collisions analytically, but evaluating the expressions numerically is tricky for large numbers. I can recommend https://herbie.uwplse.org/ https://herbie.uwplse.org/ to rewrite the expressions into a form that can be evaluated.
im3w1l 2y ago
Fisher Yates is simple, fast and correct. The only area of improvement I can think of is reducing cache misses.
- o11c 2y ago
  That needs some conditions: * 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. https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html
  - im3w1l 2y ago
    Modern languages usually provide a generate integer in range primitive. Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution
    - jltsiren 2y ago
      The C++ distributions are problematic, because the standard does not specify the algorithms. If you specify the generator and the seed, you can still get different random numbers on different platforms. Which is why applications that need reproducible results must use another library or implement their own distributions.
  - Dylan16807 2y ago
    What's unnecessary slowness in this situation? Are we worried about a single division per random number? 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.
    - whyever 2y ago
      You will still get better results when avoiding the bias, even with a non-CSPRNG. Their bias is much smaller. Avoiding the division can be faster, especially if you sample many numbers from the same range. But it depends on the use case.
orlp 2y ago
Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): 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 Naturally, p(1-p) and (1-p)p are equiprobable, thus if we reject the other outcomes we have distilled an unbiased coin out of our biased coin.
- amelius 2y ago
  Regarding your second fact: if we need N tosses, then is your method the most efficient one?
  - orlp 2y ago
    Looking into it a bit, it appears that this particular fun fact was first thought of (or at least put to paper) by von Neumann in "Various techniques used in connection with random digits" in 1951. Yuval Peres proves in "Iterating von Neumann's procedure for extracting random bits" that if N goes to infinity it approaches the entropy limit. 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.
skybrian 2y ago
I recently stumbled across some other ways that random number generation can go wrong. 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_generator https://en.wikipedia.org/wiki/Counter-based_random_number_ge...
- londons_explore 2y ago
  > When a mutable random number generator is copied to a child task 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.
  - skybrian 2y ago
    Makes sense. Do you have any particular implementations in mind that work this way? 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.
IAmLiterallyAB 2y ago
Interesting, but there's one part I'm not sure I agree with. > 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/msg04763.html 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
- 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
tomcam 2y ago
I'm sure I'll get roasted for this, but getting the right answer will scratch a years-old itch. Why aren't most random number generators seeded using the system clock in addition to the existing algos?
- skybrian 2y ago
  It's not entirely useless, but as a source of entropy, it's pretty predictable. You'd only get a few bits.
- YZF 2y ago
  seeding PRNGs from the system clock is quite common. Using the system time as a source of entropy for generating secure random numbers is problematic because it's not random. You want sources that are "noisy" to contribute. 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.
- whyever 2y ago
  Nowadays, your operating system has a dedicated API for providing randomness (e.g. `getrandom` on Linux), so you would just use that to seed your RNG. Using the time is questionable, because an adversary can often estimate when the RNG was seeded, enabling brute-force attacks to reconstruct the seed.
deleted 2y ago
[deleted]
westurner 2y ago
python has random.shuffle() and random.sample() with an MT Mersenne Twister PRNG for random. https://docs.python.org/3/library/random.html#random.shuffle https://docs.python.org/3/library/random.html#random.shuffle Modules/_randommodule.c: https://github.com/python/cpython/blob/main/Modules/_randommodule.c https://github.com/python/cpython/blob/main/Modules/_randomm... , Library/random.py: https://github.com/python/cpython/blob/main/Lib/random.py#L354 https://github.com/python/cpython/blob/main/Lib/random.py#L3... From "Uniting the Linux random-number devices" (2022) https://news.ycombinator.com/item?id=30377944 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 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 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 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_crypto/lib/randomness_tests https://github.com/google/paranoid_crypto/tree/main/paranoid...

190 points by Harmohit 2y ago

Trusting a broken library seems like a different kind of error than implementing an algorithm that isn't quite the algorithm you meant to implement.

zug_zug 2y ago

Kinda interesting. 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.

vlovich123 2y ago
The number of permissions of a deck of cards is 2^225 according to the article. Permissions grow quite quick
- zug_zug 2y ago
  Yeah. So something like a 50-digit number. I guess your point is this would require a BigInt? From a performance perspective it's negligible. Like when doing RSA for example the primes are usually 2^512 in length.
  - vlovich123 2y ago
    Your algorithm will never shuffle a deck of cards because randomly selecting a 64 digit means your N(logN) algorithm will need to generate on average the 2^63th or larger permutation. It’ll be several millennia for every deck shuffle. If you don’t believe me try to write it. 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.
    - zug_zug 2y ago
      I don't know what you're talking about, and that makes two of us. 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-permutation-without-computing-others https://stackoverflow.com/questions/7918806/finding-n-th-per...
pvillano 2y ago
A real pendant would handle collisions 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
- whyever 2y ago
  You can calculate the probabilities and expected number of collisions analytically, but evaluating the expressions numerically is tricky for large numbers. I can recommend https://herbie.uwplse.org/ https://herbie.uwplse.org/ to rewrite the expressions into a form that can be evaluated.

im3w1l 2y ago

Fisher Yates is simple, fast and correct. The only area of improvement I can think of is reducing cache misses.

o11c 2y ago
That needs some conditions: * 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. https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html
- im3w1l 2y ago
  Modern languages usually provide a generate integer in range primitive. Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution
  - jltsiren 2y ago
    The C++ distributions are problematic, because the standard does not specify the algorithms. If you specify the generator and the seed, you can still get different random numbers on different platforms. Which is why applications that need reproducible results must use another library or implement their own distributions.
- Dylan16807 2y ago
  What's unnecessary slowness in this situation? Are we worried about a single division per random number? 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.
  - whyever 2y ago
    You will still get better results when avoiding the bias, even with a non-CSPRNG. Their bias is much smaller. Avoiding the division can be faster, especially if you sample many numbers from the same range. But it depends on the use case.

orlp 2y ago

Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits): 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 Naturally, p(1-p) and (1-p)p are equiprobable, thus if we reject the other outcomes we have distilled an unbiased coin out of our biased coin.

amelius 2y ago
Regarding your second fact: if we need N tosses, then is your method the most efficient one?
- orlp 2y ago
  Looking into it a bit, it appears that this particular fun fact was first thought of (or at least put to paper) by von Neumann in "Various techniques used in connection with random digits" in 1951. Yuval Peres proves in "Iterating von Neumann's procedure for extracting random bits" that if N goes to infinity it approaches the entropy limit. 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.

skybrian 2y ago

I recently stumbled across some other ways that random number generation can go wrong. 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_generator https://en.wikipedia.org/wiki/Counter-based_random_number_ge...

londons_explore 2y ago
> When a mutable random number generator is copied to a child task 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.
- skybrian 2y ago
  Makes sense. Do you have any particular implementations in mind that work this way? 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.

IAmLiterallyAB 2y ago

Interesting, but there's one part I'm not sure I agree with. > 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/msg04763.html 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

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

tomcam 2y ago

I'm sure I'll get roasted for this, but getting the right answer will scratch a years-old itch. Why aren't most random number generators seeded using the system clock in addition to the existing algos?

skybrian 2y ago
It's not entirely useless, but as a source of entropy, it's pretty predictable. You'd only get a few bits.
YZF 2y ago
seeding PRNGs from the system clock is quite common. Using the system time as a source of entropy for generating secure random numbers is problematic because it's not random. You want sources that are "noisy" to contribute. 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.
whyever 2y ago
Nowadays, your operating system has a dedicated API for providing randomness (e.g. `getrandom` on Linux), so you would just use that to seed your RNG. Using the time is questionable, because an adversary can often estimate when the RNG was seeded, enabling brute-force attacks to reconstruct the seed.

deleted 2y ago

[deleted]

westurner 2y ago

python has random.shuffle() and random.sample() with an MT Mersenne Twister PRNG for random. https://docs.python.org/3/library/random.html#random.shuffle https://docs.python.org/3/library/random.html#random.shuffle Modules/_randommodule.c: https://github.com/python/cpython/blob/main/Modules/_randommodule.c https://github.com/python/cpython/blob/main/Modules/_randomm... , Library/random.py: https://github.com/python/cpython/blob/main/Lib/random.py#L354 https://github.com/python/cpython/blob/main/Lib/random.py#L3... From "Uniting the Linux random-number devices" (2022) https://news.ycombinator.com/item?id=30377944 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 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 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 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_crypto/lib/randomness_tests https://github.com/google/paranoid_crypto/tree/main/paranoid...