I have two sequences of random variables which are bounded in probability, denoted as $X_n=\mathcal{O}_p(\sqrt{n})$ and $Y_n=\mathcal{O}_p(\lVert\theta\rVert)$, where $\lVert\theta\lVert=\sum_{i=1}^n\theta_i^2$ with $\theta_i \in \mathbb R$. I would like to show that $X_n+Y_n$=$\mathcal{O}_p(\sqrt{n+\lVert\theta\rVert^2})$. Typically, when adding 'big O' terms, the dominant one would be all that remains. However, since $\lVert\theta\rVert$ depends on the sample size $n$, it is not clear in this case which term dominates. The definition of bounded in probability tells us that
$X_n=\mathcal{O}_p(a_n)$ if for all $\varepsilon>0$ there exists a constant $M_\varepsilon>0$ and an integer $N_\varepsilon>0$ such that $$P\left(\biggr\lvert\frac{X_n}{a_n}\biggr\lvert\geq M_\varepsilon\right)\leq\varepsilon \text{ for all } n\geq N_\varepsilon$$
Here is what I have tried to show so far. I am mostly having issues with stating the right conditions. We have that for all $\varepsilon>0$, there exists $M_1>0$ and $N_1>0$ s.t. $P\left(\biggr\lvert\frac{X_n}{\sqrt{n}}\biggr\lvert\geq M_1\right)\leq\varepsilon \text{ for all } n\geq N_1$. Similarly, for all $\varepsilon>0$, there exists $M_2>0$ and $N_2>0$ s.t. $P\left(\biggr\lvert\frac{Y_n}{\sqrt{\lVert\theta\rVert^2}}\biggr\lvert\geq M_2\right)\leq\varepsilon \text{ for all } n\geq N_2$. Note that $\{|X_n+Y_n|>M\} \subset \{|X_n|\geq M/2\}\cup \{|Y_n|\geq M/2\}$ and hence $P(|X_n|+|Y_n|>M)\leq P(|X_n|\geq M/2)+P(|Y_n|\geq M/2).$ Then we can write
\begin{align}
P\left(\biggr\lvert\frac{X_n+Y_n}{\sqrt{n+\lVert\theta\rVert^2}}\biggr\lvert> M\right)&\leq P\left(\biggr\lvert\frac{X_n}{\sqrt{n+\lVert\theta\rVert^2}}\biggr\lvert+\biggr\lvert\frac{Y_n}{\sqrt{n+\lVert\theta\rVert^2}}\biggr\lvert> M\right)\\
&\leq P\left(\biggr\lvert\frac{X_n}{\sqrt{n+\lVert\theta\rVert^2}}\biggr\lvert> \frac{M}{2}\right)+P\left(\biggr\lvert\frac{Y_n}{\sqrt{n+\lVert\theta\rVert^2}}\biggr\lvert> \frac{M}{2}\right)\\
&\leq P\left(\biggr\lvert\frac{X_n}{\sqrt{n}}\biggr\lvert> \frac{M}{2}\right)+P\left(\biggr\lvert\frac{Y_n}{\sqrt{\lVert\theta\rVert^2}}\biggr\lvert> \frac{M}{2}\right)
\end{align}
I would like to say that the last part $\leq \frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon \text{ for all } n \geq N$, but I'm not sure what conditions I need on $M$, $N$, and $\varepsilon$ to make this true. It has been a while since I've done a real analysis course and I am not very familiar with asymptotics. I would appreciate any help!
Best Answer
You have the right idea but just got a little confused, because there are actually three different $\epsilon$'s involved.
You want to prove: $\forall \epsilon_1> 0, \exists M_1 > 0, \exists N_1 > 0$ s.t. some condition (on $X+Y$) holds.
You are given that: $\forall \epsilon_2> 0, \exists M_2 > 0, \exists N_2 > 0$ s.t. some condition (on $X$) holds.
You are also given that: $\forall \epsilon_3 > 0, \exists M_3 > 0, \exists N_3 > 0$ s.t. some condition (on $Y$) holds.
I like to think of these as a game with an adversary.
The adversary is giving us $\epsilon_1$, and we have to find $M_1, N_1$.
To help us do that, we have a magic black box, where we can put in $\epsilon_2, \epsilon_3$ and the magic box gives us $M_2, N_2, M_3, N_3$.
So the trick is to turn the adversary's $\epsilon_1$ into $\epsilon_2, \epsilon_3$, get the $M_2, N_2, M_3, N_3$ from the magic box, and combine them somehow into $M_1, N_1$ to show the adversary.
In this case what you need is: $\epsilon_2 = \epsilon_3 = \frac12 \epsilon_1$. So you have:
$\forall n > N_2: P(|X_n | / \sqrt{n} > M_2) < \epsilon_1 /2 $
$\forall n > N_3: P(|Y_n | / ||\theta|| > M_3) < \epsilon_1 /2 $
Now you need to combine $M_2, M_3$ into an $M_1$, and $N_2, N_3$ into an $N_1$, s.t. you have the following:
$N_1$ is gonna be $\max(N_2, N_3)$, obviously, or else the conditions on $X_n$ and $Y_n$ individually won't even apply. Can you see what $M_1$ you need?