6
$\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)$".

$\endgroup$
4
$\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$).

$\endgroup$
  • $\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 '14 at 10:07
  • 2
    $\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 '14 at 16:40
  • $\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 '14 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 '15 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 '15 at 18:48

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.