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!


1 Answer 1


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?

  • $\begingroup$ 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"? $\endgroup$
    – user208614
    Oct 6, 2019 at 5:14
  • $\begingroup$ 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. $\endgroup$
    – antkam
    Oct 6, 2019 at 17:06

You must log in to answer this question.