5
$\begingroup$

I've been 'playing about' with pseudo random generators in C#, while studying Algorithms (Sedgewick & Wayne). I've noticed that the BCL Random class generates distributions in a 'half-open' way .. [min, max) .. that is the returned value is always greater than or equal to min and less than (but not equal to) max. This seems very common across programming languages. When I look at the StdRandom Java code the Gaussian distribution (for one) seems to forget this open upper bound when doing it's calculation. Admittedly, the difference is very small. Probabilities range from 0 to 1 [0,1], there is some possibility of 'epic fail' (0) and absolute success (1). It seems odd to me that so many various probability distribution functions use (or depend on) the open range which excludes 1.

At the same time I can't imagine a bunch of smart people just chose to implement in this way based on tradition or convenience. Does anyone know the statistical reasoning behind using the half open range [0,1) rather than the close range [0,1] when implementing probability functions dependent on randomly generated values?

Update 20Sept2015

I appreciate Creosote answer, but I had previously considered these reasons and rejected them.

  1. Loop endpoints: When generating random ints this might be useful, but even then it would be easy to transform or request the appropriate endpoint. When using a double and you wanted an open endpoint you would actually want the possibility of 1.0 to produce the correct (maximum) open loop endpoint. In the end I don't see that generating loop endpoints as a major use case in determining API behavior.

  2. Binary range representations: Most methods I've seen that generate doubles don't use the full range of the double they simple take a 32 unsigned int and divide it by 2^32 (actually they usually multiple by the reciprocal of 2^32, but that's an implementation detail). I quite easily wrote a function that takes 50 random bits and divides by (2^50 - 1) to give the 0.0 to 1.0 range. Fifty bits was as large as I could go and still see the change from a one bit difference.

I read the blog about the value of half-open ranges and it makes sense in allowing for a null range representation. However, this doesn't seem to apply when considering a probability distribution. I've also read an argument suggesting that the range [0,0.5) and [0.5,1) represent equal partitions. However, if I look at it as a discrete number of bits (lets say 3 for example), then there is an equal distribution between 000-011 and 100-111. These can be easily mapped to a 0.0-1.0 value (by dividing by 111), but the partitions would be [0.0,0.5) and [0.5,1.0] ... or alternately [0.0,0.5] and (0.5,1.0] neither is symmetric. The symmetry argument is interesting but am not sure I find it convincing given the purpose of generating a probability is to generate a value in the [0,1] range.

Trying to update this question I ran across another wrinkle that plays into the symmetry argument. Consider (this is C#, via scriptcs):

> uint.MaxValue /2.0
2147483647.5

Note that dividing MaxValue by 2.0 results in a fractional value, but if these values are being generated using ints, then:

> 2147483647/(double)uint.MaxValue
0.499999999883585
> 2147483648/(double)uint.MaxValue
0.500000000116415

There is no discrete value that results in exactly 0.5 (because (2^n)-1 is always odd, and prime for n = 2, 3, 5, 7, 13, 17, 19, 31... see Mersenne Primes). Experimenting I found that at the point where n = 50, FP rounding causes the value (((2^n)-1)/2)/(2^n)-1) to equal 0.50. This problem can be eliminated
by dividing by 2^n-2 rather than 2^n-1, but that makes generation a bit more complicated. I suppose it's useful that a [0,1] distribution be able to generate a .5 exactly, if for no other reason that to not have to explain the vagaries of computer math.

I'm still not sure why the chosen range is generally [0,1) and would still love to know if anyone can explain either the reasoning or history.

Update 08Aug2023

This may be the first time I've updated an eight year old question :-) Thank you logitude.

I had to reconstitute my 'headspace' from 2015 and think about this a bit. I believe logitude is correct, but I'd like to expand on the answer here for anyone finding this in the future.

I was looking for a deeper reason for the random function returning an open interval. Specifically, I was thinking in terms of a probability value. In that context, both 0 and 1 are useful values. The [StdRandom] link reinforces this thinking by providing a variety of statistical distributions. However, I think logitude is correct in thinking that these random() functions are not specifically designed for generating a probability value, but instead designed to make generation of random integer values easy. This also explains why so many of these restrict themselves to 32 bit ranges. Consider

If I build my random generator using 32 bit values, ideally, I can create a distribution from 0...4294967295 (4294967296 values) that can be mapped (by division by 4294967295) into a real range of 0.0...1.0 . If people need integer values they can just use the integer random generator to get those. Then "people" come along and say hey I need to generate a 1...20 value for my D&D group day job. "No problem" you say just divide by 4294967296, multiply by 20 and add 1. "Huh?" where'd that 4294967296 come from ... is it a constant? Hmmm, maybe I isolate (hide) that 4294967296, cause maybe it will change at some point ... thus (in my imagination) the "random" function is born, not as a way to produce a probability, but as a way to generate integer sequences without exposing too many underlying details. Yes, that's just speculation.

So why are we still using it. Why not have better generators or API's? We do, but the it works and has a long tail. PRNGs aren't easy to get right and while there are several good ones that will generate random bits (that you can string together into 64 or more bit values), you end up having to explain computer floating point to people. "Yes, I know doubles are 64 bits in length, but you can't use all the bits for precision" ... "oh, sure I understand, how many bytes in a bit again?" ... . So simple pattern and you don't have to explain probability or FP'ing to others.

There are cracks in the system. The (generic) current mapping is something like this: use a 32-bit int generator and division by 4294967296 to produce a range of 0.0...0.999999999767169. With real numbers $0.\overline{9}$ is exactly 1.0, what's a bit of rounding among friends. Do a little rounding magic and you get something close "1.0" when you need it. The better your "rounding magic" the less bias your "1.0" will be, but most of the time it won't make a big difference. The problem is you are using the function for probability, when it was likely designed for integer generation. That's not to say you can't use the "floaty bits" directly, only that rounding or truncating might produce an unintentional bias. FP already has a bias toward values expressible as sums of powers of 2 ;-)

Now if you need some "big" randoms, you can take the output of your 32-bit random function and multiply it by 2^60 (for example) and easy peasy you are lemon squeezy. Except not quite. You really aren't going to get a good distribution. You can only generate 2^32 distinct values but you are trying to map them to more than that. Don't worry nobody will notice and truly for many things it won't make a noticeable difference. It will be technically wrong, but close enough and you won't have to listen to anyone explain discrete math (which is very hard).

TLDR; I think the premise of my question is wrong. The expectation that these functions were meant to be used as probability distributions is flawed. I believe their primary use is (somewhat paradoxically) for generating integer sequences, from integer based PRNGs. The open range a convenience ... "it's a feature not a bug".

$\endgroup$
2
  • 3
    $\begingroup$ In theory, sampling uniformly from [0,1] and [0,1) is equivalent in distribution, since P(X = 1) = 0 in both cases. But I don't know why they would chose half open range in practice. $\endgroup$
    – Cliff AB
    Sep 19, 2015 at 17:33
  • $\begingroup$ I should think RNG designers went through your 50-bit experiment too. This is only conjecture, but consider: (1) dividing by $2^{50}-1$ and rounding down leaves a gap at 0.1111...1 which, as statisticians concerned with tails of distributions, is probably not where we want the error to creep in; (2) there's an interpretability issue with methods other than shift-and-truncate, i.e. other than divide by $2^n$, which makes the precise handling of the result rather awkward -- where exactly was the gap again? -- so simplicity is the better choice. $\endgroup$
    – Creosote
    Sep 21, 2015 at 6:12

2 Answers 2

1
$\begingroup$

Consider writing a program to simulate the result of rolling a 6-sided die. If your programming API does not offer a random-number-generator function that returns an integer, but does offer one that returns a floating-point value with a uniform distribution in $[0.0,1.0)$, then the way to get a uniformly-distributed integer in $[1,6]$ is with code of the form

pips = floor(random() * 6) + 1

If random() were ever to return 1.0, then your program would roll a 7.

$\endgroup$
6
  • $\begingroup$ If this were a closed range you would write "pips = floor(random() * 5) + 1". It seems you are asserting the consequence. You write the code the way you do because the random() function returns a half open range. If it returned a closed range you would write different code. The question is why. Does discrete mathematics favor an open range, or was it just an arbitrary coding decision that became a pseudo-standard? $\endgroup$
    – Dweeberly
    Aug 21, 2023 at 21:43
  • $\begingroup$ No, if the range were closed, then pips = floor(random() * 5) + 1 would only roll a 6 with infinitesimal probability. $\endgroup$
    – Logitude
    Aug 22, 2023 at 3:54
  • $\begingroup$ You are correct. You might even be 'right', see update in question. Either way you win the point :-) $\endgroup$
    – Dweeberly
    Aug 22, 2023 at 20:37
  • $\begingroup$ Thanks. I landed here because I wanted a seeded, random-integer function in JavaScript, and it has neither. Numbers in JavaScript are (64-bit IEEE 754) floats that happen to be integers sometimes. I would much rather have an API for an integer PRNG, but I wouldn't be surprised if it ended up being implemented with floats under the hood, even in other languages. $\endgroup$
    – Logitude
    Aug 22, 2023 at 21:31
  • $\begingroup$ You may have already seen this, but SO has a thread on that stackoverflow.com/questions/424292/…. $\endgroup$
    – Dweeberly
    Aug 23, 2023 at 0:01
7
$\begingroup$

There are probably basically two reasons.

  1. Programmers are used to writing loops like for (i=0; i<20; i++) or for j in range(20) where the start is included and endpoint excluded. So it feels natural that random(a,b) should include a but exclude b. (Of course there are exceptions, like R.)

  2. Floating point numbers are represented on a computer as $u\times 2^v$ (plus a sign bit) for integers $u$ and $v$, e.g. see here. Random numbers in $[0,1)$ are easy to generate: just grab 52 (say) random bits for $u$, and have $v=-52$. Random numbers in $[0,1]$ would be harder: how would you convert the random bits to floating-point format?

$\endgroup$
3
  • $\begingroup$ 2. seems like a very reasonable answer to me (and I did up vote), but 1. seems less likely to me; the for loop written still would examine the $20^{th}$ element of a vector in C++ (as indexed by myVec[i]), for example. $\endgroup$
    – Cliff AB
    Sep 19, 2015 at 19:15
  • 1
    $\begingroup$ I appreciate that, thanks. For tangentially-related, Pythonic, arguments that "half-open is good" see a blog and, specifically for random number generation, stackoverflow. $\endgroup$
    – Creosote
    Sep 19, 2015 at 19:25
  • $\begingroup$ Very interesting! Almost all the algorithms I've ever written involve keeping track of a stochastic number of indices (and occasionally subsetting them) and the nuisances they discuss have long bugged me! $\endgroup$
    – Cliff AB
    Sep 19, 2015 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.