Randomized algorithm
Randomized algorithm is a type of algorithm that uses a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.
Overview[edit | edit source]
In the case of deterministic algorithms, the set of inputs is divided into several classes, where the algorithm behaves differently for different classes. In contrast, a randomized algorithm has the ability to make random choices, and thus can behave differently on the same input on different executions, allowing it to be correct on a larger set of inputs than deterministic algorithms.
Randomized algorithms are particularly useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm such as in the Two Armed Bandit Problem. It is for this reason that randomized algorithms are a useful tool in cryptography. In such cases, the randomness of the algorithm can be used to thwart the adversary's attempts to choose a particularly bad input.
Types of Randomized Algorithms[edit | edit source]
Randomized algorithms are subdivided into two major types, which are Las Vegas algorithms and Monte Carlo algorithms.
- Las Vegas algorithms always produce the correct result and are always expected to finish in a reasonable amount of time, but that time is a random variable.
- Monte Carlo algorithms are expected to be fast, but aren't always correct. The incorrectness is bounded by a probability parameter.
Applications[edit | edit source]
Randomized algorithms are often used in computer_science, mathematics, and related fields such as cryptography, game_theory, graph_theory, machine_learning, computational_geometry, and computational_biology. They offer several advantages over deterministic algorithms, primarily in terms of simplicity and speed.
See Also[edit | edit source]
This Computer Science related article is a stub. You can help WikiMD by expanding it.
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
