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.
Best Answer
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).