I must prove that the following algorithm returns Poisson distributed numbers $k$.
algorithm poisson random number (Knuth):
init:
Let L ← e−λ, k ← 0 and p ← 1.
do:
k ← k + 1.
Generate uniform random number u in [0,1] and let p ← p × u.
while p > L.
return k − 1.
I am asked to consider the conditions of the uniformly distributed numbers $u_j$ where the algorithm stops after k iterations. Which I have determined to be:
$$ \prod_{j=0}^{k} u_j \leq e^{-\lambda} $$
Which can then be written:
$$ \sum_{j=0}^{k} \ln{u_j} \leq -\lambda $$
I believe I am then supposed to find the distribution of $\ln u_j$ (using the transformation method maybe?) and combine them using the following lemma stating that the volume of the following set is $\frac{\lambda^n}{n!}$:
$$ \Delta^n = \{(t_1, ..., t_n) \in \mathbb{R}^n | \sum_j t_j \leq \lambda\ and\ t_j \geq 0\ \forall\ j\} $$
I am unsure how to do this despite many attempts and a lot of research, I am very unfamiliar with set theory and its notation and also apparently not as good at probability as I once thought, any help would be appreciated.