Let $X \geq 1$ be a 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)$?

Context: This question is linked to this question

Random walks on graphs: Cover time and blanket time

  • 2
    $\begingroup$ Interestingly, if $X$ are standard normal then, as $K$ goes to infinity, $E[Y_\tau-K]$ approaches $\zeta(1/2)$. This is a well known result in finance used for approximating prices of barrier options. $\endgroup$ – George Lowther Dec 22 '10 at 3:40
  • $\begingroup$ @George: But $\zeta(1/2)$ is negative (and about $-1.46$) while $E[Y_\tau-K]$ is positive for every $K$, so the latter cannot approach the former. Maybe you had a different result in mind? $\endgroup$ – Did Jan 19 '11 at 14:20
  • $\begingroup$ @Probabilist: Are you still waiting for another aswer to this question? $\endgroup$ – Did Feb 15 '11 at 13:53

As mentioned in Shai's answer, this is standard renewal theory. In the limit $K\to+\infty$, the overshoot $Y_\tau-K$ converges in distribution. (For a non asymptotic result, go to the very end of this post.) The most appealing (to me) description of this convergence result is as follows.

First the length $X_{\tau}=Y_{\tau}-Y_{\tau-1}$ of the renewal interval $[Y_{\tau-1},Y_\tau[$ which contains $K$ converges in distribution to the size-biased distribution of the holding times $X$. This means that $X_\tau$ converges in distribution to a random variable $\hat{X}$ whose distribution is characterized by the fact that, for every bounded measurable function $u$, $$ E(u(\hat{X}))=\frac{E(Xu(X))}{E(X)}. $$ Second the location of $K$ in the renewal interval $[Y_{\tau-1},Y_\tau[$ is uniformly distributed.

This shows that the overshoot $Y_\tau-K$ converges in distribution to $U\hat{X}$ where $\hat{X}$ is as above, $U$ is uniform on $[0,1]$ and $\hat{X}$ and $U$ are independent. In particular, $$ \lim_{K\to+\infty}E(Y_\tau-K)=E(U\hat{X})=E(U)E(\hat{X})=\frac{E(X^2)}{2E(X)}, $$ in the usual sense if $X$ is square integrable and in the sense that the limit is $+\infty$ if $X$ is not square integrable.

At least, this is the situation when the holding times $X$ are continuous random variables. Now, I realize that the OP is interested in integer valued holding times, in which case one should assume that $X$ is not restricted to a sublattice of the integers and one should modify the result as follows.

The renewal length $X_\tau$ still converges in distribution to $\hat{X}$ defined as before. (And in the discrete case the distribution of $\hat{X}$ is simply given by $P(\hat{X}=k)=kP(X=k)/E(X)$ for every $k$.) But now the overshoot $Y_\tau-K$ converges in distribution to a random variable $Z$ which is uniformly distributed on the set $\{1,2,\ldots,\hat{X}\}$ conditionally on $\hat{X}$. For instance, $$ \lim_{K\to+\infty}E(Y_\tau-K)=E(Z)=\frac12E(\hat{X}+1)=\frac{E(X(X+1))}{2E(X)}. $$ Finally, a non asymptotic upper bound of the distribution of the overshoot $Y_\tau -K$ is the fact that $$ P(Y_\tau -K=n)\le P(X\ge n), $$ for every $n$ and every $K$. This implies that, for every $K$, $$ E(Y_\tau -K)\le\frac12E(X(X+1)). $$


To get $O(\mu)$ without extra information is not really possible. Take $X$ to be $1$ with probability $1-p$ and $M$ with probability $p$ where $M$ is huge enough so that $EX\approx Mp\gg 1$. Now, if at least one of first $K\ll M$ steps is a huge leap, then the overshot is at least $M-K$ and the probability to have that leap at least once is about $Kp$ for small $p$, so the expectation of the overshot is almost $K$ times larger than the expectation of the step here.

  • $\begingroup$ What if $K$ = a\mu for some large positive constant $a$? $\endgroup$ – Probabilist Dec 22 '10 at 2:08
  • $\begingroup$ No luck here either. Let's say we have $M_k$ with probability $p_k$. To have finite $\mu$, all we need is the convergence of $\sum_k p_k M_k$. Now, the same argument gives the expectation of the overshot at least $(K/M_k)p_k (M_k-K)$. Now, if $M_k=k!^4$, we can take $K=k^3 M_k$ and still get $k^3p_kM_k/2$ for the expectation. But if $M_kp_k=k^{-2}$, this tends to infinity. You need some higher moments to put this under control. $\endgroup$ – fedja Dec 22 '10 at 2:24
  • $\begingroup$ Sorry, should be $(K/M_{k-1})$ and $K=k^3M_{k-1}$, of course. $\endgroup$ – fedja Dec 22 '10 at 2:27
  • $\begingroup$ @fedja: Since (in the original question) $K$ is a fixed integer, we do get $O(\mu)$. So, the first sentence in your answer has probably confused some readers. Note also that your answer corresponds to the upper bound indicated in my answer. $\endgroup$ – Shai Covo Dec 23 '10 at 14:50
  • $\begingroup$ Well, when I have plenty of fixed parameters ($\mu$ is fixed as well) and write $O(\mu)$, I usually mean that the implied constant is absolute. Also, the estimate $\le (K+1)\mu$ is totally trivial (we get an overshot in first $K+1$ steps for sure and each step can add only $\mu$ since the overshot is not greater than the step itself), so I just couldn't imagine that it was what was asked :) $\endgroup$ – fedja Dec 23 '10 at 16:03

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

EDIT: 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)$.

EDIT: Elaborating on the relation to the framework of renewal theory.

For completeness and for general purposes, let us consider the problem in the (more general) setting of renewal theory. For this purpose, we replace $Y$ by $S$, in accordance with the common notation used in renewal theory. Henceforth we suppose that $X_i$ are i.i.d. non-negative rv's with mean $\mu > 0$, and set $S_n = \sum\nolimits_{i = 1}^n {X_i }$. For $t \geq 0$ real, we set $\tau_t = \inf \{ n : S_n > t \}$ (thus further generalizing the case considered in the question). We now introduce the stochastic process $N = \lbrace N_t : t \geq 0 \rbrace$, defined by $N_t = \sup \{ n:S_n \le t\}$. The counting process $N$ is called a renewal process. The key observation is that $\tau_t$ and $N_t$ are related by $\tau_t = N_t + 1$. (Note that thus $N_t + 1$ is a stopping time for the $X_i$.) Thus, $S_{\tau _t } = S_{N_t + 1}$. This corresponds to $Y_\tau$ of the original question, upon letting $t=K$. However, in accordance with the common notation used in renewal theory, we shall use $Y$ for the following random variable: we define $Y_t = S_{N_t + 1} - t$. The random variable $Y_t$ is called the excess at $t$ of the renewal process $N$. Thus, $Y_t = S_{\tau _t } - t$, and so (by letting $t=K$) this corresponds to the random variable denoted $Y_\tau - K$ in the original question. Hence, as it turns out, the OP actually considered the expectation of the excess at $K$ of a renewal process with inter-arrival times distributed according to the distribution of the $X_i$.

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

  • $\begingroup$ Shai, thanks for this very nice answer. I am not familiar with renewal theory (my user name is somewhat ironic), but if for my purposes I am happy to let K→∞, then m(K)∼K/μ and so $E(Y_\tau)\sim (1+K/\mu)\mu= O(K)$ when $K>\mu$. This would solve the related problem that I posted here mathoverflow.net/questions/50137/… when we allow the cover time C (which is equivalent to K here) to go to ∞, which of course, is the case for for all graphs as their size goes to $\infty$. $\endgroup$ – Probabilist Dec 22 '10 at 22:48
  • $\begingroup$ @Probabilists: Did you write $m(K) \sim K/\mu$? I see $m(K)-K/\mu$. As for renewal theory, it is a standard topic in probability courses, and you can very easily learn it. $\endgroup$ – Shai Covo Dec 23 '10 at 0:44
  • $\begingroup$ Yes, I wrote $m(K) \sim K/\mu$. The ASCII characters look fairly clear on my screen, but I will make a point to use Latex in future. $\endgroup$ – Probabilist Dec 23 '10 at 0:58
  • $\begingroup$ If $n\rightarrow \infty$ and $\mu=\mu(n)\rightarrow \infty$ as $n\rightarrow \infty$ and $\omega=\omega(n)\rightarrow \infty$ as $n\rightarrow \infty$ , then can we say, by rescaling that $\lim_{n\rightarrow \infty}\frac{m(\omega\mu)}{\omega\mu} = \frac{1}{\mu}$ and thus $m(\omega\mu)\sim \omega$? Intuitively this would make sense, but seems a little too easy $\endgroup$ – Probabilist Jan 4 '11 at 14:14
  • $\begingroup$ Since in the original case $\mu$ is fixed, we cannot simply say that $m(\omega \mu)\sim \omega$ as $n \to \infty$ (especially if $\mu > \omega$). Using simulations, you can try to figure out what is the asymptotic behavior of $m(\omega \mu)/ \omega$. $\endgroup$ – Shai Covo Jan 4 '11 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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