randomized algorithm part of a series onprobabilisticdata structures bloom filter countmin sketch quotient filter skip list random trees random binary tree treap rapidly exploring random tree related randomized algorithm hyperloglog computer science portalvte randomized algorithms redirects here it is not to be confused with algorithmic randomness a randomized algorithm is an algorithm that employs 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 algorithms performance will be a random variable determined by the random bits thus either the running time or the output or both are random variables one has to distinguish 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 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 however in some cases probabilistic algorithms are the only practical means of solving a problem in common practice randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits such an implementation may deviate from the expected theoretical behavior motivation as a motivating example consider the problem of finding an a in an array of n elements input an array of n2 elements in which half are as and the other half are bs output find an a in the array we give two versions of the algorithm one las vegas algorithm and one monte carlo algorithm las vegas algorithm findingalvarray a n begin repeat randomly select one element out of n elements until a is found end this algorithm succeeds with probability 1 the number of iterations varies and can be arbitrarily large but the expected number of iterations is lim n i 1 n i 2 i 2 displaystyle lim nto infty sum imathop 1nfrac i2i2 since it is constant the expected run time over many calls is 1 displaystyle theta 1 see big o notation monte carlo algorithm findingamcarray a n k begin i0 repeat randomly select one element out of n elements i i 1 until ik or a is found end if an a is found the algorithm succeeds else the algorithm fails after k iterations the probability of finding an a is pr f i n d a 1 1 2 k displaystyle pr112k 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 1 displaystyle theta 1 randomized algorithms are particularly useful when faced with a malicious adversary or attacker who deliberately tries to feed a bad input to the algorithm see worstcase complexity and competitive analysis online algorithm such as in the prisoners dilemma it is for this reason that randomness is ubiquitous in cryptography in cryptographic applications pseudorandom numbers cannot be used since the adversary can predict them making the algorithm effectively deterministic therefore either a source of truly random numbers or a cryptographically secure pseudorandom number generator is required another area in which randomness is inherent is quantum 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 the monte 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 parameter k but allows a small probability of error observe that any las vegas algorithm can be converted into a monte carlo algorithm via markovs 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 computational complexity theory models randomized algorithms as probabilistic turing machines both las vegas and monte carlo algorithms are considered and several complexity classes are studied the most basic randomized complexity class is rp which is the class of decision problems for which there is an efficient polynomial time randomized algorithm or probabilistic turing machine which recognizes noinstances with absolute certainty and recognizes yesinstances with a probability of at least 12 the complement class for rp is corp problem classes having possibly nonterminating algorithms with polynomial time average case running time whose output is always correct are said to be in zpp the class of problems for which both yes and noinstances are allowed to be identified with some error is called bpp this class acts as the randomized equivalent of p ie bpp represents the class of efficient randomized algorithms history historically the first randomized algorithm was a method developed by michael o rabin for the closest pair problem in computational geometry the study of randomized algorithms was spurred by the 1977 discovery of a randomized primality test ie determining the primality of a number by robert m solovay and volker strassen soon afterwards michael o rabin demonstrated that the 1976 millers primality test can be turned into a randomized algorithm at that time no practical deterministic algorithm for primality was known the millerrabin primality test relies on a binary relation between two positive integers k and n that can be expressed by saying that k is a witness to the compositeness of n it can be shown that if there is a witness to the compositeness of n then n is composite ie n is not prime and if n is composite then at least threefourths of the natural numbers less than n are witnesses to its compositeness and there is a fast algorithm that given k and n ascertains whether k is a witness to the compositeness of n observe that this implies that the primality problem is in corp if one randomly chooses 100 numbers less than a composite number n then the probability of failing to find such a witness is 14100 so that for most practical purposes this is a good primality test if n is big there may be no other test that is practical the probability of error can be reduced to an arbitrary degree by performing enough independent tests therefore in practice there is no penalty associated with accepting a small probability of error since with a little care the probability of error can be made astronomically small indeed even though a deterministic polynomialtime primality test has since been found see aks primality test it has not replaced the older probabilistic tests in cryptographic software nor is it expected to do so for the foreseeable future examples quicksort quicksort is a familiar commonly used algorithm in which randomness can be useful any deterministic version of this algorithm requires on2 time to sort n numbers for some welldefined 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 in onlogn time regardless of the characteristics of the input randomized incremental constructions in geometry in computational geometry a standard technique to build a structure like a convex hull or delaunay 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 upper bounded this technique is known as randomized incremental construction min cut kargers algorithm input a graph gve output a cut partitioning the vertices into l and r with the minimum number of edges between l and r recall that the contraction of two nodes u and v in a multigraph yields a new node u with edges that are the union of the edges incident on either u or v except from any edges connecting u and v figure 1 gives an example of contraction of vertex a and b after contraction the resulting graph may have parallel edges but contains no self loops figure 2 successful run of kargers algorithm on a 10vertex graph the minimum cut has size 3 and is indicated by the vertex colours figure 1 contraction of vertex a and b kargers basic algorithm begin i1 repeat repeat take a random edge uv e in g replace u and v with the contraction u until only 2 nodes remain obtain the corresponding cut result ci ii1 until im output the minimum cut among c1c2cm 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 o n displaystyle on and n denotes the number of vertices after m times executions of the outer loop we output the minimum cut among all the results the figure 2 gives an example of one execution of the algorithm after execution we get a cut of size 3 lemma 1 let k be the min cut size and let c e1e2ek be the min cut if during iteration i no edge e c is selected for contraction then cic proof if g is not connected then g can be partitioned into l and r without any edge between them so the min cut in a disconnected graph is 0 now assume g is connected let vlr be the partition of v induced by c c uv e u lv r welldefined since g is connected consider an edge uv of c initially uv are distinct vertices as long as we pick an edge f e displaystyle fneq e u and v do not get merged thus at the end of the algorithm we have two compound nodes covering the entire graph one consisting of the vertices of l and the other consisting of the vertices of r as in figure 2 the size of min cut is 1 and c ab if we dont select ab for contraction we can get the min cut lemma 2 if g is a multigraph with p vertices and whose min cut has size k then g has at least pk2 edges proof because the min cut is k every vertex v must satisfy degreev k therefore the sum of the degree is at least pk but it is well known that the sum of vertex degrees equals 2e the lemma follows analysis of algorithm the probability that the algorithm succeeds is 1the probability that all attempts fail by independence the probability that all attempts fail is i 1 m pr c i c i 1 m 1 pr c i c displaystyle prod i1mprcineq cprod i1m1prcic by lemma 1 the probability that cic is the probability that no edge of c is selected during iteration i consider the inner loop and let gj denote the graph after j edge contractions where j01n3 gj has nj vertices we use the chain rule of conditional possibilities the probability that the edge chosen at iteration j is not in c given that no edge of c has been chosen before is 1 k e g j displaystyle 1frac kegj note that gj still has min cut of size k so by lemma 2 it still has at least n j k 2 displaystyle frac njk2 edges thus 1 k e g j 1 2 n j n j 2 n j displaystyle 1frac kegjgeq 1frac 2njfrac nj2nj so by the chain rule the probability of finding the min cut c is p r c i c n 2 n n 3 n 1 n 4 n 2 3 5 2 4 1 3 displaystyle prgeq leftfrac n2nrightleftfrac n3n1rightleftfrac n4n2rightldots leftfrac 35rightleftfrac 24rightleftfrac 13right cancellation gives pr c i c 2 n n 1 displaystyle prgeq frac 2nn1 thus the probability that the algorithm succeeds is at least 1 1 2 n n 1 m displaystyle 1left1frac 2nn1rightm for m n n 1 2 ln n displaystyle mfrac nn12ln n this is equivalent to 1 1 n displaystyle 1frac 1n the algorithm finds the min cut with probability 1 1 n displaystyle 1frac 1n in time o m n o n 3 log n displaystyle omnon3log n derandomization randomness can be viewed as a resource like space and time derandomization is then the process of removing randomness or using as little of it as possible it is not currently known if all algorithms can be derandomized without significantly increasing their running time for instance in computational complexity it is unknown whether p bpp ie we do not know whether we can take an arbitrary randomized algorithm that run 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 the method 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 the pairwise independence used in universal hashing the use of expander graphs or dispersers in general to amplify a limited amount of initial randomness this last approach is also referred to as generating pseudorandom bits from a random source and leads to the related topic of pseudorandomness where randomness helps when the model of computation is restricted to turing 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 2k characters half as and half bs a random access machine requires at least 2k1 lookups in the worstcase to find the index of an a 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 in embedded systems or cyberphysical 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 in communication complexity the equality of two strings can be verified to some reliability using log n displaystyle log n bits of communication with a randomized protocol any deterministic protocol requires n displaystyle theta n bits if defending against a strong opponent the volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time this is true unconditionally ie without relying on any complexitytheoretic assumptions assuming the convex body can be queried only as a black box a more complexitytheoretic example of a place where randomness appears to help is the class ip ip consists of all languages that can be accepted with high probability by a polynomially long interaction between an allpowerful prover and a verifier that implements a bpp algorithm ip pspace however if it is required that the verifier be deterministic then ip np in a chemical reaction network a finite set of reactions like ab 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 concentrationbased 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 to primitive recursive functions probabilistic analysis of algorithms atlantic city algorithm monte carlo algorithm las vegas algorithm principle of deferred decision notes thomas h cormen charles e leiserson ronald l rivest and clifford stein introduction to algorithms second edition mit press and mcgrawhill 1990 isbn0262032937 chapter 5 probabilistic analysis and randomized algorithms pp91122 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 don fallis 2000 the reliability of randomized algorithms british journal for the philosophy of science 5125571 m mitzenmacher and e 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 isbn0201530821 chapter 11 randomized computation pp241278 m o rabin 1980 probabilistic algorithm for testing primality journal of number theory 1212838 a a tsay w s lovejoy david r karger random sampling in cut flow and network design problems mathematics of operations research 242383413 1999 