A type of stochastic jump process

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.