4
$\begingroup$

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

$\endgroup$
3
  • 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$ Dec 22, 2010 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, 2011 at 14:20
  • $\begingroup$ @Probabilist: Are you still waiting for another aswer to this question? $\endgroup$
    – Did
    Feb 15, 2011 at 13:53

3 Answers 3

3
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What if $K$ = a\mu for some large positive constant $a$? $\endgroup$ Dec 22, 2010 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, 2010 at 2:24
  • $\begingroup$ Sorry, should be $(K/M_{k-1})$ and $K=k^3M_{k-1}$, of course. $\endgroup$
    – fedja
    Dec 22, 2010 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, 2010 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, 2010 at 16:03
2
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Dec 22, 2010 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, 2010 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$ Dec 23, 2010 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$ Jan 4, 2011 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, 2011 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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