# With high probability

__: Description of limiting behavior in probabilistic algorithms__

**Short description**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.

## Applications

The term WHP is especially used in computer science, in the analysis of probabilistic algorithms. For example, consider a certain probabilistic algorithm on a graph with *n* nodes. If the probability that the algorithm returns the correct answer is [math]\displaystyle{ 1-1/n }[/math], 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:

- Miller–Rabin primality test: a probabilistic algorithm for testing whether a given number
*n*is prime or composite. If*n*is composite, the test will detect*n*as composite WHP. There is a small chance that we are unlucky and the test will think that*n*is prime. But, the probability of error can be reduced indefinitely by running the test many times with different randomizations. - Freivalds' algorithm: a randomized algorithm for verifying matrix multiplication. It runs faster than deterministic algorithms WHP.
- Treap: a randomized binary search tree. Its height is logarithmic WHP. Fusion tree is a related data structure.
- Online codes: randomized codes which allow the user to recover the original message WHP.
- BQP: a complexity class of problems for which there are polynomial-time quantum algorithms which are correct WHP.
- Probably approximately correct learning: A process for machine-learning in which the learned function has low generalization-error WHP.
- Gossip protocols: a communication protocol used in distributed systems to reliably deliver messages to the whole cluster using a constant amount of network resources on each node and ensuring no single point of failure.

## See also

## References

- Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm".
*Distributed Computing***23**(5–6): 331. doi:10.1007/s00446-010-0121-5. - "Principles of Distributed Computing (lecture 7)". ETH Zurich. http://dcg.ethz.ch/lectures/podc_allstars/lecture/chapter7.pdf. Retrieved 21 February 2015.

Original source: https://en.wikipedia.org/wiki/With high probability.
Read more |