Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to generate random variates from a truncated geometric distribution over the interval $[0, n)$ with specified expected value, $0 \le E < n$. The obvious way to do this seems to be to sample the exponential distribution over the same interval and round down to the nearest integer, but I've run into some technical difficulties, in (what I believe to be) decreasing order of seriousness:

  1. I don't know how to truncate the distribution except by rejection sampling, but I cannot do that, because the surrounding code requires a constant-time operation.

  2. I'm not confident that rounding an exponential variate down to the nearest integer gives the proper distribution of integers.

  3. The obvious way to generate an exponential variate over $[0, n)$ in constant time is inverse transform sampling: $T = -E \log U$ where $E$ is the expected value and $U$ is a uniform variate over $(0, 1]$. However, on a real computer (using IEEE doubles for all calculations), this will not generate variates larger than $744.44E$, because $U$ cannot be smaller than approximately $5\times 10^{-324}$. In my application, the desired upper limit $n$ might be quite large. I'm not sure this is a problem, since variates larger than $744.44E$ should appear less than once in $2 \times 10^{323}$ trials, but I can't convince myself it's genuinely not a problem.

  4. When $E=0$, the above equation always evaluates to zero. Is that the correct behavior?

share|improve this question
1  
By "exponentially-distributed integer" do you mean something like a (conditional) geometric random variate? –  cardinal Jan 10 '12 at 0:13
    
Yes, I believe I do mean that. I wasn't aware it existed, and the Wikipedia page is unenlightening on how to generate variates, alas. –  zwol Jan 10 '12 at 0:27
1  
There are multiple ways to generate a geometric random variate. The easiest constant-time algorithm is to take an exponential random variable and truncate it to its integer part. But, I think you first need to precisely define the distribution from which you want to sample. Only then will it be possible to give a precise answer. :) –  cardinal Jan 10 '12 at 0:33
    
@cardinal: Edited to clarify, I hope. –  zwol Jan 10 '12 at 0:57

1 Answer 1

up vote 3 down vote accepted

I'm assuming that $E$ is the expected value of the full geometric distribution, not of the truncated one. You've used $E$ for the expected value of both the geometric distribution and the exponential distribution; since they need to be slightly different, I'll use $E'$ for the expected value of the geometric distribution.

  1. You can truncate the distribution by restricting $U$ to a range such that $T\in[0,n)$; that is, $U$ should be uniformly distributed in $(\mathrm e^{-n/E},1]$.

  2. It does if you choose the right parameter. The area under each interval of length $1$ of the continuous distribution is larger by a factor of $\mathrm e^{-1/E}$ than the one to the right, so the expected value of the geometric distribution you get will be $E'=\mathrm e^{-1/E}/(1-\mathrm e^{-1/E})=1/(\mathrm e^{1/E}-1)$. Thus, given $E'$, you can determine $E$ as $E=1/\log(1+1/E')$.

  3. As you wrote, this is quite unlikely to be a problem in your lifetime or anyone else's.

  4. Yes. An exponential distribution can only have expected value $0$ if it's degenerate, a delta distribution at the origin.

share|improve this answer
    
Shouldn't the expected value be more like 0 <= E < n/2 ? –  opt Jan 10 '12 at 1:23
    
@opt: It seems you interpreted $E$ to refer to the expected value of the truncated distribution. I think it was intended to refer to the expected value of the untruncated distribution, though the formulation in the question does suggest your interpretation. In any case, as far as I'm aware my answer doesn't rely on any upper bound on $E$. –  joriki Jan 10 '12 at 2:44
    
This is helpful. I did mean the expected value of the untruncated distribution. One remaining issue: I have a primitive that generates a number uniformly distributed in (0,1] (using the algorithm here: allendowney.com/research/rand ) Since these are floating-point rather than true real numbers, restricting the range of U with the obvious arithmetic will introduce nonuniformity (some values in the restricted range will be more probable than others). I can probably live with that for this application, but do you have any suggestions for avoiding it? –  zwol Jan 10 '12 at 19:32
    
@Zack: That problem will always occur when you use finite-precision arithmetic. Do you have any reason to believe that it will be a particular problem in this case? Note that where the spacing of the values becomes very wide is where they're extremely improbable, so this shouldn't be a problem in itself. –  joriki Mar 21 '12 at 20:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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