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

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

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

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

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

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

<p>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. </p>

<p>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?</p>

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

CC BY-SA 3.0
2015-06-24T15:54:19.297Z
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.
Robin Kothari
CC BY-SA 3.0
2015-06-24T17:25:33.030Z
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.
Huck Bennett
CC BY-SA 3.0
2015-06-25T06:43:53.543Z
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.
Radu GRIGore
CC BY-SA 3.0
2015-06-25T07:29:28.660Z
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.
Niel de Beaudrap
<cc.complexity-theory><linear-algebra><randomized-algorithms><na.numerical-analysis><asymptotics>
the confusion about 'with high probability (w.h.p.)'
olivia
# the confusion about 'with high probability (w.h.p.)'

(Asked by: username_0 on 2015-06-24)

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.'?

**Tags:** cc.complexity-theory, linear-algebra, randomized-algorithms, na.numerical-analysis, asymptotics
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: 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.  

---

## 0 answers

