Let $X$ be a non-negative integer-valued random variable with probability mass function $f(k)=P(X=k)$ for $k=0,1,2,\ldots$ Define a function $h(r) = P(X=r | X \geq r)$. Let $U_i$ for $i=0,1,2,\ldots$ be a sequence of i.i.d. random variable uniformly distributed over $[0,1]$.

Find the distribution of $Z=\min \{n: U_n \leq h(n) \}$.


For every $k\geqslant0$, $P(Z=k)=P(X=k)$. Actually, this is a well known procedure to simulate any given distribution on the nonnegative integers using an i.i.d. sequence of uniform random variables on $[0,1]$.

Hint: For every $n\geqslant0$, $1-h(n)=P(X\geqslant n+1\mid X\geqslant n)=\dfrac{P(X\geqslant n+1)}{P(X\geqslant n)}$ hence, for every $k\geqslant0$, the identity $$ [Z\geqslant k+1]=\bigcap_{n=0}^k[U_n\gt h(n)] $$ implies that, by independence of $(U_n)$, $$ P(Z\geqslant k+1)=\prod_{n=0}^k(1-h(n))=\prod_{n=0}^k\frac{P(X\geqslant n+1)}{P(X\geqslant n)}=P(X\geqslant k+1). $$

  • $\begingroup$ Oh dear, i can see how works... I am trying to delete my answer but it wouldn't let me. $\endgroup$ – Lost1 Jan 23 '14 at 12:14
  • $\begingroup$ Why would people use this scheme rather than inverse transformation? Am i correct to think think it is faster if the rv takes small values with high probability when it can take a large number of values? $\endgroup$ – Lost1 Jan 23 '14 at 12:22
  • $\begingroup$ I'm havin trouble seeing how this works. Can someone elaborate? $\endgroup$ – Wintermute Jan 23 '14 at 19:51
  • $\begingroup$ mtiano "Someone"? What do you mean? $\endgroup$ – Did Jan 23 '14 at 20:05
  • 1
    $\begingroup$ @Lost1 This scheme could be used with profit each time the ratios P(X>n+1)/P(X>n) have a simpler form than the raw probabilities P(X=n). Actually the inverse transformation method is often the least effective of all. $\endgroup$ – Did Feb 8 '14 at 7:50

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.