With high probability

Last updated

In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making n big enough.

Contents

Applications

The term WHP is especially common in computer science, in the analysis of probabilistic algorithms. [1] For example, consider a certain probabilistic algorithm on a graph with n nodes. If the probability that the algorithm returns the correct answer is , then when the number of nodes is very large, the algorithm is correct with a probability that is very near 1. This fact is expressed shortly by saying that the algorithm is correct WHP.

Some examples where this term is used are:

See also

References

  1. Mitzenmacher, Michael; Upfal, Eli (2012). Probability and computing: randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press. ISBN   978-0-521-83540-4.