Chapter 8 - Randomization

The concept of chance has been a subject of philosophical inquiry and scientific investigation for centuries. While classical physics often favored a deterministic view, the 20th century, particularly with quantum mechanics and evolutionary biology, embraced randomness as an inherent aspect of nature. In computer science, too, randomness has emerged not as a sign of incomplete knowledge, but as a powerful tool for designing algorithms that are often simpler, more efficient, and more robust than their deterministic counterparts. Unlike deterministic algorithms that follow a fixed path, randomized algorithms can “explore” possibilities, often finding solutions much faster or handling adversarial inputs more effectively.

In previous chapters, we’ve seen the limitations of deterministic algorithms, especially when facing NP-hard problems or adversarial inputs. Randomized algorithms introduce an element of chance into their logic, allowing them to make choices based on random bits. This unpredictability can help algorithms escape worst-case scenarios, achieve significant speedups, or solve problems that are otherwise intractable.

This chapter explores the fundamental ideas behind randomized algorithms. We will start with a brief review of elementary probability theory, then demonstrate the power of randomization through practical examples: an efficient communication protocol for comparing large databases, a randomized primality test, and a method for checking polynomial equivalence. These examples will illustrate key paradigms like the method of frequent witnesses and the method of fingerprints, showcasing how randomness can lead to surprisingly effective solutions.

8.1 Aims

By the end of this chapter, you will be able to:

• Understand Elementary Probability: Grasp basic concepts of probability spaces, distributions, and independent events.
• Model Randomized Algorithms: Understand how randomized algorithms are formally defined and analyzed.
• Appreciate Efficiency Gains: See how randomization can lead to algorithms that are exponentially more efficient than their deterministic counterparts for certain tasks.
• Apply the Method of Frequent Witnesses: Learn this paradigm for designing randomized algorithms, exemplified by the Solovay-Strassen primality test.
• Apply the Method of Fingerprints: Understand this technique for solving equivalence problems, demonstrated through polynomial equivalence testing.
• Analyze Error Probability: Learn how to analyze and reduce the error probability of randomized algorithms through repetition.

---

8.2 Elementary Probability Theory

To understand randomized algorithms, a basic grasp of probability is essential.

Definition 8.1 (Probability Space)

A probability space is a pair $(S,\text{Prob})$, where:

1. $S$ is a finite set of elementary events (all possible outcomes of an experiment). (Think of these as the most basic, indivisible results, like “rolling a 3” on a die.)
2. $\text{Prob}:\mathcal{P}(S)\to [0,1]$ is a probability distribution (or measure) that assigns a probability to each event (subset of $S$), satisfying:
   • $\text{Prob}(\{x\})\ge 0$ for every elementary event $x\in S$.
   • $\text{Prob}(S)=1$. (This means that one of the possible outcomes must occur.)
   • $\text{Prob}(X\cup Y)=\text{Prob}(X)+\text{Prob}(Y)$ for any two disjoint events $X,Y\subseteq S$.

The probability of an event $X\subseteq S$ is the sum of the probabilities of its elementary events: $\text{Prob}(X)={\sum }_{x\in X}\text{Prob}(\{x\})$. A uniform probability distribution assigns equal probability to all elementary events: $\text{Prob}(\{x\})=1/|S|$ for all $x\in S$.

Exercise 8.1 (Properties of Probability)

Prove the following properties for any probability space $(S,\text{Prob})$:

1. $\text{Prob}(\varnothing )=0$.
2. $\text{Prob}(S\setminus X)=1-\text{Prob}(X)$ for any $X\subseteq S$.
3. If $X\subseteq Y$, then $\text{Prob}(X)\le \text{Prob}(Y)$.
4. $\text{Prob}(X\cup Y)=\text{Prob}(X)+\text{Prob}(Y)-\text{Prob}(X\cap Y)$.

Modeling Randomized Algorithms

A randomized algorithm can be viewed in two ways: (These perspectives are equivalent and offer different insights into how randomness is incorporated.)

1. As a nondeterministic algorithm where each nondeterministic choice is made with a certain probability. The probability of a computation path is the product of the probabilities of its individual random decisions.
2. As a probability distribution over a set of deterministic algorithms. This is often implemented by providing a deterministic algorithm with a sequence of random bits as an additional input. Each sequence of random bits effectively selects a specific deterministic execution path.

The error probability of a randomized algorithm is typically defined as the maximum probability of producing an incorrect output over all possible inputs of a given size. (This is a crucial metric, as it quantifies the reliability of the algorithm’s probabilistic choices.)

---

8.3 A Randomized Communication Protocol

Consider the task of comparing the contents of two large databases, $x$ and $y$, stored on two different computers, RI and RII. Both databases contain $n$ bits. A deterministic protocol would require exchanging $\Omega (n)$ bits in the worst case to guarantee correctness. For $n=10^{16}$ bits, this is infeasible.

Here’s a randomized protocol that achieves exponential efficiency.

Stochastic Communication Protocol R

Initial situation: RI has an $n$-bit number $x$, RII has an $n$-bit number $y$.

1. RI chooses a prime number $p$ uniformly at random from the set of primes $\le n^2$.
2. RI calculates $s=\text{Number}(x)(\mathrm{mod}p)$ and sends $(s,p)$ to RII.
3. RII calculates $q=\text{Number}(y)(\mathrm{mod}p)$.
   • If $q\ne s$, RII outputs “unequal”.
   • If $q=s$, RII outputs “equal”.

Analysis of Protocol R

• Communication Complexity: RI sends $s$ and $p$. Since $s\le p<n^2$, the length of the message is $O(\log (n^2))=O(\log n)$ bits. For $n=10^{16}$, this is about $4\cdot {\log }_2(10^{16})\approx 256$ bits, a tiny message. (This logarithmic communication is a massive improvement over the $O(n)$ bits required by deterministic protocols, especially for very large $n$.)
• Error Probability:
  • If $x=y$: Then $\text{Number}(x)=\text{Number}(y)$, so $s=q$ for any $p$. RII always outputs “equal”. Error probability is 0.
  • If $x\ne y$: RII outputs “equal” (a wrong answer) only if $s=q$, which means $\text{Number}(x)(\mathrm{mod}p)=\text{Number}(y)(\mathrm{mod}p)$. This implies $p$ divides $|\text{Number}(x)-\text{Number}(y)|$. (This is the only way for a mismatch to go undetected: if the difference between the numbers happens to be a multiple of the chosen prime $p$.) Let $D=|\text{Number}(x)-\text{Number}(y)|$. Since $x\ne y$, $D\ne 0$. Also, $D<2^n$. A number $D$ has at most ${\log }_{2}D$ distinct prime factors. So $D$ has at most $O(n)$ prime factors. The probability that a randomly chosen prime $p\le n^2$ divides $D$ is at most $\frac{\text{number of prime factors of }D}{\text{number of primes }\le n^2}\approx \frac{n}{\pi (n^2)}\approx \frac{n}{n^2/\ln (n^2)}=\frac{\ln (n^2)}{n}=\frac{2\ln n}{n}$. For $n=10^{16}$, this error is extremely small, around $0.369\cdot 10^{-14}$.

Error Reduction by Repetition

The error probability can be further reduced by repeating the protocol multiple times with independent random choices. If we repeat the protocol $k$ times, and all $k$ choices of $p_i$ lead to $s_i=q_i$, the error probability drops to $(\frac{2\ln n}{n}{)}^k$. For $k=10$, the error for $n=10^{16}$ becomes less than $10^{-140}$.

This demonstrates a key advantage of randomized algorithms: they can achieve extremely low error probabilities with minimal communication or computation, often exponentially better than deterministic approaches.

---

8.4 The Method of Frequent Witnesses and the Randomized Primality Test

The efficiency of Protocol R stems from the method of frequent witnesses.

• A witness for a property is additional information that allows efficient deterministic verification of that property. (Think of it as a piece of evidence that quickly confirms a claim.)
• For a randomized algorithm, we need a set of witness candidates such that, for any input, a sufficiently large fraction of these candidates are actual witnesses. (This “frequent witnesses” property is what makes random sampling effective: you’re likely to pick a witness by chance.)

The Primality Test

Determining the primality of a large number $n$ is a fundamental problem in cryptography. The naive deterministic algorithm (trial division up to $\sqrt{n}$) is too slow.

Fermat’s Little Theorem provides a basis for a randomized test:

Theorem 8.1 (Fermat's Little Theorem)

For every prime number $p$ and every integer $a$ such that $\text{gcd}(a,p)=1$, it holds that $a^{p-1}\equiv 1(\mathrm{mod}p)$.

If $n$ is composite, it is possible that $a^{n-1}\equiv 1(\mathrm{mod}n)$ for some $a$. Such $n$ are called Carmichael numbers. (These numbers are “Fermat pseudoprimes” and can fool the basic Fermat test, making it unreliable for proving primality.) A stronger test is needed.

For an odd number $n$ with odd $(n-1)/2$ (i.e., $n\equiv 3(\mathrm{mod}4)$):

Theorem 8.2

1. If $n$ is prime, then $a^{(n-1)/2}\equiv \pm 1(\mathrm{mod}n)$ for all $a\in \{1,\dots ,n-1\}$.
2. If $n$ is composite, then $a^{(n-1)/2}\not\equiv \pm 1(\mathrm{mod}n)$ for at least half of the numbers $a\in \{1,\dots ,n-1\}$.

This theorem defines a “witness” for compositeness: an $a$ such that $a^{(n-1)/2}\not\equiv \pm 1(\mathrm{mod}n)$.

Solovay-Strassen Primality Test

Input: An odd number $n$ with odd $(n-1)/2$.

1. Choose $a$ uniformly at random from $\{1,\dots ,n-1\}$.
2. Calculate $x:=a^{(n-1)/2}(\mathrm{mod}n)$. (This is done efficiently using repeated squaring in $O({\log }^{2}n)$ time).
3. If $x\in \{1,n-1\}$, output “prime number”.
4. Else, output “not a prime number”.

Error Analysis of Solovay-Strassen

• If $n$ is prime: The algorithm always outputs “prime number”. Error probability is 0.
• If $n$ is composite: The probability that a randomly chosen $a$ is not a witness (i.e., $a^{(n-1)/2}\equiv \pm 1(\mathrm{mod}n)$) is at most $1/2$. So the error probability is at most $1/2$.

By repeating the test $k$ times with independent choices of $a$, the error probability for composite $n$ drops to $(1/2{)}^k$. For $k=20$, the error is less than $10^{-6}$. This makes the test highly reliable for practical purposes.

---

8.5 The Method of Fingerprints and the Equivalence of Two Polynomials

The method of fingerprints is a special application of the frequent witnesses paradigm, particularly useful for solving equivalence problems between large objects. (Think of a fingerprint as a much smaller, unique-enough identifier for a large object, allowing for quick comparisons without needing to compare the entire objects.)

Scheme of the Method of Fingerprints

Task: Decide if two objects $O_1$ and $O_2$ are equivalent.

1. Choose a random mapping $h$ from a suitable set of mappings $M$.
2. Calculate $h(O_1)$ and $h(O_2)$ (the “fingerprints”).
3. If $h(O_1)=h(O_2)$, output “equivalent”.
4. Else, output “not equivalent”.

The key idea is that fingerprints $h(O_i)$ are significantly shorter representations of $O_i$, making their comparison much faster. The risk of error arises if $O_1\ne O_2$ but $h(O_1)=h(O_2)$ (a “collision”). The set $M$ must be chosen such that collisions are rare for non-equivalent objects. (This rarity is crucial; if collisions were common, the fingerprint wouldn’t be a reliable indicator of equivalence.)

Equivalence of Two Polynomials

Consider two polynomials $P_1(x_1,\dots ,x_n)$ and $P_2(x_1,\dots ,x_n)$ over a finite field ${\mathbb{Z}}_p$. We want to check if $P_1\equiv P_2(\mathrm{mod}p)$, meaning they evaluate to the same value for all inputs $({\alpha }_1,\dots ,{\alpha }_n)\in ({\mathbb{Z}}_p{)}^n$. Comparing coefficients directly requires converting to normal form, which can be exponentially slow.

Algorithm AQP (Algorithm for Polynomial Equivalence)

Input: Prime $p$, polynomials $P_1,P_2$ (degree at most $d$) over $n$ variables.

1. Choose $\alpha =({\alpha }_1,\dots ,{\alpha }_n)$ uniformly at random from $({\mathbb{Z}}_p{)}^n$.
2. Calculate fingerprints: $h_{\alpha }(P_1)=P_1({\alpha }_1,\dots ,{\alpha }_n)(\mathrm{mod}p)$ and $h_{\alpha }(P_2)=P_2({\alpha }_1,\dots ,{\alpha }_n)(\mathrm{mod}p)$.
3. If $h_{\alpha }(P_1)=h_{\alpha }(P_2)$, output "$P_1\equiv P_2$".
4. Else, output "$P_1\not\equiv P_2$".

Error Analysis of AQP

• If $P_1\equiv P_2$: The algorithm always outputs “equivalent”. Error probability is 0.
• If $P_1\not\equiv P_2$: Let $Q(x_1,\dots ,x_n)=P_1(x_1,\dots ,x_n)-P_2(x_1,\dots ,x_n)$. Since $P_1\not\equiv P_2$, $Q$ is not identically zero. The algorithm makes an error if $Q({\alpha }_1,\dots ,{\alpha }_n)\equiv 0(\mathrm{mod}p)$ for the randomly chosen $\alpha$. A key result (Theorem 8.4) states that for a non-zero polynomial $Q$ of $n$ variables and degree at most $d$, the number of roots in $({\mathbb{Z}}_p{)}^n$ is at most $n\cdot d\cdot p^{n-1}$. Thus, the probability of choosing a root $\alpha$ (and making an error) is at most $\frac{n\cdot d\cdot p^{n-1}}{p^n}=\frac{n\cdot d}{p}$. If we choose $p>2nd$, this error probability is less than $1/2$. Again, repeating the test $k$ times reduces the error to $(nd/p{)}^k$.

This method provides an efficient randomized solution for a problem for which no polynomial-time deterministic algorithm is known.

---

Summary

• Randomized algorithms leverage chance to achieve efficiency, simplicity, and robustness, often outperforming deterministic algorithms.
• They are modeled either as nondeterministic algorithms with probabilistic choices or as deterministic algorithms with random bit sequences as input.
• The Stochastic Communication Protocol R for database comparison demonstrates exponential efficiency gains over deterministic protocols, achieving extremely low error probabilities with minimal communication.
• The Method of Frequent Witnesses is a paradigm where an algorithm relies on finding a “witness” that efficiently verifies a property. If witnesses are frequent among candidates, random sampling is effective.
• The Solovay-Strassen Primality Test is a randomized algorithm based on frequent witnesses, efficiently determining if a number is prime with a controllable error probability.
• The Method of Fingerprints is a specialized technique for equivalence problems, where large objects are mapped to small “fingerprints” via random functions. Comparing fingerprints is efficient, with a small, controllable risk of collision.
• The Algorithm AQP for polynomial equivalence testing uses fingerprints to efficiently determine if two polynomials are equivalent, a problem for which deterministic polynomial-time algorithms are not known.
• Error amplification through repetition is a common technique to reduce the error probability of randomized algorithms to arbitrarily low levels.

Randomization is a powerful tool in algorithm design, offering practical solutions to problems that are otherwise intractable.

---

Previous Chapter: Chapter 7 - Algorithmics for Hard Problems Next Up: Chapter 9 - Communication and Cryptography

Exercises

Exercise 8.1 (Coin Tossing)

Model the experiment of five-fold coin tossing. What is the probability that the number of heads and the number of tails differ by at most 1?

Solution

The total number of outcomes is $2^5=32$. The number of heads and tails differ by at most 1 means:

• 3 Heads, 2 Tails (e.g., HHHTT): $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ ways.
• 2 Heads, 3 Tails (e.g., HHTTT): $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ ways. The total number of favorable outcomes is $10+10=20$. The probability is $20/32=5/8$.

Exercise 8.2 (Database Comparison)

Two computers have each stored a word of 18 bits. They use Protocol R to check for equality.

1. From how many prime numbers is one chosen randomly?

2. How many bits are communicated?

3. What is the error probability if the words are different?

Solution

1. $n=18$. Primes are chosen from $\{2,\dots ,n^2=18^2=324\}$. The number of primes $\pi (324)$ is 66.
2. Communication bits: $O(\log n)=O(\log 18)$. More precisely, the message contains $p<n^2=324$ and $s<p$. So, we need $\lceil {\log }_{2}324\rceil$ bits for $p$ and $\lceil {\log }_{2}324\rceil$ bits for $s$. $\lceil {\log }_{2}324\rceil =9$. Total bits: $9+9=18$.
3. Error probability: $\frac{2\ln n}{n}=\frac{2\ln 18}{18}\approx \frac{2\cdot 2.89}{18}\approx 0.32$. This is quite high for small $n$.

Exercise 8.3 (Solovay-Strassen Error Reduction)

How far can one reduce the error probability of the Solovay-Strassen algorithm if, instead of one attempt, $k$ independent attempts are made?

Solution

If $n$ is composite, each independent attempt has an error probability of at most $1/2$. If $k$ independent attempts are made, and all of them fail to find a witness (i.e., all of them output “prime number” for a composite $n$), the probability of this happening is at most $(1/2{)}^k$. So, the error probability is reduced to at most $2^{-k}$.

Exercise 8.4 (Polynomial Equivalence)

Are $P_1(x,y)=(x+y{)}^2$ and $P_2(x,y)=x^2+2xy+y^2$ equivalent over ${\mathbb{Z}}_p$? Describe how Algorithm AQP would test this.

Solution

Yes, they are equivalent. Algorithm AQP would:

4. Choose a prime $p$ (e.g., $p=7$).
5. Choose random values ${\alpha }_1,{\alpha }_2\in {\mathbb{Z}}_p$ (e.g., ${\alpha }_1=3,{\alpha }_2=5$).
6. Calculate $P_1(3,5)=(3+5{)}^2=8^2=64\equiv 1(\mathrm{mod}7)$.
7. Calculate $P_2(3,5)=3^2+2(3)(5)+5^2=9+30+25=64\equiv 1(\mathrm{mod}7)$.
8. Since $P_1(3,5)\equiv P_2(3,5)(\mathrm{mod}7)$, the algorithm would output "$P_1\equiv P_2$".

Since $P_1$ and $P_2$ are indeed equivalent, the algorithm will always output “equivalent” (error probability 0). If they were not equivalent, the probability of error would be at most $\frac{nd}{p}$, where $n=2$ (variables), $d=2$ (degree), so $\frac{4}{p}$. For $p=7$, this is $4/7$.