# Product and sum of big $O_p$ random variables

I seems that people often use the following properties $$O_p(a_n)O_p(b_n) = O_p(a_nb_n)$$ and $$O_p(a_n)+O_p(b_n) = O_p(a_n+b_n)$$. I'm wondering, if these are true for any sequences $$a_n,b_n$$. The reason I ask is that in textbooks, I've only saw $$O_p(n^\alpha)O_p(n^\beta) = O_p(n^{\alpha+\beta})$$ and $$O_p(n^\alpha) + O_p(n^\beta) = O_p(n^{\max\{\alpha,\beta\}})$$. My first question is how to show this for such particular choice of $$a_n,b_n$$. The second question, whether the this is true at the general level.

I know that $$X_n=O_p(x_n)$$ if and only if $$\forall\varepsilon,\exists M<\infty$$ such that $$P(|X_n/x_n|>M)<\varepsilon,\forall n\geq 1$$ but I fail to proceed from here.

Update: I show that $$O_p(a_n) + O_p(b_n) = O_p(a_n+b_n)$$. Let $$X_n = O_p(a_n)$$ and $$Y_n = O_p(b_n)$$. Then $$\forall\varepsilon>0,\exists M_x,M_y$$ such that $$$$P\left(\left|\frac{X_n}{a_n}\right|>M_x\right) < \varepsilon/2,\qquad P\left(\left|\frac{Y_n}{b_n}\right|>M_y\right) < \varepsilon/2$$$$ Now let $$M_{xy} = M_x+M_y$$, then \begin{aligned} P\left(\left|\frac{X_n+Y_n}{a_n+b_n}\right|>M_{x,y}\right) & = P\left(\left|\frac{X_n+Y_n}{a_n+b_n}\right|>M_{x,y}, \left|\frac{X_n}{a_n+b_n}\right|>M_x\right) + P\left(\left|\frac{X_n+Y_n}{a_n+b_n}\right|>M_{x,y}, \left|\frac{X_n}{a_n+b_n}\right|\leq M_x\right) \\ & \leq P\left(\left|\frac{X_n}{a_n+b_n}\right|>M_x\right) + P\left(\left|\frac{Y_n}{a_n+b_n}\right|>M_y\right) \\ \end{aligned} and so we need $$a_n,b_n$$ to be positive in order to conclude that $$$$|a_n| \leq |a_n+b_n|$$$$

If $X_n=O_p(a_n)$ and $Y_n=O_p(b_n)$, this means that we can choose $M_X$ and $M_Y$ such that $$P(|X_n/a_n|>M_X)<\epsilon/2\\ P(|Y_n/b_n|>M_Y)<\epsilon/2$$

Your statement is that $X_nY_n=O_p(a_nb_n)$. Consider this product and let $M_{XY}=M_XM_Y$. Then we want to show:

$$P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}\right)=P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}, \left|\frac{X_n}{a_n}\right|\leq M_X\right)+P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}, \left|\frac{X_n}{a_n}\right|>M_X\right)<\epsilon$$ For the first term, $$P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}, \left|\frac{X_n}{a_n}\right|\leq M_X\right)\leq P\left(\left|\frac{M_Xa_nY_n}{a_nb_n}\right|>M_{XY}\right)=P\left(\left|\frac{Y_n}{b_n}\right|>\frac{M_{XY}}{M_X}\right)=P\left(\left|\frac{Y_n}{b_n}\right|>M_Y\right)<\epsilon/2.$$ For the second term, $$P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}, \left|\frac{X_n}{a_n}\right|>M_X\right)\leq P\left( \left|\frac{X_n}{a_n}\right|>M_X\right)<\epsilon/2.$$ So together you get that $$P\left(\left|\frac{X_nY_n}{a_nb_n}\right|>M_{XY}\right)\leq P\left(\left|\frac{Y_n}{b_n}\right|>M_Y\right)+P\left( \left|\frac{X_n}{a_n}\right|>M_X\right)<\epsilon.$$

For addition, use the definition and go from there.

First, let us assume that $a_n$ and $b_n$ are both positive. This makes it easier, but it is not particularly restrictive. If $X_n$ is $O_p(a_n)$, that is the same as saying that $X_n/a_n$ is uniformly tight. If $X_n/a_n$ is uniformly tight, then obviously $-X_n/a_n$ must also be. So the results for positive sequences can be directly translated to negative sequences (but for the $O_p$ statements, we have absolute values, so for that it would not matter).

Again, we have $$P(|X_n/a_n|>M_X)<\epsilon/2\\ P(|Y_n/b_n|>M_Y)<\epsilon/2.$$ We now want to show $$P\left(\left|\frac{X_n+Y_n}{a_n+b_n}\right|>M_{XY}\right)\leq P\left(\left|\frac{X_n}{a_n+b_n}\right|>M_{XY}/2\right)+P\left(\left|\frac{Y_n}{a_n+b_n}\right|>M_{XY}/2\right)\\ =P\left(\left|\frac{X_n}{a_n}\right|\left|\frac{1}{1+\frac{b_n}{a_n}}\right|>M_{XY}/2\right)+P\left(\left|\frac{Y_n}{b_n}\right|\left|\frac{1}{1+\frac{a_n}{b_n}}\right|>M_{XY}/2\right)\\ \leq P\left(\left|\frac{X_n}{a_n}\right|>{M_{XY}}/{2}\right)+P\left(\left|\frac{Y_n}{b_n}\right|>M_{XY}/2\right)\\ <\epsilon/2+\epsilon/2=\epsilon.$$ Here, letting $M_{XY}=2*\max(M_X, M_Y)$ would put you on the safe side.

The more common statement of the rule is, however, $O_p(a_n)+O_p(b_n)=O_p(a_n)$ if $a_n$ is of higher (or equal) order compared to $b_n$. For example, if $a_n=n^2$ and $b_n=n$, then $O_p(n^2+n)$ is a bit redundant and $O_p(n^2)$ is enough. Formulating it in this way (i.e. when $|a_n|$ is of higher (or the same) order than (as) $|b_n|$, it is easier to show:

$$P\left(\left|\frac{X_n+Y_n}{a_n}\right|>M_{XY}\right)\leq P\left(\left|\frac{X_n}{a_n}\right|>M_{XY}/2\right)+P\left(\left|\frac{Y_n}{a_n}\right|>M_{XY}/2\right)\\ \leq P\left(\left|\frac{X_n}{a_n}\right|>M_{XY}/2\right)+P\left(\left|\frac{Y_n}{b_n}\right|>M_{XY}/2\right)\\ <\epsilon/2+\epsilon/2=\epsilon.$$

• So for addition, the restriction is that $a_n,b_n$ are positive sequences? – Lionville Oct 10 '15 at 9:06
• @Lionville no. Start like I did, writing down the inequalities for X and Y. Then start looking at them together, and apply the triangle inequality. Then you get X and Y by themselves and then you can go from there. Give it a try and see where you end up. – hejseb Oct 10 '15 at 9:37
• I did it, but I'm still not sure if we can have it with negative $a_n,b_n$. – Lionville Oct 10 '15 at 11:04
• @Lionville I have edited my post. I don't think that matters much. – hejseb Oct 10 '15 at 15:28
• thanks a lot for explanation. BTW, is the proof that I wrote using your first proof correct? – Lionville Oct 11 '15 at 9:43

By the triangle inequality,

$$\Vert X_n + Y_n\Vert \le \Vert X_n \Vert + \Vert Y_n \Vert$$

Now, suppose that $$a_n,b_n > 0$$.

We want to show that for an arbitrary $$\varepsilon > 0$$ and large enough $$t,N > 0$$ then $$P(\Vert X_n + Y_n \Vert > (a_n + b_n)t) < \varepsilon$$ for all $$n \ge N$$. For $$t > 0$$,

\begin{align} P(\Vert X_n + Y_n \Vert > (a_n + b_n)t) &\le P(\Vert X_n\Vert + \Vert Y_n \Vert > (a_n + b_n)t) \\ & \le P\left(\left\{\Vert X_n\Vert > a_n t \right\}\bigcup\left\{\Vert Y_n \Vert > b_n t\right\}\right) \\ &\le P\left(\Vert X_n\Vert > a_n t) + P\left(\Vert Y_n \Vert > b_n t\right\}\right) \\ & \end{align}

The second inequality (Event Subset) is the key point that drives the result. We want to show that $$\Vert X_n\Vert + \Vert Y_n \Vert > (a_n + b_n)t$$ implies that either $$\Vert X_n \Vert > a_n t$$ or $$\Vert Y_n \Vert > b_nt$$. This is easy to show by contradiction. Suppose that $$\Vert X_n \Vert \le a_n t$$ and $$\Vert Y_n \Vert \le b_n t$$. That would imply that $$\Vert X_n\Vert + \Vert Y_n \Vert \le (a_n + b_n)t$$, a contradiction.

This form is convenient because it allows us to analyze each random variable separately. Our objective is to show that we can make the right-hand side arbitrarily small. I fill in some of the technical details to complete the proof below.

Since $$X_n = O_p(a_n)$$ and $$Y_n = O_p(b_n)$$, then there exists constants $$(t_X,t_Y,N_X,N_Y)$$ such that $$P(\Vert X_n \Vert > a_n t_X) \le \varepsilon / 2$$ for all $$n \ge N_X$$ and $$P(\Vert Y_n \Vert > b_n t_Y) \le \varepsilon / 2$$ for all $$n \ge N_Y$$. Choose $$t^* = \max\{t_X,t_Y\}$$ and $$N^* = \max\{N_X,N_Y\}$$. Then,

$$P(\Vert X_n \Vert > a_n t^*) \quad \le \quad P(\Vert X_n \Vert > a_n t_X) \quad \le \varepsilon /2 \quad \forall n \ge N^* \ge N_X$$

$$P(\Vert Y_n \Vert > b_n t^*) \quad \le \quad P(\Vert Y_n \Vert > b_n t_Y) \quad \le \varepsilon /2 \quad \forall n \ge N^* \ge N_Y$$

Therefore, $$P(\Vert X_n + Y_n \Vert > (a_n + b_n)t^*) \quad \le \varepsilon/2 + \varepsilon/2 \quad = \varepsilon \quad \forall n \ge N*$$

This shows that $$X_n + Y_n$$ is $$O_p(a_n + b_n)$$.