Is there a way generate a random variable this way in constant time?

41 Views Asked by At

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?