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.

$\endgroup$
  • 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 '15 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 '15 at 6:12
6
$\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$
  • $\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 '15 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 '15 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 '15 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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