# Question about "with high probability"

An event that occurs with high probability is one whose probability depends on a certain number $$n$$ and goes to $$1$$ as $$n$$ goes to infinity, i.e. it can be made as close as desired to $$1$$ by making $$n$$ big enough.

I often see that authors tend to try to prove an event $$A$$ happens with high probability by showing that $$Pr(\bar A)\leq \frac{1}{n} \implies Pr(A) \geq 1-\frac{1}{n} \rightarrow 1$$ as $$n$$ tends to infinity.

My question is, what is special about $$\frac{1}{n}$$? What if we prove that $$Pr(\bar A)\leq \frac{1}{\log(n)}$$, would this still count as "with high probability"?

• Since $\log$ is a strictly monotonically increasing function $1-\frac{1}{\log n} \rightarrow 1$ as well for $n$ to infinity. Is this your question? Aug 3 at 6:46
• @idmean I am just asking about the common convention. I know it tends to $1$, but I am wondering if the accepted convention in the community is that the probability should be $\geq 1-\frac{1}{n}$ Aug 3 at 6:59

Yes. The common convension of "with high probability" (that I know of) states that for every $$0\le \delta<1$$, there is some $$n_0$$ such that for $$n>n_0$$ it holds that the probability $$P(A)>\delta$$.
Therefore, showing that $$P(A)>1-\frac{1}{\log(n)}$$ is enough to say that $$A$$ occures with probability $$\rightarrow 1$$, and hence is with high probability.