
> 
> 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](http://kom.aau.dk/~kft/two_dim_rw.pdf).


Any suggestions or ideas are appreciated.



Stopping time of two dimensional random walk
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). 


