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
\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}
 A: 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)$.
A: 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.
$$
