Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X \geq 1$ be an integer r.v. with $E[X]=\mu$. Let $X_i$ be a sequence of iid rvs with the distribution of $X$. On the integer line, we start at $0$, and want to know the expected position after we first cross $K$, which is some fixed integer. Each next position is determined by adding $X_i$ to the previous position. So the question is, if we stop this process after the first time $\tau$ for which $Y_{\tau}=\sum_{i=1}^{\tau}X_i > K$, that is, after the first time it crosses $K$, then what is $E[Y_{\tau}-K]$?. Can we get a bound of $O(\mu)$?

share|cite|improve this question

Let $\tau = \min \{ n \geq 1:X_1 + \cdots + X_n > K \}$. Then $\tau$ is an integer-valued random variable, bounded from above by $K+1$ (since $X_i \geq 1$). Note that $\tau = n$ if and only if $\sum\nolimits_{i = 1}^{n - 1} {X_i } \le K$ and $\sum\nolimits_{i = 1}^{n} {X_i } > K$. Thus, the event $\lbrace \tau = n \rbrace$ depends only on the values $X_1,\ldots,X_n$. So, by definition, $\tau$ is a stopping time with respect to the sequence $X_1,X_2,\ldots$. Now, $X_1,X_2,\ldots$ are i.i.d. with finite expectation $\mu$, and $\tau$ is a stopping time for them. Moreover, ${\rm E}(\tau) < \infty$ since $\tau \leq K+1$. Hence, by Wald's identity, $$ {\rm E}\bigg(\sum\limits_{i = 1}^\tau {X_i } \bigg) = {\rm E}(\tau )\mu \leq (K+1)\mu. $$ So if we put $Y_\tau = \sum\nolimits_{i = 1}^\tau {X_i }$, we get $$ {\rm E}(Y_\tau - K) = {\rm E}(Y_\tau) - K \leq (K+1)\mu - K. $$


Since $\tau \geq 1$, we have $$ \mu - K \leq {\rm E}(Y_\tau - K) \leq (K+1)\mu - K. $$

As we have seen above, the problem reduces to calculating ${\rm E}(\tau)$. Put $S_n = \sum\nolimits_{i = 1}^n {X_i }$ ($S_0 = 0$). Note that $$ {\rm P}(\tau = n) = {\rm P}(S_{n - 1} \le K,S_n > K) = {\rm P}(S_{n - 1} \le K) - {\rm P}(S_n \le K). $$ Hence, $$ {\rm E}(\tau) = \sum\limits_{n = 1}^{K + 1} {n{\rm P}(\tau = n)} = \sum\limits_{n = 1}^{K + 1} n[{\rm P}(S_{n - 1} \le K) - {\rm P}(S_n \le K)] = \sum\limits_{n = 0}^K {{\rm P}(S_n \le K)}. $$ So, we can write $$ {\rm E}(\tau) = 1 + \sum\limits_{n = 1}^\infty {{\rm P}(S_n \le K)} = 1 + \sum\limits_{n = 1}^\infty {F^{(n)}(K)}, $$ where $F^{(n)}$ is the distribution function of $S_n$. For $t>0$ real, define $m(t) = \sum\nolimits_{n = 1}^\infty {F^{(n)}(t)}$. From the theory of renewal processes, we know that $m(t) = {\rm E}(N_t)$, where $\lbrace N_t:t \geq 0 \rbrace$ is a renewal process with inter-arrival times distributed according to the distribution of $X$. $m(t)$ is called the renewal function. It may be worth noting that by the Elementary Renewal Theorem, $$ \mathop {\lim }\limits_{t \to \infty } \frac{{m(t)}}{t} = \frac{1}{\mu }. $$ Returning to our original setting, we have $$ {\rm E}(Y_\tau ) = {\rm E}(\tau )\mu = (1 + m(K))\mu. $$ So, the problem reduces to calculating $m(K)$.

Finally, here is some useful link concerning renewal theory, which is very relevant to this answer.

share|cite|improve this answer
Well done Shai. May I ask what your speciality is? You answer all the probablity and statistics questions with considerable ease, so I guess you are indeed specializing in some statistics or probability research. Is that correct? – Raskolnikov Dec 22 '10 at 15:11
Thanks. I have a PhD in probability; my speciality is probability, in particular stochastic processes (but not statistics), though recently I haven't done much research. – Shai Covo Dec 22 '10 at 16:05
@Raskolnikov: I second Raskolnikov's comment and add that I have very much enjoyed reading Shai Covo's answers to probability and stochastic processes questions. Shai has added a lot to this site, especially in those two areas. – Mike Spivey Dec 22 '10 at 16:33
@Mike: Thanks a lot! Your contribution to this site is very significant as well... – Shai Covo Dec 22 '10 at 16:56
I posted this same question on MO (I am a new user, and didn't realise there were two of these forums - MO seemed more appropriate for this question). You can go here to see the question as well as the context… Thanks again to Shai and the other contributors. – iMath Dec 22 '10 at 23:05

Edit: This answer shows what happens when $X$ could be zero (contrary to the question).

Let $K = 1$, and $X = M$ ($M > 1$) with probability $p$ and $0$ otherwise. Thus $E[Y_\tau - K] = M-1$ whereas $E[X] = pM$. Choosing $M = n+1$ and $p = 1/n(n+1)$ we get $E[X] = 1/n$ and $E[Y_\tau - K] = n$, so a bound of $O(\mu)$ isn't possible.

share|cite|improve this answer
You forgot that $X\geq1$. So X can't take on the value $0$. (Damn, took me a while to figure out. I always thought I found it just to realize I made a mistake.) – Raskolnikov Dec 22 '10 at 13:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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