This page (revision-1) was last changed on 29-Nov-2024 16:16 by UnknownAuthor

Only authorized users are allowed to rename pages.

Only authorized users are allowed to delete pages.

Page revision history

Version Date Modified Size Author Changes ... Change note

Page References

Incoming links Outgoing links
Randomized algorithm
Randomized algorithm

Version management

Difference between version and

At line 1 added 28 lines
!!! Overview
[{$pagename}] is an [algorithm] that employs a degree of randomness as part of its logic.[{$pagename}]s 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].
[{$pagename}]s requires distinguishing between [algorithms] that use the [random] input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort[1]), and [algorithms] which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem[2]) or fail to produce a result either by signaling a failure or failing to terminate.In the second case, random performance and random output, the term "algorithm" for a procedure is somewhat questionable. In the case of random output, it is no longer formally effective.[3] However, in some cases, [probabilistic algorithm]s are the only practical means of solving a problem.[4]!! [{$pagename}] [Classification]
Types of [{$pagename}]:
* [Monte Carlo algorithm]s
** may return an answer that is not correct.
** Example: primality testing
** Subtypes: one-sided vs. two-sided errors
* [Las Vegas algorithm]s
** may not return an answer at all, but if they do the answer is guaranteed to be correct.
** Example: factoring
* Sherwood algorithms
** always give the correct answer. (Sometimes also called Las Vegas.)
** Example: Quicksort
! Complexity classes:
* Randomized Polynomial time (RP): A language is in RP if there is a polynomial-time (Monte Carlo) algorithm that never accepts words that are not in the language, and has probability at least 1/2 of accepting words in the language
* Zero-error Probabilistic Polynomial (ZPP) Like RP, except the algorithm is Sherwood, so it always accepts if the word is in the language
* Bounded-error Probabilistic Polynomial (BPP) Like RP, except that the algorithm has probability at least 3/4 of accepting if the word is in the language, and probability at most 1/4 of accepting if the word is not in the language.
!! [Turing Machine]
!! More Information
There might be more information for this subject on one of the following:
[{ReferringPagesPlugin before='*' after='\n' }]
----
* [#1] - [Randomized_algorithm|Wikipedia:Randomized_algorithm|target='_blank'] - based on information obtained 2019-05-03
This page (revision-1) was last changed on 29-Nov-2024 16:16 by UnknownAuthorTop