# Calculating $\mathbb{E}[N]$ for $N = \displaystyle \min_{n\in \mathbb{N}}\Big\{\sum_{i=1}^{n}{X_i\geq5000\Big\}}$, using Wald's lemma

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, 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.

• Are $n$ and $N$ different or the same? Is $N$ the index for which the sum exceeds 5000 or the sum that exceeds 5000? Jul 1, 2022 at 9:53
• 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$. Jul 1, 2022 at 10:05
• @cookiemonster - $N$ is the index for which the sum first exceeds 5000, the stopping time Jul 1, 2022 at 10:15
• 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. Jul 1, 2022 at 10:20
• @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 Jul 1, 2022 at 10:24

## 3 Answers

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$$

• Perfect, this is kind of what I would have wanted to write as well. The "claim" captures the memoryless nature of $N$. Jul 1, 2022 at 11:19
• (+1) I would plead for $N=Y+1$ where $Y$ denotes the number of successes in the first $4999$ trials. A bit less cumbersome. Jul 1, 2022 at 17:28
• @drhab more elegant for sure and I see how one could immediately come to that expression. Jul 1, 2022 at 18:08
• 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 Jul 2, 2022 at 9:56
• I had a feeling I was being sloppy with realizations/random variables. Appreciate your thorough edits @MaximilianJanisch! Jul 2, 2022 at 10:21

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$$

• 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? Jul 1, 2022 at 10:21
• @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 Jul 1, 2022 at 10:31

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

Comments on equalities:

1. Layer cake representation;
2. We have $$N_x\ge r$$ iff $$\sum_{m=1}^{r-1} X_m;
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$$.