When random is not actually random enough

I got lost when OP talked about using 10 integers to choose from 3 choices. I think I figured out what was missing in the explanation. random_u64() Mod 3 does indeed have a single bucket that is oversized. This overweights one option by about 5×10^-20. rand() Itself has only 32767 possible values, so it's also common for a bucket to be overweighted depending on the number of buckets.

• incompatible · 10 hours ago

  Makes you wonder at what point overweighting by about 5×10^-20 is something you'd want to care about.

  • jojobas · 6 hours ago

    Picking that from the noise would take quite a while.

  • pestatije · 5 hours ago

    this is what has always baffled me about statistics...having the opportunity to make things exact, with little effort, it is dismissed just because the small error

    • randomNumber7 · 2 hours ago

      It's basic engineering to do what is necessary for solving a problem. Not more.

      • account42 · 1 hour ago

        Not unless of your definition for "what is neccessary for solving a problem" already includes tolerances for the unforseen.

• omoikane · 7 hours ago

  > rand() Itself has only 32767 possible values For MingW maybe (due to MSVCRT). I think most libraries such as glibc have RAND_MAX at 2147483647.

The thing you actually want is rejection sampling: https://en.wikipedia.org/wiki/Rejection_sampling . That Wiki page makes it sound very complicated but for this purpose our implementation can be laughably simple which has the advantage that you know why it works and can maintain it properly with confidence. Get suitably large inputs, for example if you're trying to pick integers between 2 and 11 inclusive, a nibble (half a byte) would be fine. Now, is the random input in the range you wanted? If so, you've got your answer. If not, throw this random input away and get more. Too many programmers act as though random numbers were a precious resource.

• Dylan16807 · 10 hours ago

  Wow that page really gets lost in the weeds of multiple dimensions. And yeah it's just rerolling when your random number is out of range. If you want it as simple as possible, always generate from 0-n, and grab barely enough random bits for n to fit.

• skybrian · 9 hours ago

  Random numbers aren't precious, but they do take time to generate. Rejection sampling adds a branch and it can matter how often it's taken. In my property-testing framework, generating a large, random array of numbers more efficiently improved performance.

  • deathanatos · 6 hours ago

    If your RNG outputs a u64 (a getrandom() call can do this, or even a simple RNG like xoshiro), a random int in TFA's range of [0, 10) has a very small (6 in 2⁶⁴ chance, or 3.2e-17%, might as well be 0) chance of needing to redraw. Obviously, wider ranges will (possibly) reject more often, but unless the range is huge , rejection should be a very cold branch.

    • skybrian · 2 hours ago

      You’re throwing a lot of bits away, though. If you used four bits per number then you could pack 16 random digits into one 64-bit draw. But a rejection-sampling branch will be taken much more often.

      • adrian_b · 1 hour ago

        If you want to split a 64-bit random number into 16 4-bit random numbers, the quality of the RNG that generates the 64-bit random numbers must be extremely high. Only cryptographic RNGs may have such a high quality. Any non-cryptographic PRNG is useful only if it is much faster than a cryptographic RNG, e.g. one using AES, which in many modern CPUs needs around 10 clock cycles to generate a 128-bit random number (less than that, even less than half of that, in some more recent CPUs). So non-cryptographic PRNGs must generate a 64-bit number in less than 1 nanosecond to be competitive. Many older PRNGs are not this fast, so they are completely obsolete. Such PRNGs do not offer any guarantee that if you take more than one piece of a generated number they will not be correlated. So the rule is that you can not make 2 or more random numbers from 1 random number provided by a PRNG.

  • adrian_b · 1 hour ago

    Rejection is unavoidable if you want a uniform distribution for a number of choices that is not a power of two. Nonetheless, the rejection can be done either before or after the multiplication or division that does most of the job for passing from the input range to the output range. The place where rejection is done can be chosen to minimize the amount of values that are rejected, making thus unlikely that the branch is taken, so it will be correctly predicted most of the time. For maximum speed, it is preferable to use multiplication instead of division, i.e. the input is seen as a fraction less than 1 and after multiplication only the integer part is retained. Taking care to use multiplication is normally more important than worrying that rejection may decrease the performance.

• LoganDark · 10 minutes ago

  Rejection sampling has a chance to never terminate, which makes it incredibly uncertain. I think it's perfectly fair to treat it like a last resort.

I don’t think the “random uint” api is too low-level, or lacks a pit of success - I think you’re just reaching for the wrong api. The problem of “make n bits pseudo randomly set to either 1 or 0” is nearby to your problem of “choose an element according to a probability distribution”, but it’s a separate problem in its own right. I think actually this is an argument for language designers to include a “std.choice” in their standard library that consumes random bytes and correctly performs common ergonomic operations like “get one element at random from this collection”. (If your standard library tries to make a distinction between “regular random number generators” and “cryptographically secured random number generators”, I think this distinction between “generate random bits” and “make probabilistic choices” is about equally important.)

Randomness test > Specific tests for randomness: https://en.wikipedia.org/wiki/Randomness_test Which NIST SP-800-22 implementation instead of the now-archived paranoid_crypto randomness tests? paranoid_crypto/docs/randomness_tests.md : https://github.com/google/paranoid_crypto/blob/main/docs/ran... /? NIST SP-800-22 Rust: https://www.google.com/search?q=NIST+SP-800-22+rust&oq=NIST+... Sometimes it's possible to whiten random to make it uniform random or normal random; Whitening transformation: https://en.wikipedia.org/wiki/Whitening_transformation

so it's not really *random* that isn't random enough - it's the operator% that worsens it

• degamad · 2 hours ago

  Exactly. There's many a page on random which explains why taking the modulus of rand is the wrong choice, but it's also the easiest one, which makes it all to common.

  • binaryturtle · 24 minutes ago

    `man random` has no such disclaimer here on OS X. I guess this refers to a Linux man page?

• antonvs · 1 hour ago

  Yes, but that wouldn’t work as clickbait.

The modulo operator is not a uniform mapping; use Lemire's nearly divisionless method or simple rejection sampling and move on.

After finding out that trig/transcendental was basically not guaranteed to be equivalent across kernels (libc/musl), which caused the dreaded “only fails in CI” problem for me when I was trying to generate nonflat distributions of drng’s, I ended up creating https://github.com/pmarreck/random to solve it, which it did

• syntacticsalt · 3 hours ago

  Curious why you used Box-Muller for normal PRNGs instead of Ziggurat.

  • seanhunter · 1 hour ago

    Ziggurat is badass. It’s also one of those algorithms (like “Metropolis-Hastings”) that has a fantastic name to go along with cool mathematical and practical properties. https://heliosphan.org/zigguratalgorithm/zigguratalgorithm.h...

A Uniform(0, 1) PRNG is the right primitive on which to base a PRNG library for arbitrary real-valued random variables because any real-valued random variable can be represented as an inverse quantile transform of a Uniform(0, 1) random variable. While I agree that only providing this primitive risks footguns as described in the article, I'm skeptical that providing a better UI alone would meaningfully reduce the risk of such footguns because availability and convenience is no guarantee of use if a prevailing attitude of users is that they know better and don't need it. Bisection search is simpler than rejection sampling or inverse transform sampling, yet it's common to see buggy, hand-rolled implementations of bisection search despite wide availability of library implementations with better UI ergonomics than PRNGs. I think wider use of fuzz testing or deterministic simulation testing really is necessary to disabuse people of that notion, along with more articles like the above explaining why hand-rolling an adapter to a uniform PRNG is a false economy compared to proven implementations with vetted statistical properties.

• atoav · 3 hours ago

  I don't really follow your argument. > I'm skeptical that providing a better UI alone would meaningfully reduce the risk of such footguns because availability and convenience is no guarantee of use if a prevailing attitude of users is that they know better and don't need it. If we transfer that argument to other domains it quickly falls apart: We don't need a safety on handguns since some people will opt to not use it properly. We don't need safety belts in cars since some people won't use it. We don't need handrails.. You get the point. This is basically the Nirvana fallacy (also called the perfect solution fallacy): a safety measure not being able to catch 100% of the cases it was meant to prevent is not an argument against it. We could have an argument if that measure would significantly impact usual use cases. Any safety measure needs to be judged both by the benefits and by how practical it is to deploy it (aside from other considerations like maintenance, etc) In this case having an easier to use API is the opposite of impractical. It both safes developers time and reduces the number of errors. And if you still need to write your own function, you totally can. To me that sounds as close as you can get to the definition of a "no-brainer".

  • syntacticsalt · 31 minutes ago

    Yes, I should probably clarify and amend my argument. My impression of the article is that it suggests if ergonomic APIs were more available than they already are, then the frequency with which we see bugs in implementing random variable sampling would decrease. I question that premise because the ergonomic APIs already widely exist -- as the article itself points out, in many language standard libraries, and also in popular third-party libraries. Such a suggestion seems like it relies too much on a single mitigation. To borrow your examples: - we don't rely on safety belts alone to reduce injuries: we augment that control with more engineering controls, regulations, and education. - we don't rely on gun safeties alone to reduce injuries: we augment that control with more engineering controls, regulations, and education. For obvious reasons, I think regulation or mandatory education would be impractical for this situation. Because other engineering domains, including the ones you mentioned, rely on complementary controls to achieve further safety, I speculated that fuzz testing and deterministic simulation testing could be effective potential complementary controls. Property testing could be another. I make this argument because I work as a computational statistician with software engineers in a large software company and I see variations on the theme of these bugs on a weekly basis. The usual justification I get is "I know that (insert library implementation) exists but I thought what I wrote was a simpler version of the same thing, and then I have fewer dependencies", as if equivalence of function were self-evident. It's not, and sometimes I can persuade the engineer to use the library from first principles, but generating witnesses violating the properties of the object they're computing tends to be more compelling, and generalizable strategies for testing tend to get more buy-in because the value-add is not limited to statistical applications.

• ketzu · 31 minutes ago

  I wonder how much of the problem is how randomness is usually taught it encountered. Most cases I have seen is a version of srand(time(NULL)); int r = rand(); Most people think "I understand this and I can use this" and just throw on top whatever they need beyond that. I was most people too.

• truekonrads · 15 minutes ago

  PRNG is the answer, if you want over a set of small numbers (say a 100) to get a nice distribution of your choice , then you shouldn’t use a RNG, you should generate the desired points on the curve and then shuffle them (or use deterministic code to that effect). A true RNG can output any numbers and only over a large set of numbers the distribution would be uniform.

I think this is interesting theory and fun to read about. If I was actually working with cryptography this would seem immensely important. I would also be arguing vehemently online about the std implementation of Mersenne twister and worrying about people analyzing bulk traffic with advanced scripts scraping a hundredth of a bit per sample. But, I make games.

The blog post doesn't mention the term, but what it describes is commonly known as a "modulo bias" in cryptography. See also: https://romailler.ch/2020/07/28/crypto-modulo_bias_guide/