I want to generate some random variable $X$, with $0 \leq X \leq H$ for some maximum value $H$ (programatically, if that matters) such that $P(X=1) = p$, $P(X=2)= p^2$, $P(X=3)=p^3$, etc.
$P(X=k) = p^k$.
For example, this can be done (with $p=0.5$) in C code:
int foo() {
int x = 0;
while(boolean_coin_flip() && x <= H) x++;
return x;
}
Is there a way to generate this random variable in constant time?