Big O almost surely

Question

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.

Answer 1

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.

Answer 2

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|<M_{\omega}$ 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.