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.
 A: 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.
A: 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.

