8
$\begingroup$

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn't get it.

They just said, "Event $E$ occurs with high probability (w.h.p.) if, for any $\alpha\geq1$, there is an appropriate choice of constants for which $E$ occurs with probability at least $1 − O(1/n^\alpha)$".

Something from algorithmist.com didn't help, either.

What is $\alpha$ and what is $1 − O(1/n^\alpha)$? Not understanding this thing make me confused of the analysis of why "With high probability, every search in an $n$-element skip list costs $O(\lg n)$".

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

An event happens with high probability with respect to a parameter $n$ if it happens with probability $p_n$ and $\lim_{n\to\infty} p_n = 1$. Usually the parameter $n$ is clear from the context. In this case, for example, it is probably the number of elements in the list.

The definition of "with high probability" in the lecture notes is even more specific, specifying how fast $p_n$ should converge to $1$: an event happens with high probability if it happens with probability $p_n \geq C/n^\alpha$ for some $C,\alpha>0$. For example, if you choose a random number from $\{0,\ldots,n\}$ then it is non-zero with high probability since the probability that it is non-zero is $1-1/(n+1) \geq 1-1/n$ (so in this case $C=\alpha=1$).

Improve this answer
$\endgroup$
5
  • $\begingroup$ The limit criterion is also called "almost surely". I have seen "high probability" used mostly when referring to probabilities approaching one with exponential rate. $\endgroup$
    – Raphael ♦
    Dec 9, 2014 at 10:07
  • 3
    $\begingroup$ When I see "whp" it is usually synonymous with "almost surely", and when I use it (without defining it) this is always the meaning I refer to. But more generally "whp" could mean either approaching 1, approaching 1 polynomially fast, or approaching 1 exponentially fast. If you use it in any of the latter sense, be sure to define it explicitly. $\endgroup$
    – Yuval Filmus
    Dec 9, 2014 at 16:40
  • 1
    $\begingroup$ Really, you'd call $p_n = 1 - \frac{1}{\log^* n}$ "with high probability"? ;) But yea: to be safe, define what you mean in your context in any case. $\endgroup$
    – Raphael ♦
    Dec 9, 2014 at 17:09
  • $\begingroup$ What is a standard reference (e.g. textbooks) which defines WHP formally? I tried to write an article about WHP in wikipedia en.wikipedia.org/wiki/With_high_probability but it was suggested for deletion because there are no sources, so I am looking for sources.. $\endgroup$
    – Erel Segal-Halevi
    Feb 21, 2015 at 18:21
  • 1
    $\begingroup$ You can check standard complexity and algorithms textbooks. But even if you do find a reference, that's only that particular textbook's usage of the term. It's probably best to just define it explicitly as a common definition without any specific "proof". $\endgroup$
    – Yuval Filmus
    Feb 21, 2015 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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