5
$\begingroup$

Suppose I have a sequence of $i.i.d$ random variables: $X_1,X_2,... \sim Geom(p)$. That means that each of the $X_i$'s is holding an unknown random number of trials until a 'success'.

Since $0<p<1$, we know that $X_i$ has a finite expectation $\mathbb{E}[X_i] = \frac{1}{p}$, which also means that there exists an integer $N \in \mathbb{N}$ such that: $$N = \displaystyle \min_{n\in \mathbb{N}}\Big\{X_1+X_2+...+X_n= \sum_{i=1}^{n}{X_i\geq5000}\Big\}$$

We would like to calculate the expectation of this finite integer 'stopping time' $N$. From Wald's lemma:

If $X_i$ are i.i.d. with finite $\mathbb{E}[X_i] = \mu$, and N is a finite stopping time then: $\mathbb{E}\Big[\sum_{i=1}^{N}{X_i}\Big] = \mu\mathbb{E}[N]$.

My problem is how to deal with the 'greater-equal' ($\geq$) sign. Since we define $N = \displaystyle \min_{n\in \mathbb{N}}\Big\{\sum_{i=1}^{n}{X_i\geq5000\Big\}}$, this means that $X_N$ contibutes a number of trials with which the sum exceeds $5000$, but we dont know the exact sum.

My intuition is something like: if we take the the sum as the bare minimum, then $$\mathbb{E}\Big[\sum_{i=1}^{N}{X_i}\Big] = 5000= \mathbb{E}[N]\times \frac{1}{p} \to \mathbb{E}[N] = 5000p$$ But even if that's the case I'm having trouble justifying taking the sum as exactly 5000.

Another possible approach is to condition on $\sum_{i=1}^{N}{X_i}=k$ and take the expectation, but $k = 5000, 5001,...$ and I'm not sure how to formulate this, since $k$ is potentially unbounded ($k\in [5000,\infty)$), if that's even a valid approach.

I'd love some guidance please.

$\endgroup$
6
  • $\begingroup$ Are $n$ and $N$ different or the same? Is $N$ the index for which the sum exceeds 5000 or the sum that exceeds 5000? $\endgroup$ Jul 1, 2022 at 9:53
  • $\begingroup$ Please check my edit. BTW, if we do it for $2$ instead of $5000$ then we get $P(N=1)=1-p$ and $P(N=2)=p$ so that $\mathbb EN=1+p\neq2p$. $\endgroup$
    – drhab
    Jul 1, 2022 at 10:05
  • $\begingroup$ @cookiemonster - $N$ is the index for which the sum first exceeds 5000, the stopping time $\endgroup$
    – Avi P
    Jul 1, 2022 at 10:15
  • 1
    $\begingroup$ I take back what I said earlier : this may generally come under renewal theory, but the memoryless property will give you a recursion for $N_{x}$ ,where $x$ is the threshold ($5000$ in your case). If you replace the geometric random variable by something non-memoryless like the uniform, then you could use renewal theory to solve this question. $\endgroup$ Jul 1, 2022 at 10:20
  • $\begingroup$ @SarveshRavichandranIyer - can you please elaborate how the memorylessness property is used in this case? I'd like to get the logic, so I can justify my movements clearly $\endgroup$
    – Avi P
    Jul 1, 2022 at 10:24

3 Answers 3

5
$\begingroup$

I reached the same conclusion as Henry (+1) in a more roundabout manner. What follows is the gist of my thoughts:

Recall that a geometric random variable models the number of independent Bernoulli trials until a success occurs. Hence to every realization of a geometric random variable we can canonically associate a realization of a string of Bernoulli random variables. For example, let $X_1,\dots, X_{20}$ be a sequence of geometric random variables and $\omega$ be such that the $(X_1(\omega),\dots,X_{20}(\omega))$ is equal to $(6, 3, 2, 12, 1, 17, 1, 1, 1, 1, 2, 2, 3, 6, 1, 2, 1, 4, 5, 3)$. To this realization we can associate the following realization of a string of Bernoulli random variables:

$00000100101000000000001100000000000000001111101010010000011011000100001001$

Where $1$ denotes success. Note that the number of $1$'s in this string is equal to the number of geometric random variables. We are interested in the minimal number of geometric random variables (the minimal number of $1$'s) such that the string up to and including the last $1$ has length $\geq 5000$. Consider the first $5000$ entries in the string. Clearly, the number of $1$'s in the first $5000$ entries (or trials) can be written as a binomial random variable.

Let $Y$ denote the number of $1$'s in the first $5000$ entries of the random string that is obtained from the geometric random variables as described above. $Y$ is a random variable and we have $Y\sim \text{Bin}(5000,p)$. Denote by $Y_{5000}$ the outcome of the $5000$'th Bernoulli trial.

Claim. We have the following equality

$$N=Y \mathbf{1}({Y_{5000}=1})+(Y+1) \mathbf{1}(Y_{5000}=0), \qquad (1)$$

where $\mathbf{1}()$ is an indicator function. In particular, $$\mathsf E(N) = 4999p+1.$$

Proof. The reasoning is as follows. Consider the first $5000$ trials. Either we have a success on the $5000$'th trial, in which case we have that exactly $Y$ geometric RV have been added up to reach $5000$, and hence $N=Y$; or we do not have a success on the 5000'th trial. In this case we have to wait until the next success occurs for the current geometric RV, which will add $1$ to the tally of $Y$. So in this case we must have $N=Y+1$.

Rewriting $(1)$ as

$$N=Y+\mathbf{1}(Y_{5000}=0).$$

And taking expectations gives the result.
$\square$

$\endgroup$
6
  • $\begingroup$ Perfect, this is kind of what I would have wanted to write as well. The "claim" captures the memoryless nature of $N$. $\endgroup$ Jul 1, 2022 at 11:19
  • 1
    $\begingroup$ (+1) I would plead for $N=Y+1$ where $Y$ denotes the number of successes in the first $4999$ trials. A bit less cumbersome. $\endgroup$
    – drhab
    Jul 1, 2022 at 17:28
  • 1
    $\begingroup$ @drhab more elegant for sure and I see how one could immediately come to that expression. $\endgroup$
    – user18214
    Jul 1, 2022 at 18:08
  • 1
    $\begingroup$ Great and very insightful answer! I have made a few small edits in order to avoid confusion of the word "realization" as you used it with the common usage of this word. I have also renamed $X_{5000}$ to $Y_{5000}$ since it could otherwise be confused with the $5000$'th geometric random variable. Cheers $\endgroup$ Jul 2, 2022 at 9:56
  • 1
    $\begingroup$ I had a feeling I was being sloppy with realizations/random variables. Appreciate your thorough edits @MaximilianJanisch! $\endgroup$
    – user18214
    Jul 2, 2022 at 10:21
4
$\begingroup$

Geometric distributions have the memorylessness property, which makes this much easier if you regard it as a sequence of attempts stopping with the first success at $5000$ or more attempts.

You can calculate the expected value of the number of attempts when you stop: once you have reached $4999$ attempts (it does not matter how many of these were successes or not), you expect $\frac1p$ more attempts until you stop, making the expected value of the sum $$\mathbb{E}\left[\sum\limits_{i=1}^{N}{X_i}\right]=4999+\frac1p$$

This makes the expected number of successes when you stop $$\mathbb{E}[N]=\dfrac{4999+\frac1p }{\frac1p} = 4999p+1$$

$\endgroup$
2
  • $\begingroup$ thank you for your answer. When I read it it makes sense, but can you please clarify how the memorylessness of the distribution is helping? Do you mean that because of the memorylessness I dont mind if the $j^{th}$ element of $X_i$ was a 'fail' or a 'success' as long as I did not yet reach 5000 trials? $\endgroup$
    – Avi P
    Jul 1, 2022 at 10:21
  • $\begingroup$ @AviP - essentially that. When you get to $4999 $ trials, what happens next (and so decides the value of the sum when you stop) does not depend on what has already happened either getting towards the boundary or earlier - you could not use this argument if your $X_i$ was say a six-sided-dice throw as how you cross $5000$ does matter, but you could use this argument if $X_i$ has an exponential distribution (using $5000$ rather than $4999$) as that does have the memoryless property $\endgroup$
    – Henry
    Jul 1, 2022 at 10:31
3
$\begingroup$

We can also calculate $\mathsf E(N)$ directly. We let $\mathbb N=\mathbb Z_{\ge 1}$ and assume that $(X_n)_{n\in\mathbb N}$ is a sequence of iid random variables such that $\mathsf P(X_1 = m) = p (1-p)^{m-1}$ for some $p\in[0,1]$ and all $m\in\mathbb N$.

For $x\in\mathbb N$, let

$$N_x=\min\left\{n\in\mathbb N:\sum_{i=1}^{n}{X_i\geq x}\right\}.$$

Then

\begin{equation*}\begin{split} \mathsf E(N_x) &=\sum_{r=1}^\infty \mathsf P(N_x\ge r) \\ &=1+\sum_{r=2}^\infty \mathsf P\left(\sum_{m=1}^{r-1}X_m<x\right)\\ &= 1+\sum_{r=2}^\infty\sum_{l=r-1}^{x-1} \binom{l-1}{r-2} p^{r-1} (1-p)^{l-r+1} \\ &=1+\sum_{l=1}^{x-1}\sum_{r=2}^{l+1} \binom{l-1}{r-2} p^{r-1} (1-p)^{l-r+1} \\ &=1+\sum_{l=1}^{x-1}p\sum_{r=0}^{l-1}\binom{l-1}{r} p^r (1-p)^{l-1-r} \\ &=1+\sum_{l=1}^{x-1} p (p+(1-p))^{l-1} \\ &= 1 + p(x-1). \end{split}\end{equation*}


Comments on equalities:

  1. Layer cake representation;
  2. We have $N_x\ge r$ iff $\sum_{m=1}^{r-1} X_m<x$;
  3. See How to compute the sum of random variables of geometric distribution;
  4. Re-arranging terms (can be justified with Fubini+counting measure but I expect there to also be an easier justification that I am too lazy to come up with);
  5. Changing index $r-2\to r$;
  6. Binomial Theorem;
  7. Direct simplification.

Setting $x=5000$ gives the special case $\mathsf E(N)=4999 p +1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .