What is With High Probability on Probabilistic Algorithms?

Question

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

• Raphael: Note that randomized and probabilistic algorithms are not the same thing.

Answer 1

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$).

• Raphael: The limit criterion is also called "almost surely". I have seen "high probability" used mostly when referring to probabilities approaching one with exponential rate.
• Yuval Filmus: 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.
• Raphael: 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.
• Erel Segal-Halevi: 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..
• Yuval Filmus: 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".

Answer 2

I have seen multiple definitions of "with high probability".

Let $P = (P_n)_{n \in \mathbb N}$ be a sequence of real numbers in the unit interval $[0,1]$. These represent the probability that an event happens, dependent on some $n \in \mathbb N$. We say that $P$ happens with high probability if and only if, depending on your definition:

• "$P_n$ approaches 1ドル$" (as per French Wikipedia)

  • 1ドル-P_n \in O(g(n))$ for some nonnegative function $g$ with $\lim_{n \to \infty} g(n) = 0$

    This is equivalent to $\lim_{n \to \infty} P_n = 1$, I am just writing it in this way to make it more similar to the other definitions

• "$P_n$ approaches 1ドル$ polynomially with noninteger exponents allowed" (sorry I don't know the right term for this) (as per another answer for your question)
  • 1ドル-P_n \in O(\frac 1 {n^\alpha})$ for some (real-valued) $\alpha > 0$
• "$P_n$ approaches 1ドル$ linearly"
  • 1ドル-P_n \in O(\frac 1 {n})$
• "$P_n$ approaches 1ドル$ significantly faster than linearly" (as per this paper)
  • 1ドル-P_n \in o(\frac 1 n)$
• "$P_n$ approaches 1ドル$ superpolynomially" (as per DISCO of ETH Zuerich)
  • 1ドル-P_n \in O(\frac 1 {n^r} )$ for all $r \in \mathbb N$

I think the last definition is the one you are looking for, it seems to most fit the sloppily written definition which you mentioned. It is also the most common definition I have seen.

---

Notes

• I believe a lot of these discrepancies are due to sloppy definitions and bad copying. Indeed, I believe another answer for your question posted here also misunderstood the meaning of $\alpha$.

• I have also seen:

  $P_n \in O(\frac{1}{n^\alpha})$ for some $\alpha \in \mathbb N$.

  But this is just equivalent to $P_n \in O(\frac{1}{n})$ (or actually $P_n \in O(1)$ if 0ドル \in \mathbb N$, which wouldn't make sense). It seems like an instance of bad copying.

• If you are intuitively confused by Big-$O$ notation for things getting smaller rather than bigger, we can also write $\frac{1}{1-P_n} \in \Omega(h(n))$ instead of 1ドル-P_n \in O(\frac{1}{h(n)})$. This $h(n)$ is then what I refer to as "linearly" if $h(n) = n$, or "superpolynomially" if $h(n)$ can be any polynomial (any $n^\alpha$), etc.

  • Since we are talking about "faster than" etc., and we are with regards to the terms "linearly", "polynomially" etc. actually talking about $\Omega$-asymptotes, and not $O$-asymptotes, really, you can see how "for some polynomial" doesn't make sense, since faster than "some polynomial" means faster than the "smallest" polynomial, which can mean linear polynomial, or even a constant or even zero.