Arandomized algorithm is analgorithm that employs a degree ofrandomness as part of its logic or procedure. The algorithm typically usesuniformly 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 determined by the random bits; thus either the running time, or the output (or both) are random variables.

There is a distinction 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 exampleQuicksort^[1]), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for theMFAS problem^[2]) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.^[3]

In common practice, randomized algorithms are approximated using apseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.

As a motivating example, consider the problem of finding an ‘a’ in anarray ofn elements.

Input: An array ofn≥2 elements, in which half are ‘a’s and the other half are ‘b’s.

Output: Find an ‘a’ in the array.

We give two versions of the algorithm, oneLas Vegas algorithm and oneMonte Carlo algorithm.

Las Vegas algorithm:

findingA_LV(arrayA,n)beginrepeatRandomlyselectoneelementoutofnelements.until'a'isfoundend

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\sum _{i=1}^n\frac{i}{2^i}=2}$

Since it is constant, the expected run time over many calls is${\displaystyle \mathrm{\Theta }(1)}$. (SeeBig Theta notation)

Monte Carlo algorithm:

findingA_MC(arrayA,n,k)begini:=0repeatRandomlyselectoneelementoutofnelements.i:=i+1untili=kor'a'isfoundend

If an ‘a’ is found, the algorithm succeeds, else the algorithm fails. Afterk iterations, the probability of finding an ‘a’ is:

This algorithm does not guarantee success, but the run time is bounded. The number of iterations is always less than or equal to k. Taking k to be constant the run time (expected and absolute) is${\displaystyle \mathrm{\Theta }(1)}$.

Randomized algorithms are particularly useful when faced with a malicious "adversary" orattacker who deliberately tries to feed a bad input to the algorithm (seeworst-case complexity andcompetitive analysis (online algorithm)) such as in thePrisoner's dilemma. It is for this reason thatrandomness is ubiquitous incryptography. In cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of truly random numbers or acryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent isquantum computing.

In the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm (related to theMonte Carlo method for simulation) is guaranteed to complete in an amount of time that can be bounded by a function the input size and its parameterk, but allows asmall probability of error. Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm (viaMarkov's inequality), by having it output an arbitrary, possibly incorrect answer if it fails to complete within a specified time. Conversely, if an efficient verification procedure exists to check whether an answer is correct, then a Monte Carlo algorithm can be converted into a Las Vegas algorithm by running the Monte Carlo algorithm repeatedly till a correct answer is obtained.

Computational complexity theory models randomized algorithms asprobabilistic Turing machines. BothLas Vegas andMonte Carlo algorithms are considered, and severalcomplexity classes are studied. The most basic randomized complexity class isRP, which is the class ofdecision problems for which there is an efficient (polynomial time) randomized algorithm (or probabilistic Turing machine) which recognizes NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class for RP is co-RP. Problem classes having (possibly nonterminating) algorithms withpolynomial time average case running time whose output is always correct are said to be inZPP.

The class of problems for which both YES and NO-instances are allowed to be identified with some error is calledBPP. This class acts as the randomized equivalent ofP, i.e. BPP represents the class of efficient randomized algorithms.

Quicksort was discovered byTony Hoare in 1959, and subsequently published in 1961.^[4] In the same year, Hoare published thequickselect algorithm,^[5] which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.^[6]

In 1917,Henry Cabourn Pocklington introduced a randomized algorithm known asPocklington's algorithm for efficiently findingsquare roots modulo prime numbers.^[7]In 1970,Elwyn Berlekamp introduced a randomized algorithm for efficiently computing the roots of a polynomial over a finite field.^[8] In 1977,Robert M. Solovay andVolker Strassen discovered a polynomial-timerandomized primality test (i.e., determining theprimality of a number). Soon afterwardsMichael O. Rabin demonstrated that the 1976Miller's primality test could also be turned into a polynomial-time randomized algorithm. At that time, no provably polynomial-timedeterministic algorithms for primality testing were known.

One of the earliest randomized data structures is thehash table, which was introduced in 1953 byHans Peter Luhn atIBM.^[9] Luhn's hash table used chaining to resolve collisions and was also one of the first applications oflinked lists.^[9] Subsequently, in 1954,Gene Amdahl,Elaine M. McGraw,Nathaniel Rochester, andArthur Samuel ofIBM Research introducedlinear probing,^[9] althoughAndrey Ershov independently had the same idea in 1957.^[9] In 1962,Donald Knuth performed the first correct analysis of linear probing,^[9] although the memorandum containing his analysis was not published until much later.^[10] The first published analysis was due to Konheim and Weiss in 1966.^[11]

Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.^[9] In 1979, Carter and Wegman introduceduniversal hash functions,^[12] which they showed could be used to implement chained hash tables with constant expected time per operation.

Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as theBloom filter.^[13] In 1989,Raimund Seidel andCecilia R. Aragon introduced a randomized balanced search tree known as thetreap.^[14] In the same year,William Pugh introduced another randomized search tree known as theskip list.^[15]

Prior to the popularization of randomized algorithms in computer science,Paul Erdős popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as theprobabilistic method.^[16]Erdős gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.^[17] He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.^[18][16]

Quicksort is a familiar, commonly used algorithm in which randomness can be useful. Many deterministic versions of this algorithm requireO(n²) time to sortn numbers for some well-defined class of degenerate inputs (such as an already sorted array), with the specific class of inputs that generate this behavior defined by the protocol for pivot selection. However, if the algorithm selects pivot elements uniformly at random, it has a provably high probability of finishing inO(n log n) time regardless of the characteristics of the input.

Incomputational geometry, a standard technique to build a structure like aconvex hull orDelaunay triangulation is to randomly permute the input points and then insert them one by one into the existing structure. The randomization ensures that the expected number of changes to the structure caused by an insertion is small, and so the expected running time of the algorithm can be bounded from above. This technique is known asrandomized incremental construction.^[19]

Input: AgraphG(V,E)

Output: Acut partitioning the vertices intoL andR, with the minimum number of edges betweenL andR.

Recall that thecontraction of two nodes,u andv, in a (multi-)graph yields a new nodeu ' with edges that are the union of the edges incident on eitheru orv, except from any edge(s) connectingu andv. Figure 1 gives an example of contraction of vertexA andB.After contraction, the resulting graph may have parallel edges, but contains no self loops.

Karger's^[20] basic algorithm:

begin    i = 1repeatrepeat            Take a random edge (u,v) ∈ E in G            replace u and v with the contraction u'until only 2 nodes remain        obtain the corresponding cut result Ci        i = i + 1until i = m    output the minimum cut among C1, C2, ..., Cm.end

In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is${\displaystyle O(n)}$, andn denotes the number of vertices.Afterm times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives anexample of one execution of the algorithm. After execution, we get a cut of size 3.

The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is$${\displaystyle \prod _{i=1}^{m}Pr(C_i\ne C)=\prod _{i=1}^m(1-Pr(C_i=C)).}$$

By lemma 1, the probability thatC_i =C is the probability that no edge ofC is selected during iterationi. Consider the inner loop and letG_j denote the graph afterj edge contractions, wherej ∈ {0, 1, …,n − 3}.G_j hasn −j vertices. We use the chain rule ofconditional possibilities.The probability that the edge chosen at iterationj is not inC, given that no edge ofC has been chosen before, is${\displaystyle 1-\frac{k}{|E(G_j)|}}$. Note thatG_j still has min cut of sizek, so by Lemma 2, it still has at least${\displaystyle \frac{(n-j)k}{2}}$ edges.

Thus,${\displaystyle 1-\frac{k}{|E(G_j)|}\ge 1-\frac{2}{n-j}=\frac{n-j-2}{n-j}}$.

So by the chain rule, the probability of finding the min cutC is$${\displaystyle Pr[C_i=C]\ge \left(\frac{n-2}{n}\right)\left(\frac{n-3}{n-1}\right)\left(\frac{n-4}{n-2}\right)\dots \left(\frac{3}{5}\right)\left(\frac{2}{4}\right)\left(\frac{1}{3}\right).}$$

Cancellation gives${\displaystyle Pr[C_i=C]\ge \frac{2}{n(n-1)}}$. Thus the probability that the algorithm succeeds is at least${\displaystyle 1-{\left(1-\frac{2}{n(n-1)}\right)}^m}$. For${\displaystyle m=\frac{n(n-1)}{2}\ln n}$, this is equivalent to${\displaystyle 1-\frac{1}{n}}$. The algorithm finds the min cut with probability${\displaystyle 1-\frac{1}{n}}$, in time${\displaystyle O(mn)=O(n^3\log n)}$.

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved. Find sources: "Randomized algorithm" – news ·newspapers ·books ·scholar ·JSTOR(September 2023) (Learn how and when to remove this message)

Randomness can be viewed as a resource, like space and time. Derandomization is then the process ofremoving randomness (or using as little of it as possible).^[21][22] It is not currently known^{[as of?]} if all algorithms can be derandomized without significantly increasing their running time.^[23] For instance, incomputational complexity, it is unknown whetherP =BPP,^[23] i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

There are specific methods that can be employed to derandomize particular randomized algorithms:

• themethod of conditional probabilities, and its generalization,pessimistic estimators
• discrepancy theory (which is used to derandomize geometric algorithms)
• the exploitation of limited independence in the random variables used by the algorithm, such as thepairwise independence used inuniversal hashing
• the use ofexpander graphs (ordispersers in general) toamplify a limited amount of initial randomness (this last approach is also referred to as generatingpseudorandom bits from a random source, and leads to the related topic of pseudorandomness)
• changing the randomized algorithm to use ahash function as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm bybrute-forcing all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)

When the model of computation is restricted toTuring machines, it is currently an open question whether the ability to make random choices allows some problems to be solved in polynomial time that cannot be solved in polynomial time without this ability; this is the question of whether P = BPP. However, in other contexts, there are specific examples of problems where randomization yields strict improvements.

• Based on the initial motivating example: given an exponentially long string of 2^k characters, half a's and half b's, arandom-access machine requires 2^k−1 lookups in the worst-case to find the index of ana; if it is permitted to make random choices, it can solve this problem in an expected polynomial number of lookups.
• The natural way of carrying out a numerical computation inembedded systems orcyber-physical systems is to provide a result that approximates the correct one with high probability (or Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting to randomization^[24]
• Incommunication complexity, the equality of two strings can be verified to some reliability using${\displaystyle \log n}$ bits of communication with a randomized protocol. Any deterministic protocol requires${\displaystyle \mathrm{\Theta }(n)}$ bits if defending against a strong opponent.^[25]
• The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.^[26]Bárány andFüredi showed that no deterministic algorithm can do the same.^[27] This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.
• A more complexity-theoretic example of a place where randomness appears to help is the classIP. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP =PSPACE.^[28] However, if it is required that the verifier be deterministic, then IP =NP.
• In achemical reaction network (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited toprimitive recursive functions.^[29]

• Approximate counting algorithm
• Atlantic City algorithm
• Bogosort
• Count–min sketch
• HyperLogLog
• Karger's algorithm
• Las Vegas algorithm
• Monte Carlo algorithm
• Principle of deferred decision
• Probabilistic analysis of algorithms
• Probabilistic roadmap
• Randomized algorithms as zero-sum games

• Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest, andClifford Stein.Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 1990.ISBN 0-262-03293-7. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.
• Dirk Draheim."Semantics of the Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics)." Springer, 2017.
• Jon Kleinberg andÉva Tardos.Algorithm Design. Chapter 13: "Randomized algorithms".
• Fallis, D. (2000). "The reliability of randomized algorithms".The British Journal for the Philosophy of Science.51 (2):255–271.doi:10.1093/bjps/51.2.255.
• M. Mitzenmacher andE. Upfal.Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
• Rajeev Motwani and P. Raghavan.Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• Rajeev Motwani and P. Raghavan.Randomized Algorithms. A survey on Randomized Algorithms.
• Christos Papadimitriou (1993),Computational Complexity (1st ed.), Addison Wesley,ISBN 978-0-201-53082-7 Chapter 11: Randomized computation, pp. 241–278.
• Rabin, Michael O. (1980)."Probabilistic algorithm for testing primality".Journal of Number Theory.12:128–138.doi:10.1016/0022-314X(80)90084-0.
• A. A. Tsay, W. S. Lovejoy, David R. Karger,Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.
• "Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).

• Randomized algorithms
• Analysis of algorithms

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from September 2023
• All articles needing additional references
• All articles with vague or ambiguous time
• Vague or ambiguous time from September 2023