 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (December 2023) (Learn how and when to remove this message) |
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 , 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.
, 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)" (PDF). ETH Zurich. Retrieved 21 February 2015.
 | This computer science article is a stub. You can help Misplaced Pages by expanding it. |