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

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).$$

• Oh dear, i can see how works... I am trying to delete my answer but it wouldn't let me. – Lost1 Jan 23 '14 at 12:14
• 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? – Lost1 Jan 23 '14 at 12:22
• I'm havin trouble seeing how this works. Can someone elaborate? – Wintermute Jan 23 '14 at 19:51
• mtiano "Someone"? What do you mean? – Did Jan 23 '14 at 20:05
• @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. – Did Feb 8 '14 at 7:50