Question about "with high probability"

Question

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"?

Answer 1

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.

Answer 2

When I’m told “something happens with high probability” I don’t care about a limit, I care whether it’s going to happen or not. Say something happens with probability 1 - 1 / log n. Then if I try 100 n around a billion, the “high probability” will miss 3 of the 100 n.

If you can say with good conscience “if anyone observes this high probability event not happening, then it is most likely due to some hardware defect”, that’s when you can call it “high probability”.