1
$\begingroup$

I have the following code for simulating a geometric random variable where $X \sim \text{Geometric}(p)$, $0 \leq p \leq 1$, and pmf is $p(n) = (1 - p)^np$:

  1. Set $X = 0$.
  2. Generate $U \sim \text{Uniform}(0,1)$.
  3. If $U \leq (1-p)$ set $X = (X + 1)$ and return to (2).
  4. Else return $X$,

Obviously this is an inefficient approach to say generating one with, $\lfloor \text{ln}(U) / \text{ln}(1 - p)\rfloor$, since a small $p$ rarely goes through multiple iterations.

My question: With a simulation in R, I can calculate an estimated number of times we will loop through for a $p$. But I would like to have an actual equation to which I can calculate the expected number for any arbitrary $p$ to compare with more efficient algorithms.

How do I go about calculating this? Obviously, $E(U)=.5$, do we need to condition this on $1−p$?

$\endgroup$
3
  • 1
    $\begingroup$ What is your question? $\endgroup$ Sep 28, 2017 at 7:12
  • $\begingroup$ Apologies, updated. $\endgroup$
    – jj8989
    Sep 28, 2017 at 7:15
  • 3
    $\begingroup$ The number you're generating is geometric. The number of times you add 1 to the count before you stop and output your geometric value is therefore ... geometric, so your question is just "What's the mean of a geometric(p)?" ... en.wikipedia.org/wiki/Geometric_distribution (see the sidebar on the left near the top) $\endgroup$
    – Glen_b
    Sep 28, 2017 at 7:43

1 Answer 1

1
$\begingroup$

We are just simulating geometric distribution that starts from $0$.

When we simulate $U ~\sim \operatorname{Uniform}(0,1)$ and compare the value with $1-p$, it is equivalent to tossing a coin with probability of tail being $1-p$ where we view probability of obtaining a head as the success event. Note that we have $Pr(U \leq 1-p) = 1-p$.

The corresponding mean is $\frac{1-p}{p}$.

Edit:

The expected number of rounds that is required is $\frac{1-p}{p}+1=\frac1p$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.