World Library  
Flag as Inappropriate
Email this Article

With high probability

Article Id: WHEBN0045454942
Reproduction Date:

Title: With high probability  
Author: World Heritage Encyclopedia
Language: English
Subject: WHP, Randomized algorithms, Probability, WikiProject Mathematics/List of mathematics articles (W)
Collection: Probability, Randomized Algorithms
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

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.  
  • "Principles of Distributed Computing (lecture 7)" (PDF). ETH Zurich. Retrieved 21 February 2015. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


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.