# Big O almost surely

I came across the following: Let $Z_n$ be some sequence of random variables defined on a probability space $(\Omega, F, P)$ and suppose $$P(Z_n > n^{-1/2}(x+12*log(n))) \leq \exp(-x/6)$$ for all $x>0$. The author then claims that this implies $Z_n \overset{a.s}{=}O(n^{-1/2} \hspace{1mm} log(n))$.

First, what does it mean precisely that $Z_n\overset{a.s}{=}O(n^{-1/2} \hspace{1mm} log(n))$? For a given $\omega\in\Omega$ , it would mean that there exist some constant $C$ and $n_0$ such that if $n>n_0$ we have $\frac{Z_n(\omega)}{n^{-1/2}log(n)}\leq C$. I was thinking that since these constants $C$ may be different for different $\omega$, we define $Z_n\overset{a.s}{=}O(n^{-1/2} \hspace{1mm} log(n))$ as $$P(\limsup_{n \to \infty} \frac{Z_n}{n^{-1/2}log(n)}< \infty)=1$$

But then I don't know how to proceed to show the claim made above, assuming that my definition makes sense to begin with.

• this must a.s. be a mistake. from the exponential inequality it follows that $Z_n = O_p(n^{-1/2}\log(n))$. For my part, I can't even make sense of the statement $Z_n \stackrel{a.s.}{=}O(n^{-1/2}\log(n))$. Apr 24, 2018 at 7:27
• The problem is that this notation is used throughout the entire book. Also, could you show how you derive that $Z_n=O_{p}(n^{-1/n} log(n))$? Apr 24, 2018 at 10:31
• I do not know if you are still interested, but he is establishing an almost sure convergence and providing the rate that it occurs. He said that the limit superior of the random variable divided by $n^{-1/2}log n$ is bounded with probability one. This result is stronger than convergence in probability, as answered below. Apr 23, 2020 at 2:28

I don't know the notation they used and never encountered it. There should be at least some definition of $Z_n \stackrel{a.s.}{=}O(a_n)$ given in the book.

However, I can show that $Z_n$ is bounded in probability by $n^{-1/2}\log(n)$, i.e. $Z_n=O_p(n^{-1/2}\log(n))$, provided the results leading to your exponential inequality can also be applied for $-Z_n$, i.e. you have in fact $P(|Z_n| > n^{-1/2}(x+12\log(n))) \leq 2 \exp(-x/6)$.

Given

\begin{align}\label{1} P(|Z_n| > n^{-1/2}(x+12\log(n))) \leq 2\exp(-x/6), \end{align}

We have to show that for all $\epsilon>0$ there exists a constant $M_{\epsilon}$ such that $$P(|Z_n/(n^{-1/2}\log(n))|> M_{\epsilon}) < \epsilon$$ for all sufficiently large $n$.

Chose some $\epsilon>0$. There then exists a corresponding $0<x_\epsilon<\infty$ such that \begin{align} P(|Z_n|>n^{−1/2}(x_\epsilon+12\log(n)) &\leq \exp(-x_\epsilon/6)<\epsilon\\ \Rightarrow P(|Z_n|>n^{−1/2}(x_\epsilon+12\log(n)) & < \epsilon\\ \Rightarrow P(\left|Z_n/(n^{-1/2}\log(n))\right|>(x_\epsilon/\log(n)+12)& < \epsilon. \end{align} Now, observe that as $n\to \infty$, the right hand side in the probability term $(x_\epsilon/\log(n)+12)$ is a strictly decreasing sequence and converges from above to the value 12, hence there clearly exists a constant $M_\epsilon$ such that $M_\epsilon \geq (x_\epsilon/\log(n)+12)$ for all sufficiently large $n$. We hence have $$P(\left|Z_n/(n^{-1/2}\log(n))\right|>M_\epsilon) \leq P(\left|Z_n/(n^{-1/2}\log(n))\right|>x_\epsilon/\log(n)+12) < \epsilon.$$ since $\epsilon$ was arbitrary the assertion follows immediately.

I would define the a.s. order $$a_n\stackrel{a.s.}{=}O(b_n)$$ as $$P(a_n=O(b_n))=1$$, equivalently $$P\left[\limsup_{n\to\infty}\left|\frac{a_n}{b_n}\right|<\infty\right]=1,$$ equivalently, for almost every $$\omega$$ there exist finite $$M_{\omega}$$ and $$N_{\omega}$$ such that $$|a_n/b_n| for all $$n>N_\omega$$.

To prove the claim, given that you don't specify anything about the structure of the sequence over $$n$$ (eg, not independent), we probably need to use something like the Borel-Cantelli lemma to go from probability statements for a single $$n$$ to statements for the whole sequence. [There aren't that many other ways to do it, and if it is something else it will take more work than I have time for right now]

We'll need to replace $$x$$ by an increasing sequence $$x_n$$. An obvious sequence to try is $$x_n=\log n$$, which puts us right at the boundary of $$O(n^{-1/2}\log n)$$. I'm going to write $$g_n(x) = n^{-1/2}(x+12\log n)$$ because it's less annoying.

Substituting in, we get $$P(Z_n>g(x_n))<\exp(-x_n/6)=\exp(-(\log n)/6)=n^{-1/6}$$ That's not very helpful: the sum of those exceedance probabilities is infinite. But we could try $$A\log n$$ for some fixed $$A$$ $$P(Z_n>g(x_n))<\exp(-x_n/6)=\exp(-(A\log n)/6)=n^{-A/6}$$ If $$A=12$$, the exceedance probability is $$n^{-2}$$ and $$\sum_n P(Z_n>g(x_n))<\sum_n n^{-2}<\infty$$ so $$P(Z_n>g(x_n)\textrm{ i.o.})=0$$ by the Borel-Cantelli lemma. Does that help?

$$P(Z_n>g(x_n))= P(Z_n> n^{-1/2}(x_n+12\log n))=P(Z_n> n^{-1/2}(12\log n+12\log n))$$ And if $$P(Z_n> n^{-1/2}(24\log n)\textrm{ i.o.})=0$$ then $$P\left( Z_n=O(24n^{-1/2}\log n) \right)=1$$ and we are done.

Well, almost done. You'd normally want a matching lower bound for order notation, so

• $$Z_n$$ are non-negative
• An equivalent bound applies to $$-Z_n$$
• The author is using $$O()$$ notation in a non-symmetric way
• or something is wrong.