Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf $P_{X,Y}$. $X_n,Y_n$ have the following properties: \begin{align} 0 < \mathbb{E}[X_n]=\mu_X, \quad 0 < \mathbb{E}[Y_n]=\mu_Y,\quad |X_n/\mu_X| \leq K_X \text{ and } |Y_n/\mu_Y| \leq K_Y \end{align} for finite $K_X,K_Y$. The stopping time $\tau(t)$ is given by \begin{align} \tau(t) = \min(n \geq 0: U_n/\mu_X \geq t, V_n/\mu_Y \geq t) \end{align}

I am looking for an upper bound for $E[\tau(t)]$ that captures the asymptotic behavior as $t\rightarrow \infty$. I hope for an upper bound similar to \begin{align} E[\tau(t)] \leq t + \frac{1}{\sqrt{2\pi}} \sqrt{\text{Var}\left(\frac{X_1}{\mu_X} - \frac{Y_1}{\mu_Y}\right)}\sqrt{t} + \mathcal{O}(1), \end{align} as simulations suggest. However, a higher constant in front of $\sqrt{\text{Var}\left(\frac{X_1}{\mu_X} - \frac{Y_1}{\mu_Y}\right)}\sqrt{t}$ or faster growing remainder terms are also sufficient, i.e. $\mathcal{O}(t^{1/4})$ instead of $\mathcal{O}(1)$ is fine.

In the one-dimensional cases, with stopping times $ \tau_1(t)=\min(n\geq 0: U_n/\mu_X \geq t)$, $\tau_2(t)=\min(n\geq 0: V_n/\mu_Y \geq t)$ and $\tau_{12}(t)=\min(n \geq0 : \frac{1}{2}(U_n/\mu_X + V_n/\mu_Y) \geq t)$, the following bounds hold \begin{align} \mathbb{E}[\tau_1(t)] &= \mathbb{E}[U_{\tau_1(t)}/\mu_X] \leq \mu_X t + K_X\\ \mathbb{E}[\tau_2(t)] &= \mathbb{E}[V_{\tau_2(t)}/\mu_Y] \leq \mu_Y t + K_Y,\\ \mathbb{E}[\tau_{12}(t)] &= \frac{1}{2}\mathbb{E}[U_{\tau_{12}}/\mu_X+V_{\tau_{12}(t)}/\mu_Y] \leq t + \max(K_X,K_Y), \end{align} for $t > 0$, where the equalities follow from Wald's equality and the inequalities follow since $X_n$ and $Y_n$ are bounded.

Partial Solution

My main idea is to write the stopping time $\tau(t)$ in two terms; the time until $\frac{1}{2}(U_n/\mu_X + V_n/\mu_Y)$ hits the boundary $t$ plus the time until $U_n$ hits the boundary $\mu_X t$ starting from $U_{\tau_{12}(t)}$ or $V_n$ hits the boundary $\mu_Y t$ starting from $V_{\tau_{12}(t)}$: \begin{align} \mathbb{E}[\tau(t)] &\stackrel{(a)}{\leq} \mathbb{E}[\tau_{12}(t) + \tau_1(t-U_{\tau_{12}(t)}/\mu_X)+\tau_2(t-V_{\tau_{12}(t)}/\mu_Y)]+\mathcal{O}(1)\\ &\leq t +\mathbb{E}\left[1\{U_{\tau_{12}(t)}\leq \mu_X t\}\left(t- U_{\tau_{12}(t)}/\mu_X\right)\right]\nonumber\\ &\quad+\mathbb{E}\left[1\{V_{\tau_{12}(t)}\leq \mu_Y t\}\left(t- V_{\tau_{12}(t)}/\mu_Y\right)\right]+\mathcal{O}(1)\\ \end{align} However, I have not been able to come up with an argument for whether/under what conditions (a) is true, since the random variables $X_n$ and $Y_n$ are allowed to take negative values. My main concern is that $U_n$ may have decreased below $\mu_X t$ when $V_n$ hits the boundary $\mu_Y t$ or visa versa.

Assuming that (a) is correct, I was able to obtain the bound \begin{align} \mathbb{E}[\tau(t)] \leq t+ \frac{1}{2}\sqrt{\text{Var}\left(\frac{X_1}{\mu_X} - \frac{Y_1}{\mu_Y}\right)}\sqrt{t}+\mathcal{O}(t^{1/4}), \end{align} which is sufficient for my application.

For more details, see link.

Any suggestions or ideas are appreciated.

  • $\begingroup$ From what you wrote in the end, it looks like you are primarily interested in the asymptotic behavior as $t\to+\infty$. Is this correct? $\endgroup$
    – fedja
    May 27, 2014 at 4:19
  • $\begingroup$ Thanks. That is correct in the sense that I am interested in the dominating term of $\text{E}[\tau(t)]$ when $t\rightarrow \infty$ and then bound the remaining terms using Big-Oh. I have edited the question to emphasize what kind of result I hope for. $\endgroup$
    – Kasper
    May 27, 2014 at 10:00

1 Answer 1


Note that
$$\mathbf E[\tau(t)]=\sum_{j=0}^\infty \mathbf P(\tau(t)>j)\le t+1+\sqrt{t}+\sum_{j=[t+\sqrt{t}]+1}^\infty \mathbf P(\tau(t)>j).$$ To bound the sum we use $\{\tau(t)>j\}\subset \{U_j<t\mu_X\mbox{ or } V_j<t\mu_Y\} $. Therefore, $$ \mathbf P(\tau(t)>j)\le \mathbf P(U_j<t\mu_X)+\mathbf P(V_j<t\mu_Y) $$ Now we can use the fact that $X_i$ and $Y_i$ are bounded and apply Hoeffding's inequality (https://en.wikipedia.org/wiki/Hoeffding%27s_inequality), which gives for $j>t$, $$ \mathbf P(U_j<t\mu_X)=\mathbf P(U_j-j\mu_X<(t-j)\mu_X)\le \exp\left(-\frac{2(t-j)^2\mu_X^2}{4j(\mu_XK_X)^2}\right) =\exp\left(-\frac{(t-j)^2}{2j(K_X)^2}\right), $$ where I used the condition $|X_n|\le K_X\mu_X$. Similarly, $$ \mathbf P(U_j<t\mu_X)\le\exp\left(-\frac{(t-j)^2}{2j(K_Y)^2}\right), $$ Then, $$ \mathbf E[\tau(t)]\le t+1+\sqrt{t}+\sum_{j=[t+\sqrt{t}]+1}^\infty \left(e^{-\frac{(j-t)^2}{2j(K_Y)^2}}+e^{-\frac{(j-t)^2}{2j(K_X)^2}}\right) $$

Now note that for $j\ge t+\sqrt{t}$ we have the following estimate $j\le (j-t)\sqrt{t}$, which implies that $$ \sum_{j=[t+\sqrt{t}]+1}^\infty \left(e^{-\frac{(j-t)^2}{2j(K_Y)^2}}+e^{-\frac{(j-t)^2}{2j(K_X)^2}}\right)\le \sum_{j=[t+\sqrt{t}]+1}^\infty \left(e^{-\frac{(j-t)}{2(K_Y)^2\sqrt{t}}}+e^{-\frac{(j-t)}{2(K_X)^2\sqrt{t}}}\right) $$ Now the latter sum is simply a sum of geometric series. Hence, $$ \mathbf E[\tau(t)]\le t+1+\sqrt{t}+\frac{1}{1-e^{-\frac{1}{2(K_X)^2\sqrt{t}}}} +\frac{1}{1-e^{-\frac{1}{2(K_Y)^2\sqrt{t}}}} $$ and finally, $\mathbf E[\tau(t)]\le t+2(1+K_X^2+K_Y^2)\sqrt{t}$ for large $t$.

The constant in front of $\sqrt{t}$ is not sharp.

In principle, it is possible to obtain the exact behaviour $\mathbf E[\tau(t)]=t+A\sqrt t +o(\sqrt t),\quad t\to\infty$ and identify $A$. I will briefly sketch how it can be done.

As above, it is sufficient to obtain asymptotics for $\mathbf P(\tau(t)>j)$. For $j\ge 2t$ this probability will be exponentially decreasing and contribution to $\mathbf E[\tau(t)]$ is negligible. Then, for $j\le 2t$ we can use strong coupling of $(U_j,V_j)$ with 2d Brownian motion $(U(t),V(t))$. Brownian motion $(U(t),V(t))$ should have the same drift and covariance as corresponding random walk. Then strong coupling ensures that with high probability the distance between random walk and Brownian motion is less than $\log(t)$ for $j\le 2t$. Then, on the latter event, $$ \tau^{BM}(t-\log t)\le \tau(t)\le \tau^{BM}(t+\log t), $$ where $\tau^{BM}(t)$ is the corresponding exit time for the Brownian motion. Therefore, it is sufficient to show for the Brownian motion that $\mathbf E[\tau^{BM}(t)]t+A\sqrt t +o(\sqrt t)$. Now this can be done as follows a) we change the measure to remove the drift of the Brownian motion b) we do a linear transformation to remove correlation between coordinates to obtain standard 2d Brownian motion. Now the question can be treated as a question about the exit time of the sBM from a cone. For that we can use information about $\mathbf P(\tau>t, (U(t),V(t))\in dy))$ available in Brownian motion in cones (doi:10.1007/s004400050111).


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.