w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that:

Assuming we have 4 cases as bellow, and we can use $\delta$ to replace $1/n$, then $O(\log(n))=O(\log(1/\delta))$

case 1. ERROR is upper bounded by $O(n)$ with probability $1-\exp^{-n}$;

case 2. ERROR is upper bounded by $O(n)$ with probability $1-n^{-1}$;

case 3. ERROR is upper bounded by $O(n)$ with probability $1-n^{-1/3}$;

case 4. ERROR is upper bounded by $O(n)$ with probability $1-1/\log^{n}$.

In above cases, all the probabilities turns to be $1$ as $n$ increases, which are all w.h.p.(based on the above definition wiki). But in practice, case 1 is the most efficient result, case 2 and 3 can be acceptable, while case 4 seems to has no practical meaning.

So, it seems we cannot use 'w.h.p.' to persuade other people to believe that the related (randomized) algorithms and theoretical guarantee can work well in practice?

OR, can we have a rigorous definition for 'w.h.p.'?

  • 4
    $\begingroup$ When I read "with high probability" in a TCS paper without further explanation, I assume it means with probability greater than 2/3. This is usually used for classes with amplification, where you can make the error probability as small as you like by repeating the algorithm several times. $\endgroup$ Jun 24, 2015 at 15:54
  • 3
    $\begingroup$ The Wikipedia definition you give, "with high probability" defined as $1 - o(1)$, probability that goes to 1 as n goes to infinity, is precise. The examples you give all meet this definition, but are more specific. $\endgroup$ Jun 24, 2015 at 17:25
  • 4
    $\begingroup$ I think this question is not research level. Yes, sometimes we pick definitions that mostly correspond to practice, but not quite. The overriding concern is that definitions are clean and have clean consequences. You could have exactly the same concern about the definition of PTIME. If an algorithm makes $n^{100}$ steps and yet is in PTIME, how could being in PTIME be a guarantee that an algorithm works well in practice? Yet, PTIME is cool because it composes nicely, and mostly corresponds to practical algorithms. $\endgroup$ Jun 25, 2015 at 6:43
  • 4
    $\begingroup$ I have voted to close this question, as not being "research level". A question such as this about bounding error would be better suited to CS.SE. $\endgroup$ Jun 25, 2015 at 7:29


Your Answer

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