Randomized algorithm

A randomized algorithm makes some choices using random bits.

For a fixed input, the random bits can change the path taken by a randomized algorithm, its output, or its running time. Specify the distribution of those choices and which guarantee is required: one-sided error permits mistakes of only one kind, whereas ZPP requires a correct answer and bounds the expected running time. Polynomial identity testing makes this distinction concrete: choosing different field elements changes whether a nonidentity is detected.

A uniform distribution on a finite set must be implemented faithfully. To choose uniformly from $\{0,1,2,3,4\}$ using fair independent bits, read three bits as a number from zero to seven, discard five through seven, and repeat until a permitted value appears. Each retained value has the same chance. Taking the three-bit number modulo five instead would give zero, one and two twice as many preimages as three and four, invalidating a calculation that assumes equal chances.

A balanced binary sequence of length $2n$ has $n$ entries of each kind. Uniformly sample an $n$-element subset of the positions and place the first kind there. If $2n$ is a power of two, repeatedly draw uniform positions using ${\log }_2(2n)$ fair random bits, reject previously selected positions, and stop after $n$ distinct positions. Each new position is uniform among those remaining, making every $n$-element subset equally likely. The expected number of draws is ${\sum }_{s=0}^{n-1}2n/(2n-s)<2n$, giving $O(n\log n)$ expected random bits.

Derandomization converts a randomized construction or algorithm into a deterministic one while preserving its desired guarantee. The method of conditional probabilities does this by maintaining a computable conditional expectation until all choices are fixed.

The method of conditional probabilities turns an expected value guarantee into a deterministic construction. For a maximization objective function, fix one choice at a time, always keeping the conditional expectation of the final value at least as large as before. Once every choice is fixed, that conditional expectation is the actual value. The useful ingredient is a way to evaluate the conditional expectations efficiently.

No actual random choices are needed during this construction. The probability distribution describes hypothetical completions used in the analysis; the algorithm compares their conditional expectations and commits deterministically. For maximum cut, this converts the random cut lower bound into a cut of a graph containing at least half the edges. A maximum cut can still be larger, as the conditional expectations cut example shows.

In a partially fixed two-colour edge coloring of a complete graph, complete all unassigned edges independently and fairly. For a fixed clique with $r$ unassigned edges, its conditional probability of becoming monochromatic is zero if both colours already occur; $2^{-r}$ if a colour is fixed and no conflicting colour occurs; and $2^{1-r}$ if none is fixed. Sum these conditional probabilities over the cliques to obtain a computable conditional expectation. Fix each next edge to a colour that does not increase this conditional expectation, yielding a deterministic minimization construction.

Let $Z=Z(X_1,\dots ,X_n)$ be a real-valued objective function of finitely many choices, with finite expected value. Suppose a prefix $P=(X_1=x_1,\dots ,X_i=x_i)$ has positive probability. Write $q(P)=\mathbb{E}[Z\mid P]$. If the next choice is a fair bit, the law of total expectation givesAt least one child is at least this average. Choose a child with the larger value, using a fixed rule for ties. The resulting loop invariant is $q(P)\ge \mathbb{E}Z$. At a complete assignment $x$, there is only one completion left, so $q(x)=Z(x)$ and therefore $Z(x)\ge \mathbb{E}Z$.

For a biased choice or more than two possibilities, use the corresponding weighted average:Some positive-probability child is at least the weighted average. For minimization, choose a child at most the current conditional expectation and reverse the invariant. The averaging identity is the same in both directions.^[ref]

The word "probabilities" in the method's name also covers an indicator random variable for an undesirable outcome: keeping its conditional expectation, which is its conditional probability, strictly below one eventually forces that indicator to be zero. Optimizing an ordinary numerical objective function is the method of conditional expectations formulation used below.

Let $G=(V,E)$ be a finite undirected simple graph, with $n=|V|$ vertices and $m=|E|$ edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.

For the analysis, assign independent fair bits $X_v$ to the vertices. For each edge $uv$, the indicator random variable $I_{uv}=1_{\{X_u\ne X_v\}}$ has expected value $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.

For any partial assignment $P$, let $f(P)$ count edges whose two endpoints are already fixed on opposite sides, and let $u(P)$ count edges with at least one unassigned endpoint. Under the remaining independent fair bits,An edge with fixed equal labels contributes zero; fixed unequal labels contribute one. If one endpoint is unassigned, its fair bit disagrees with the fixed label with probability $1/2$. If both endpoints are unassigned, their independent fair bits disagree with probability $1/2$ as well. Count each unresolved edge once, even when both endpoints are unassigned.

Process vertices in a fixed order. Evaluate the conditional expectation cut formula after setting the next label to zero and after setting it to one; retain the larger value, choosing zero on ties. The conditional expectation choice invariant ensures the final cut of a graph has size at least $m/2$. This is a deterministic approximation algorithm for maximum cut.^[ref]

Consider the following original five-vertex simple graph, where $AB$ denotes the undirected edge $\{A,B\}$:Its seven edges give initial expected value $q(\varnothing )=7/2=3.5$. Use vertex order $A,B,C,D,E$ and choose zero whenever the two child conditional expectations tie.

The complete decision ledger is below. A prefix lists fixed labels in vertex order; all later labels remain hypothetically independent fair bits. Each candidate entry is the conditional expectation of the final cut of a graph, including the contribution of unresolved edges.

For example, after $A=0,B=1$, edge $AB$ is fixed crossing and the other six edges are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved edges: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same conditional expectation.

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing edges are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four edges.

It is not a maximum cut. Labels $(0,1,1,0,1)$ cross all edges except $BC$, giving six. Seven are impossible because the triangle in a graph $ABC$ cannot have all three edges crossing a two-sided cut of a graph. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with linearity of expectation. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an expected value guarantee; it need not preserve the best possible completion.

Directly scanning all $m$ edges to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in Big O notation. There is a faster implementation. When assigning vertex $v$, let $d_0$ and $d_1$ count its already assigned graph neighbours labelled zero and one. Contributions from edges not incident to $v$ are unchanged, and contributions from edges to unassigned graph neighbours stay $1/2$ for either choice. ThereforeChoose zero if $d_1\ge d_0$, otherwise one: put $v$ on the side with fewer already assigned graph neighbours. With adjacency lists, scanning each vertex's list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the graph. These bounds count operations on labels and counters that fit in machine words of $O(\log (n+m+2))$ bits. Multiplying the conditional expectation cut formula by two also permits exact integer comparisons without rounding.

If $\mathrm{OPT}$ is the size of a maximum cut, then $\mathrm{OPT}\le m$. The constructed cut of a graph thus has size at least $m/2\ge \mathrm{OPT}/2$, an approximation ratio of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.

For a general randomized algorithm, the averaging proof alone does not establish efficient derandomization. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant conditional expectations. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The polynomial-time algorithm here comes from the local conditional expectation cut formula, not from that enumeration.

A probabilistic Turing machine is a Turing machine whose transitions may depend on independent random bits.

A randomized decision algorithm has one-sided error when one answer is always correct and only the other answer can be mistaken.

The guarantee concerns each fixed input, with probability taken over the choices of the randomized algorithm. Always state which answer is protected. In polynomial identity testing, call an input positive when its polynomial is identically zero, and let acceptance mean claiming an identity. Then the possibilities are:

Thus a zero polynomial evaluation can leave uncertainty, but a nonzero polynomial evaluation settles the question. An error bound for a fixed nonzero polynomial is not the conditional probability that a particular accepted input is an identity; that latter question would need a distribution on the inputs as well.

In computational complexity theory, a polynomial-time algorithm with this orientation and false acceptance probability at most $1/2$ establishes membership in co-RP. Reversing the question to ask whether the polynomial is nonzero gives the RP orientation: negative instances are always rejected. The random evaluation test for a polynomial identity explains the required field, total degree, sampling and evaluation assumptions.

$\mathbf{RP}$ contains decision problems with a polynomial-time randomized algorithm that rejects every negative instance and accepts every positive instance with probability at least one half.

$\mathbf{co}\text{-}\mathbf{RP}$ consists of complements of languages in RP. Its algorithms always accept positive instances and reject negative instances with probability at least one half.

$\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Equivalently, it consists of problems having an always-correct randomized algorithm with polynomial expected running time.

Independent repetitions reduce a randomized algorithm's error probability while preserving polynomial running time.

The combining rule depends on the error orientation. For one-sided error with false acceptance probability at most $p<1$, reject as soon as any trial rejects and accept only if every trial accepts. For $k$ independent trials on the same fixed negative input, false acceptance has probability at most $p^k$. The protected positive inputs still always accept. If false rejection is the possible mistake instead, accept as soon as any trial accepts. This uses the decisive answer rather than a majority vote.

For constant $p<1$, $k$ grows only logarithmically in $1/\epsilon$ to achieve error at most $\epsilon$. A polynomial number of trials preserves a polynomial-time algorithm's running-time bound. Independence matters: repeating one answer, or evaluating at the same random point each time, supplies no new evidence. The independent repetition of a polynomial identity test gives an exact $25$-outcome example.

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials $A,B$ amounts to testing $P=A-B$ for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer $n\ge 1$, ${\prod }_{i=1}^n(1+x_i)$ has $2^n$ distinct monomials, one for each subset of the $n$ variables. Its factored expression needs only $n$ additions and $n-1$ multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Work in the finite field ${\mathbb{F}}_5=\{0,1,2,3,4\}$, using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives $(x+1{)}^2=x^2+2x+1$, so all coefficients of $F$ cancel: $F$ is identically zero. In contrast, $G=x^2-3x+2=x^2+2x+2$ in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.

The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, $G(3)=(3-1)(3-2)=2$ is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that $G$ is nonzero. A random variable $a$ with a uniform distribution on a finite set ${\mathbb{F}}_5$ hits those two polynomial roots with probability $2/5$.

A crucial limit appears with $H(x)=x^5-x$. Its coefficients make it a nonzero polynomial of polynomial degree five in ${\mathbb{F}}_5[x]$, yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are $0,0,30,240,1020$, all divisible by five. Thus $H$ induces the same polynomial function as the zero polynomial. Any number of trials restricted to ${\mathbb{F}}_5$ will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is $5/5=1$, which gives no useful guarantee.

When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish $H$ from zero.^[ref]

Let $P$ be a nonzero multivariate polynomial over a field $K$, with total degree at most $d\ge 0$. Choose a nonempty finite set $S\subseteq K$. For independent random variables $a_1,\dots ,a_n$, each with a uniform distribution on a finite set on $S$, the Schwartz-Zippel lemma givesNonzeroness is essential; the zero polynomial always evaluates to zero. The total degree sums exponents within each monomial, rather than taking their maximum: $x^2{y}^3+y$ has total degree five. The field need not be finite, but $S$ must be finite. The estimate reduces error only when $d/|S|<1$.^[ref]

The proof begins with the root bound for a polynomial. For several variables, write $P={\sum }_{j=0}^m{Q}_j(x_1,\dots ,x_{n-1})x_n^j$, with $Q_m\ne 0$. The total degree of $Q_m$ is at most $d-m$. By induction, $Q_m$ vanishes with probability at most $(d-m)/|S|$. Otherwise the remaining univariate polynomial has at most $m$ polynomial roots. Adding the two contributions gives $d/|S|$.^[ref]

The algorithm samples a point, performs exact polynomial evaluation, rejects the identity if the value is nonzero, and otherwise accepts. The lemma bounds false acceptance for every fixed nonzero input. For the polynomial identity testing over a finite field example, $G$ has $d=2$ and $|S|=5$, so its exact $2/5$ error attains the bound. Numerical near-zero values from floating-point arithmetic do not satisfy this exact algebraic contract. A polynomial-time algorithm claim additionally needs efficient sampling and evaluation, including the bit cost of representing and operating on field elements. Counting field operations alone does not establish that cost.

Repeat the random evaluation test for a polynomial identity with fresh independent random variables, keeping the same fixed polynomial. Reject as soon as any polynomial evaluation is nonzero; accept only if all $k$ values vanish. An identity is always accepted, preserving one-sided error. If a nonzero polynomial has single-trial false acceptance probability $p_1$, independence gives $p_k=p_1^k$. The Schwartz-Zippel lemma bounds this by $(d/|S|{)}^k$ when $d<|S|$.

For $G(x)=(x-1)(x-2)$ over the finite field ${\mathbb{F}}_5$, two uniform independent choices $(a,b)$ have $25$ equally likely ordered outcomes, each with probability $1/25$. Both polynomial evaluations are zero only at $(1,1),(1,2),(2,1),(2,2)$. Hence false acceptance falls from $2/5$ in one trial to $4/25$ in two trials, and correct rejection rises from $3/5$ to $21/25$.

If the second choice reuses the first, the pair is $(a,a)$ and only five diagonal outcomes are possible. Two still falsely accept, so the error remains $2/5$. Choosing fresh independent points is precisely what makes the full $25$-cell grid and the product of probabilities valid. For a target error $0<\epsilon <1$, this example needsThe ceiling function makes the trial count an integer. Four trials give $(2/5{)}^4=16/625>1/100$, while six give $64/15625<1/100$; five still give $32/3125>1/100$, so six is the first count below one percent. This is an exact error guarantee for each run on $G$, rather than an observed success rate.