A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. In common practice, this means that the machine implementing the algorithm has access to a pseudo-random number generator. The algorithm typically uses the random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case". Formally, the algorithm's performance will be a random variable determined by the random bits, with (hopefully) good expected value; this expected value is called the expected runtime. The "worst case" is typically so unlikely to occur that it can be ignored. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... Random redirects here. ... For the Pet Shop Boys album of the same name see Behaviour Behavior or behaviour (see spelling differences) refers to the actions or reactions of an object or organism, usually in relation to the environment. ... A random variable is a mathematical function that maps outcomes of random experiments to numbers. ... In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... In computer science, run time (with a space, though often its spelled without one) describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time). ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ...

Motivation

As a motivating example, consider the problem of finding an 'a' in an array of n elements, given that half are 'a's and the other half are 'b's. The obvious approach is to look at each element of the array, but this would take very long (n/2 operations) if the array were ordered as 'b's first followed by 'a's. There is a similar drawback with checking in the reverse order, or checking every second element. In fact, with any strategy at all in which the order in which the elements will be checked is fixed, i.e, a deterministic algorithm, we cannot guarantee that the algorithm will complete quickly for all possible inputs. On the other hand, if we were to check array elements at random, then we will quickly find an 'a' with high probability, whatever be the input. This article or section does not cite its references or sources. ... This article or section does not cite its references or sources. ... A strategy is a long term plan of action designed to achieve a particular goal, most often winning. Strategy is differentiated from tactics or immediate actions with resources at hand. ...

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 competitive analysis (online algorithm)). It is for this reason that randomness is ubiquitous in cryptography. 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 a cryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent is quantum computing. In some sports, an attacker is a specific type of player, usually one whose role involves aggressive play. ... Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the... The word random is used to express lack of purpose, cause, order, or predictability in non-scientific parlance. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ... A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ...

In the example above, the randomized algorithm always outputs the correct answer, it is just that there is a small probability of taking long to execute. Sometimes we want the algorithm to always complete quickly, but allow a small probability of error. The former type are called Las Vegas algorithms, and the latter are Monte Carlo algorithms (related to the Monte Carlo method for simulation). Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm, by having it output an arbitrary, possibly incorrect answer if it fails to complete within a specified time. In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. ... Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ... Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ...

Also refer to Probabilistic analysis, which is based on assuming something about the set of all possible inputs. This assumption is then used to design an efficient algorithm. If the characteristic of the input to an algorithm is unknown, e.g. we do not know the distribution of the inputs, probabilistic analysis cannot be used. Usually in a randomized algorithm, some pseudo-random number generator is used inside of the program. An algorithm is randomized if its output is determined by the input as well as the values produced by a random-number generator.

Additionally, random generators can be used to produce completely random sequences of letters if each letter is assigned a number between 1 and 26, and the blank space is assigned 27. For example, a random number generator can produce the phrase "TEERAWIT NEEDS TO STOP" at the probability which is equal to 1/27^22.

Complexity

Computational complexity theory, the study of the computational resources required to solve a given problem, 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 NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class is Co-RP, and the class of problems for which both YES and NO answers are allowed to be probabilistic is BPP. Problem classes having (possibly nonterminating) algorithms with polynomial time average case running time whose output is always correct are said to be in ZPP. For problems that (are believed to) lie outside these classes, such as NP-hard problems, even randomized algorithms do not suffice, and it becomes necessary to resort to approximation algorithms. As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point with equal probability. ... An artistic representation of a Turing Machine . ... In complexity theory, RP (randomized polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time in the input size If the correct answer is NO, it always returns NO If the correct answer is YES, then... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... This article is about the complexity class. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...

Historically, the study of randomized algorithms was spurred by the discovery by Miller and Rabin in 1976 that the problem of determining the primality of a number can be solved efficiently by a randomized algorithm. At that time, no practical deterministic algorithm for primality was known. The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... A primality test is an algorithm for determining whether an input number is prime. ... In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ...

The Miller-Rabin 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 (i.e., n is not prime), and
• If n is composite then at least three-fourths 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 Co-RP. If one randomly chooses 100 numbers less than a composite number n, then the probability of failing to find such a "witness" is (1/4)¹⁰⁰ 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. In mathematics, a prime number (or a prime) is a positive integer that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... Random redirects here. ... A primality test is an algorithm for determining whether an input number is prime. ...

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 polynomial-time primality test has since been found, it is has not replaced the older probabilistic tests in cryptographic software nor is it expected to do so for the foreseeable future. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P. The... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ... It has been suggested that this article or section be merged with Computer program. ...

If, using a randomized method, the probability of error is 2⁻¹⁰⁰⁰, the philosophical question arises: is this a mathematical proof? After all, the probability of the algorithm's error is distinctly smaller than the probability of an error in the computer hardware executing it, or the reader making an error in reading a proof - what does it mean in real terms to consider this small a probability? In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ...

Applications

Quicksort is probably the most familiar "real-world" algorithm in which randomness is very useful. The deterministic version of this algorithm requires O(n²) time to sort n numbers for some degenerate inputs -- such as the array elements being already in sorted order! However, if the algorithm randomly permutes elements before starting, it finishes in O(n log n) time with a high probability, for any input. The difference between the two is crucial when sorting large datasets in particular. Quicksort in action on a list of random numbers. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

A more complex example, representative of the use of randomized algorithms to solve graph theoretic problems, is the following randomized minimum cut algorithm: A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks. ...

 find_min_cut(undirected graph G) { while there are more than 2 nodes in G do { pick an edge (u,v) at random in G contract the edge, while preserving multi-edges remove all loops } output the remaining edges } 

Here, contracting an edge (u,v) means adding a new vertex w, replacing any edge (u,x) or (v,x) with (w,x), and then deleting u and v from G. A node is a basic unit used to build data structures, such as linked lists and tree data structures. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...

Let n = |V[G]|. It can be shown that this algorithm outputs a minimum cut with probability at least n^-2, thus running it n²log(n) times and taking the smallest output cut, we find a minimum cut with high probability.

Derandomization

It is usually the case that randomized algorithms either are more elegant or require less resources than the corresponding deterministic algorithms. Removing randomization from randomized algorithms to build equivalently powerful deterministic algorithms is an active field of research in computer science. This general method is, of course, central in resolving many complexity classes describing randomized computation. In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ...

Randomized Algorithms for Robustness

The objective is to study probabilistic and randomized methods for analysis and design of uncertain systems. This research area is fairly recent, even though its roots lie in the robustness techniques for handling complex control systems developed in the 1980s. In contrast to these previous deterministic techniques, its main ingredient is the use of probabilistic concepts. One of the goals of this research endeavor is to provide a reapprochement between the classical stochastic and robust paradigms, combining worst-case bounds with probabilistic information, thus potentially reducing the conservatism inherent in the worst-case design. In this way, the control engineer gains additional insight that may help bridging the gap between theory and applications. In the context of computer software, robustness is the resilience of the system, especially when under stress or when confronted with invalid input. ...

The algorithms derived in the probabilistic context are based on uncertainty randomization and are usually called randomized algorithms. For control systems analysis, these algorithms have low complexity and are associated with robustness bounds that are generally less conservative than the classical ones, obviously at the expense of a probabilistic risk of failure.

In the classical robustness analysis framework, the main objective is to guarantee that a certain system property is attained for all uncertainties D bounded within a specified set B. To this end, it is useful to define a performance function

J(D): B → R

and an associated performance level g. In general, the function J(D) can take into account the simultaneous attainment of various performance requirements.

In the framework of robust synthesis, the performance function depends also on some design parameters k in a bounding set K and takes the form

J(D,k): (B,K) → R.

When dealing with probabilistic methods for robustness, we assume that the uncertainty D is a random matrix distributed according to a probability density function f(D) with support B. Then, we formulate various problems. For example, the Probabilistic Performance Problem can be stated as: Given a performance function J(D) with associated level g and a density function f(D) with support B, compute the probability of performance

P = Prob{J(D) ≤ g}.

The probability of performance measures the probability that a level of performance g is achieved when D is a random matrix distributed according to f(D). We remark that this probability is in general difficult to compute either analytically or numerically, since it basically requires the evaluation of a multidimensional integral. In some cases, it can be evaluated in closed form, in other cases randomized algorithms may be used to this end. The ultimate objective of this research is to develop low complexity randomized algorithms for various analysis and synthesis problems, i.e. for specific performance functions. In probability theory and statistics, a random matrix is a matrix-valued random variable. ... In mathematics, closed form can mean: a finitary expression, rather than one involving (for example) an infinite series, or use of recursion - this meaning usually occurs in a phrase like solution in closed form and one also says closed formula; a closed differential form: see Closed and exact differential forms. ...

References

• R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford 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.
• Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1.  Chapter 11: Randomized computation, pp.241–278.
• R. Tempo, G. Calafiore and F. Dabbene. Randomized Algorithms for Analysis and Control of Uncertain Systems. Springer-Verlag, London, 2005, ISBN 1-85233-524-6.
• R. Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms. [1]