

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


