In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, in the analysis of
probabilistic algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s. 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:
*
Miller–Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
: 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
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of in ...
: a randomized binary search tree. Its height is logarithmic WHP.
Fusion tree
In computer science, a fusion tree is a type of tree data structure that implements an associative array on -bit integers on a finite universe, where each of the input integer has size less than 2w and is non-negative. When operating on a collecti ...
is a related data structure.
*
Online codes In computer science, online codes are an example of rateless erasure codes. These codes can encode a message into a number of symbols such that knowledge of any fraction of them allows one to recover the original message (with high probability). ''R ...
: 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
In computational learning theory, probably approximately correct (PAC) learning is a framework for mathematical analysis of machine learning. It was proposed in 1984 by Leslie Valiant.L. Valiant. A theory of the learnable.' Communications of the A ...
: A process for machine-learning in which the learned function has low generalization-error WHP.
*
Gossip protocols: a
communication protocol
A communication protocol is a system of rules that allows two or more entities of a communications system to transmit information via any kind of variation of a physical quantity. The protocol defines the rules, syntax, semantics (computer scien ...
used in
distributed systems
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
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
*
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
*
Almost surely
In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
References
*
*
{{cs-stub
Probability theory
Randomized algorithms