# Sum of two sequences bounded in probability

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!

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:

• $$\forall n > N_1: P(|X_n + Y_n | / \sqrt{n + ||\theta||^2} > M_1) < \epsilon_1$$

$$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?

• Thank you for the detailed answer! It was very helpful to see it outlined like this. Should I then also choose $M_1=\max(M_2,M_3)$ since the inequality inside the probability term is "greater than"?
– user208614
Oct 6, 2019 at 5:14
• If you look at your own inequalities in the OP, you split $M$ into $M/2, M/2$. Based on this, I would think you need $M_1 = M_2 + M_3$. However, I have not checked everything in detail, so pls take this with a grain of salt. Oct 6, 2019 at 17:06