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}


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 '15 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 '15 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 '15 at 11:04
  • $\begingroup$ @Lionville I have edited my post. I don't think that matters much. $\endgroup$ – hejseb Oct 10 '15 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 '15 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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