2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – idmean
    Aug 3 at 6:46
  • $\begingroup$ @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}$ $\endgroup$ Aug 3 at 6:59
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, accepted the answer $\endgroup$ Aug 3 at 7:16
-4
$\begingroup$

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”.

$\endgroup$
1
  • 2
    $\begingroup$ "In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) 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." - Wikipedia, source: en.wikipedia.org/wiki/With_high_probability $\endgroup$
    – nir shahar
    Aug 4 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.