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 \begin{equation} 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 \end{equation} Now let $M_{xy} = M_x+M_y$, then \begin{equation} \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} \end{equation} and so we need $a_n,b_n$ to be positive in order to conclude that \begin{equation} |a_n| \leq |a_n+b_n| \end{equation}


2 Answers 2


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

  • $\begingroup$ So for addition, the restriction is that $a_n,b_n$ are positive sequences? $\endgroup$
    – Lionville
    Oct 10, 2015 at 9:06
  • $\begingroup$ @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. $\endgroup$
    – hejseb
    Oct 10, 2015 at 9:37
  • $\begingroup$ I did it, but I'm still not sure if we can have it with negative $a_n,b_n$. $\endgroup$
    – Lionville
    Oct 10, 2015 at 11:04
  • $\begingroup$ @Lionville I have edited my post. I don't think that matters much. $\endgroup$
    – hejseb
    Oct 10, 2015 at 15:28
  • $\begingroup$ thanks a lot for explanation. BTW, is the proof that I wrote using your first proof correct? $\endgroup$
    – Lionville
    Oct 11, 2015 at 9:43

I will answer your second question about addition.

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.