 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# With high probability

Article Id: WHEBN0045454942
Reproduction Date:

 Title: With high probability Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### With high probability

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. it can be made as close as desired to 1 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 1-1/n, 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 algorithms in which 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. QMA and QIP are related complexity class.
• 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

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.