Advanced Algorithms · Lecture Notes

Chapter 7: Randomized Algorithms

Not every step of an algorithm has to be determined by the input. An algorithm can flip a coin, roll a die, or pick a random element of an array. This small change has surprising consequences. Quicksort, which slows down on sorted input, no longer stays slow on any particular input once it chooses its pivot at random. Whether a number of several hundred digits is prime can be decided in milliseconds, without ever looking at its factors, with a vanishingly small probability of error. The weakest cut of a graph can be found by merging random edges. The notes first introduce randomized algorithms, expected running time, and the probability tools needed. They then present the two basic kinds, Las Vegas and Monte Carlo algorithms, and show how repetition reduces the error probability. After that the examples are studied one by one. The first are the Fisher–Yates shuffle, the bias of the naive shuffle, and BogoSort. They are followed by quicksort with a random pivot, the expected number of comparisons, and randomized selection. The last examples are π estimation by the Monte Carlo method, the Miller–Rabin primality test, and Karger's minimum cut algorithm. The notes end with pseudorandom number generators.

Learning outcomes

Concepts
Define a randomized algorithm; distinguish expected running time from average-case running time; explain the difference between Las Vegas and Monte Carlo algorithms.
Shuffling and BogoSort
Write the Fisher–Yates shuffle and prove that it produces every permutation with equal probability; show by counting why the naive shuffle is biased; compute the expected Θ(n · n!) running time of BogoSort.
Randomized QuickSort
Trace partitioning with a random pivot step by step; justify the expected O(n log n) and worst-case O(n²) running times; compute the expected number of comparisons with indicator variables; explain the expected O(n) running time of randomized selection.
Monte Carlo
Compute the error probability in π estimation, the Miller–Rabin primality test, and Karger's minimum cut algorithm, and reduce it with independent repetitions.

7.1Randomness and algorithms

7.1.1Decisions based on chance

The word algorithm usually brings to mind a fully determined sequence of steps. Given the same input, the algorithm takes the same steps in the same order and produces the same result. Such algorithms are called deterministic. For some problems, however, it pays to introduce chance into the algorithm's decisions on purpose. At some point the algorithm flips a coin, rolls a die, or picks one of the elements of an array at random, and continues along its path according to that choice.

Games of chance are the most familiar example of this idea. Consider a game played with two dice. If the total is 7 or 11, the player wins; otherwise the dice are rolled again. Two dice have 36 equally likely outcomes. The outcomes with total 7 are (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), and (6, 1); there are 6 of them. The outcomes with total 11 are (5, 6) and (6, 5); there are 2 of them.

P(7) = 6/36,   P(11) = 2/36,   P(win) = 8/36 = 2/9 ≈ 0.22

= 7win: 7 or 11
Figure 7.1: Two dice: 3 and 4, total 7. The player wins on this roll.

The probability of winning on one roll is about 0.22. How many rolls does the player make before winning? This number differs from game to game: sometimes the first roll wins, sometimes ten are needed. But its average is known. Since every roll has the same winning probability and the rolls are independent of each other, the expected number of rolls is 1 / (2/9) = 4.5. This result comes from the geometric distribution. In 200,000 games played with a fixed seed (random.Random(42)), the average number of rolls came out as 4.502, in agreement with the formula.

Two observations from the dice game recur throughout these notes. First, how long a single run will take is not known in advance; what is known is the expected value of the running time. Second, the expected value is found by a probability computation and can be checked with a long simulation.

7.1.2Randomized algorithms and expected running time

Definition 7.1

A randomized algorithm is an algorithm that uses random numbers in addition to its input and makes some of its decisions according to these numbers. Two runs on the same input may follow different steps; the running time, and sometimes the output itself, varies from run to run.

Figure 7.2 shows this structure. The algorithm has two inputs: the input of the problem and a source of random bits. Even when the input stays the same, the random bits change; so the path the algorithm follows can change too.

InputRandom bitsAlgorithm(chance in its decisions)Output
Figure 7.2: A randomized algorithm: the input and random bits enter the algorithm, and the output is produced. The algorithm's decisions involve an element of chance.

The running time of a deterministic algorithm on a fixed input is a single number. For a randomized algorithm, on the same input the time is a random variable: it can take a different value in each run. So the analysis examines the expected value E[T(n)] of the time instead of a single number. There is an important detail here. The expectation is taken over the algorithm's own coin flips, not over the input. The input is fixed and may even be the worst one; the probability comes only from the random choices the algorithm makes.

Definition 7.2

The expected running time of a randomized algorithm, for each input of size n, is the expected time taken over the algorithm's random choices. By the expected running time of the algorithm we mean the largest of these values over all inputs:

Texp(n) = max|x| = n E[ T(x) ]

This definition must not be confused with average-case analysis. Average-case analysis is applied to a deterministic algorithm and makes an assumption about the inputs: for example, it assumes that every ordering of the array is equally likely. If the assumption fails, the result is invalid too. In real life data often arrive sorted or nearly sorted, so the equal-probability assumption is often violated. The expected running time, on the other hand, makes no assumption about the input. It holds for each input separately, even for the worst one.

Example 7.1

Quicksort that always chooses the first element of the subarray as pivot runs in O(n log n) time on average if the input is in random order. This is an average-case result. If the same algorithm is given a sorted array of 10 elements, it makes exactly 45 comparisons on every run, because this input produces the worst case every time. The version that chooses the pivot at random, on the same sorted array, makes about 24.4 comparisons on average, and this value does not depend on the order of the input. For a sorted array, a reverse-sorted array, or any other arrangement, the expected value is the same. The value 24.4 comes from the formula for the expected number of comparisons, 2(n + 1)Hₙ − 4n.

7.1.3Why randomness?

Randomness looks at first like a source of uncertainty. Even so, it brings four important gains in algorithm design.

Protection against bad inputs. Deterministic quicksort that chooses the first element as pivot falls to O(n²) time on a sorted array. Sorted arrays are very common in practice. An attacker who knows the rules of the algorithm can deliberately prepare the worst input. When the pivot is chosen at random, no input is consistently bad. The bad case arises only if the algorithm's own choices go unluckily, and the probability of that is very small.

Simplicity. A randomized algorithm is often much shorter and easier to understand than the best known deterministic algorithm. Karger's minimum cut algorithm is a loop of a few lines. The randomized selection algorithm is a small modification of quicksort. The deterministic solutions to these problems are either long and intricate or slow in practice.

Speed. The Miller–Rabin test decides the primality of numbers with hundreds of digits within milliseconds. The error probability can be made as small as desired. Key generation in cryptography relies on this speed.

Sampling and symmetry breaking. Some tasks are either very hard or impossible without randomness. Monte Carlo simulations, drawing a random sample from a large dataset, and electing a leader among identical processes in a distributed system are examples. Two identical processes running the same program cannot be told apart by deterministic rules; a random number breaks this symmetry.

These gains have a price. The guarantee for time or accuracy is no longer exact but probabilistic. One cannot say "this algorithm is always O(n log n)"; one says "its expected time is O(n log n)" or "the probability of error is less than 10⁻¹²". The algorithm also needs a good random number generator. Flaws in the generator break the assumptions of the analysis.

7.1.4Probability tools

A few basic probability tools are used again and again in analyzing randomized algorithms. Table 7.1 summarizes them; each is then explained with a short example.

Table 7.1: Probability tools used in these notes.
ConceptDefinition / ruleExample
Expected valueE[X] = Σ x · P(X = x)the expected value of one die is 3.5
LinearityE[X + Y] = E[X] + E[Y] (independence not required)total of two dice: 7
Indicator variableXA = 1 if A occurs, 0 otherwise; E[XA] = P(A)in QuickSort, "were i and j compared?"
Geometric distributionin independent trials with success probability p, the expected number of trials until the first success is 1/pBogoSort: p = 1/n! → n! shuffles
Independent repetitionthe probability that all of k independent trials, each failing with probability q, fail is qᵏMiller–Rabin: (1/4)ᵏ
Markov's inequalityif X ≥ 0, then P(X ≥ c · E[X]) ≤ 1/cLas Vegas → Monte Carlo

Expected value. Each value a random variable can take is multiplied by its probability and the products are summed. Each face of a die comes up with probability 1/6: E[X] = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5. The expected value itself may never be observed; no die shows 3.5. The expected value is the value the average approaches when many trials are made.

Linearity. The expected value of the sum of two random variables is the sum of their expected values. For the total of two dice, 3.5 + 3.5 = 7 is obtained; there is no need to add up the 36 outcomes one by one. The strongest feature of this rule is that it does not require independence. The rule holds even when the variables depend on each other. The analysis of quicksort relies on exactly this property: the comparisons are not independent of each other, but the expected total is still the sum of the individual expected values.

Indicator variable. For an event A, XA takes the value 1 if the event occurs and 0 if it does not. Its expected value is 1 · P(A) + 0 · (1 − P(A)) = P(A). If we are to count how many times something happens, we write an indicator for each possible event, the count is the sum of the indicators, and by linearity the expected value reduces to the sum of the probabilities. In quicksort the question "were zᵢ and zⱼ compared?" is such an indicator.

Geometric distribution. Let each trial have success probability p and let the trials be independent. If X is the number of trials up to the first success, then P(X = k) = (1 − p)ᵏ⁻¹ p and E[X] = 1/p. This result can also be seen by a short argument. The first trial is always made. With probability p the job is done; with probability 1 − p the process starts over and the same expected value is spent again: E = 1 + (1 − p) E, hence E = 1/p. In the dice game p = 2/9 and the expected number of rolls is 4.5.

Independent repetition. If a trial fails with probability at most q, the probability that all of k independent trials fail is at most qᵏ. As long as q is less than 1, this value decreases exponentially in k. The error of Monte Carlo algorithms is reduced in this way.

Markov's inequality. A random variable that takes no negative values exceeds c times its expected value with probability at most 1/c. The reason is simple: when X is at least c · E[X], it contributes at least c · E[X] · P(X ≥ c · E[X]) to the expected value. This contribution cannot exceed E[X]. The inequality gives a tail bound from the expected value alone, knowing nothing about the distribution; so it is crude but valid everywhere.

Common mistake

Looking for independence for linearity. E[X + Y] = E[X] + E[Y] is always true. Independence is needed only for products: the equality E[XY] = E[X] E[Y] holds in general only for independent variables. This is why summing dependent indicators in the comparison analysis of quicksort is no problem.

7.2Las Vegas and Monte Carlo

7.2.1Two kinds of randomized algorithms

Randomized algorithms fall into two groups according to what the randomness affects. In the first group the result is always correct and only the running time depends on chance. In the second group the running time is bounded, but the result may be wrong with a small probability. These groups are named after two cities famous for their casinos.

Definition 7.3

A Las Vegas algorithm always gives the correct result; its running time is random and its expected time is analyzed. A Monte Carlo algorithm, on the other hand, finishes within a predetermined time bound; its result may be wrong with a small probability.

Table 7.2: Comparison of Las Vegas and Monte Carlo algorithms.
Las VegasMonte Carlo
Correctnessalways the correct resulta wrong result with small probability
Running timerandom; the expected time is analyzedbounded (a deterministic upper bound)
What is randomhow long it takeswhether the result is correct
Examplesrandomized QuickSort, QuickSelect, BogoSort, Fisher–YatesMiller–Rabin, Karger's minimum cut, π estimation

Quicksort with a random pivot is a Las Vegas algorithm. Whatever pivot is chosen, the array ends up correctly sorted. Unlucky pivots only prolong the work. BogoSort is also Las Vegas: when it stops, the array is certainly sorted, but when it will stop is not known. The Fisher–Yates shuffle is a slightly different case. Its running time is exactly n − 1 swaps on every run; what is random is the permutation produced. In this algorithm the "correct result" is not a single array but the desired probability distribution, and this distribution is achieved exactly every time. So it too is placed in the Las Vegas group.

The Miller–Rabin test, on the other hand, is Monte Carlo. The number of rounds is fixed in advance and each round performs a bounded number of multiplications. But the answer "prime" may be wrong with a small probability. Karger's algorithm also performs a fixed number of contractions and sometimes returns a cut that is not minimum. The π estimate throws the desired number of points and only approaches the true value.

7.2.2One-sided and two-sided error

Monte Carlo algorithms are also classified by the direction of the error. In a decision problem, that is, a problem whose answer is "yes" or "no", if the algorithm can be wrong on only one of the answers, the error is one-sided. Miller–Rabin is the typical example. If the test says "composite", this is certain, because it has found concrete evidence that the number is not prime. Only the answer "prime" can be wrong. One-sided error has a great advantage: after repetitions, even a single "composite" answer settles the matter.

If the error can occur in both directions, it is two-sided. Numerical simulations such as the π estimate can deviate both above and below the true value. For such algorithms the margin of error shrinks as the number of samples grows, but the direction in which a single run deviates is not known. The error of Karger's algorithm is also one-sided, but in a different direction: the cut found can never be smaller than the minimum, only larger. So the smallest of several runs is taken.

7.2.3Reducing the error probability

The error probability of a Monte Carlo algorithm can be large in a single run. But if the algorithm is run many times with independent random choices, the error shrinks quickly. This technique is called amplification.

Theorem 7.1 (Amplification by repetition)

Let a Monte Carlo algorithm with one-sided error have error probability at most q in a single round. Run the algorithm k times independently, and if one of the rounds gives the definite answer, choose that answer. The error probability of this combined algorithm is at most qᵏ.

The combined algorithm errs only when all rounds err. Because the rounds use independent random choices, this probability is the product of the individual error probabilities and is at most q · q · … · q = qᵏ. □

In Miller–Rabin, for a composite number the probability of error in one round is at most 1/4. After twenty rounds the error probability drops to at most 4⁻²⁰ ≈ 9.1 · 10⁻¹³. This is smaller than the probability of a spontaneous bit error occurring in computer hardware. Figure 7.3 shows on a logarithmic scale how the bound falls with the number of rounds: each new round divides the bound by 4.

110−110−210−310−410−510−610−71234567891011number of rounds k≈ 9.5 · 10⁻⁷
Figure 7.3: The Miller–Rabin error bound 4⁻ᵏ on a logarithmic scale. At k = 9 the bound is 3.8 · 10⁻⁶; at k = 10 it drops to 9.5 · 10⁻⁷, falling below 10⁻⁶ for the first time.
Example 7.2

At least how many rounds are needed to push the error probability of Miller–Rabin below 10⁻⁹? The condition is 4⁻ᵏ < 10⁻⁹, that is, 4ᵏ > 10⁹. 4¹⁴ = 268,435,456 is not enough. 4¹⁵ = 2³⁰ = 1,073,741,824, however, exceeds 10⁹. At least 15 rounds are needed. The same computation gives 10 rounds for 10⁻⁶. Since the bound falls to a quarter, not a half, the number of rounds needed is about log₄ 10 ≈ 1.66 times the number of decimal digits desired.

In Karger's algorithm the success probability of a single run is at least 2/(n(n − 1)). This is a small number; for a graph with 100 vertices it is about 0.0002. But if the algorithm is repeated n(n − 1)/2 · ln n times, the probability that all runs fail falls to at most 1/n. However small the success probability is, if it has a known lower bound greater than zero, repetition raises it to the desired level.

7.2.4Converting between the two kinds

Las Vegas and Monte Carlo algorithms can be converted into each other. Both conversions are used in practice.

From Las Vegas to Monte Carlo. A Las Vegas algorithm with expected running time E[T] is stopped after 2 · E[T] steps. If the algorithm has finished in this time, its answer is correct. If not, "no answer" is returned. By Markov's inequality, P(T ≥ 2 E[T]) ≤ 1/2; that is, the new algorithm fails to answer with probability at most 1/2. Its running time is now strictly bounded. If the bound is taken as c · E[T], the probability of no answer is at most 1/c.

Example 7.3

On an array of four distinct elements, the number of shuffles BogoSort makes follows a geometric distribution with success probability p = 1/24 and has expected value 24. Let the algorithm be stopped after 48 shuffles. Markov's inequality gives the bound 1/2 on the probability of no answer. The true probability is much smaller: the probability that all of the first 48 shuffles fail is (23/24)⁴⁸ ≈ 0.130. A simulation of 100,000 trials with a fixed seed gave 0.129. The Markov bound is correct but crude, because it uses only the expected value of the distribution.

From Monte Carlo to Las Vegas. If the answer of a Monte Carlo algorithm can be verified quickly, the algorithm is repeated until a verified answer is found. For example, the factors found by a randomized algorithm that tries to factor a number are easily checked by multiplying them. If the success probability of a single trial is p, the expected number of trials is 1/p by the geometric distribution. The result is always correct; only the running time becomes random. For p = 1/3 the expected number of repetitions is 3; in a simulation of 100,000 trials with seed 42 the average came out as 2.994.

Common mistake

Repeating an unverifiable answer "until it comes out right". The "prime" answer of Miller–Rabin cannot be verified quickly; no short proof of primality is at hand. So Miller–Rabin cannot be converted into Las Vegas this way. The conversion works only when the answer itself can be checked cheaply.

7.3Shuffling

7.3.1The problem and the correctness criterion

Putting the elements of an array into a random order, that is, shuffling, is a common task. In card games the deck is shuffled, music players play a playlist in shuffled order, and algorithm tests generate randomly ordered test data. Another form of quicksort with a random pivot is to shuffle the array first and then run deterministic quicksort.

What does it mean for a shuffle to be "correct"? A weak criterion is that each element is equally likely to be in each position. The strong and actual criterion is that each of the n! different orderings of n elements, that is, each permutation, is produced with probability exactly 1/n!. Such a shuffle is called uniform. The strong criterion includes the weak one; the converse is not true. For example, let a method turn the array [1, 2, 3] into only one of its three cyclic shifts: [1, 2, 3], [2, 3, 1], or [3, 1, 2]. Let the three results be equally likely. This method puts each element in each position with probability 1/3. But it never produces three of the six permutations.

Table 7.3: The number of permutations n! grows very fast.
nn! permutations
36
424
103,628,800
52≈ 8.07 · 10⁶⁷

The number of permutations of a 52-card deck is about 8 · 10⁶⁷. This number is so large that the order of a well-shuffled deck has most likely never been seen in any deck before. The shuffling algorithm must choose from this huge set with equal probability, yet it cannot list the permutations one by one. The solution is to break the choice into small steps.

7.3.2The Fisher–Yates shuffle

The Fisher–Yates shuffle, also known as the Knuth shuffle, works like this: the element that will go to the last position of the array is chosen at random among all the elements and placed there. Then the element for the second-to-last position is chosen among the elements not yet placed. This continues down to the first position. At each step one position becomes final and never changes again.

static void shuffle(int[] a) {
  for (int i = a.length - 1; i > 0; i--) {
    int j = rng.nextInt(i + 1); // 0 ≤ j ≤ i
    int t = a[i]; a[i] = a[j]; a[j] = t;
  }
}

In the code, rng is a shared java.util.Random object created once in the class. The loop starts at i = n − 1 and goes down to i = 1. In each round rng.nextInt(i + 1) produces a uniformly distributed integer j between 0 and i (both included). Then a[i] and a[j] are swapped. j = i can also come up; in that case the element is swapped with itself and stays in place. This possibility is important: an element staying where it started is also a valid outcome, and the shuffle must produce this outcome with the right probability too.

The loop does not run for i = 0. At that point a single element is left and there is nothing else to choose. A total of n − 1 swaps are made and each swap takes constant time. The running time is the same on every run: Θ(n). The extra memory is O(1); the shuffle is done in place. What varies is the result itself, not the running time. Java's Collections.shuffle(list) method also uses this algorithm.

Example 7.4

Let the array a = [1, 2, 3, 4, 5] be shuffled. Let the random number generator give the values j = 1, 3, 0, 1 in turn. Table 7.4 gives each step.

Table 7.4: Fisher–Yates trace, a = [1, 2, 3, 4, 5]. Bold values are positions that are final.
ichoice rangejoperationarray
———start[1, 2, 3, 4, 5]
4a[0..4], 5 elements1a[4] ↔ a[1][1, 5, 3, 4, 2]
3a[0..3], 4 elements3j = i, no change[1, 5, 3, 4, 2]
2a[0..2], 3 elements0a[2] ↔ a[0][3, 5, 1, 4, 2]
1a[0..1], 2 elements1j = i, no change[3, 5, 1, 4, 2]

In the first round each of the 5 elements could have gone to the last position with probability 1/5; the chosen j = 1 is the value 2. After the swap a[4] = 2 is final. In the second round j = 3 = i came up, so the value 4 stays in place. In the third round a[0] = 1 is chosen among three elements and goes to a[2]; the old a[2] = 3 moves to the front. In the last round j = i comes up again. a[0] = 3 is the only element left and settles by itself. The result is [3, 5, 1, 4, 2]. The code, run in Java with a generator that returns the same j values, gives this array as well.

1051324324 3051124324
Figure 7.4: Two moments of the Fisher–Yates trace. Left, the array after the first swap: a[4] = 2 is final (green). Right, when the loop ends: [3, 5, 1, 4, 2]; all positions are final.

7.3.3Proof of correctness

The correctness of Fisher–Yates is shown by a short counting argument. In the round i = n − 1 the algorithm chooses one of n values, in the round i = n − 2 one of n − 1 values, and so on; in the last round i = 1 one of 2 values is chosen. The number of possible sequences of choices is n · (n − 1) · … · 2 = n!, and every sequence of choices is equally likely.

Theorem 7.2 (Fisher–Yates is uniform)

The Fisher–Yates shuffle produces each of the n! permutations of an array of distinct elements with probability exactly 1/n!.

There is a one-to-one correspondence between sequences of choices and permutations. Let a desired permutation be given. The element in the last position is determined by this permutation. In the round i = n − 1 that element is at exactly one position of the array; that position must be j. After the swap the same argument is repeated for the remaining front part of n − 1 elements. Thus for every permutation there is a single sequence of choices that produces it. There are n! sequences of choices and n! permutations. Since the probability of each sequence of choices is (1/n) · (1/(n − 1)) · … · (1/2) = 1/n!, the probability of each permutation is also 1/n!. □

The proof shows one thing clearly: the uniformity of the shuffle comes from the number of equally likely paths being equal to the number of permutations. In the five-element example the number of possible sequences of draws is 5 · 4 · 3 · 2 = 120 = 5!; each permutation is obtained exactly once. The array [1, 2, 3] was shuffled 600,000 times with a fixed seed (new Random(42)). Each of the six permutations came up between 99,754 and 100,315 times. The expected value is 100,000, and the deviations are at the level of random fluctuation expected for this many trials.

7.3.4The naive shuffle is biased

The first way of writing a shuffle that comes to mind is this: swap each position with a random position of the array. The code looks short and innocent.

// WRONG: for each i, pick from 0..n-1
for (int i = 0; i < n; i++) {
  int j = rng.nextInt(n);
  swap(a, i, j);
}

In this code, for each i the index j is chosen not from a shrinking range as in Fisher–Yates but always from 0..n − 1, the range of the whole array. The array really does get mixed at every round, but the result is not uniform. The reason is seen by counting. Each of the n draws can take n different values. The number of equally likely paths is nⁿ. The number of permutations, however, is n!. If every permutation were equally likely, each would be produced by exactly nⁿ / n! paths, and this number would be an integer.

For n = 3 there are 3³ = 27 paths and 3! = 6 permutations. 27 is not divisible by 6; therefore the permutations cannot be equally likely. This argument holds in general for n ≥ 3. The number n − 1 divides n! but has no common divisor with nⁿ; so nⁿ / n! is never an integer.

Table 7.5: The 27 sequences of draws of the naive shuffle on the array [1, 2, 3], counted one by one. The last column is the result of a simulation of 600,000 trials with seed 42.
resultpathsprobabilityshould besimulation (600,000)
12344/27 ≈ 0.1481/6 ≈ 0.16788,843
13255/27 ≈ 0.1851/6 ≈ 0.167110,659
21355/27 ≈ 0.1851/6 ≈ 0.167112,175
23155/27 ≈ 0.1851/6 ≈ 0.167110,602
31244/27 ≈ 0.1481/6 ≈ 0.16789,008
32144/27 ≈ 0.1481/6 ≈ 0.16788,713

In Table 7.5 the results 132, 213, and 231 are obtained by five paths each and the other three by four paths each. The expected counts are 600,000 · 5/27 ≈ 111,111 and 600,000 · 4/27 ≈ 88,889; the simulation is very close to these values. The difference may look small, but it is systematic: it does not disappear as the number of trials grows; on the contrary, it becomes more pronounced. In a card game or a statistical experiment this bias corrupts the results.

The naive shuffle does not satisfy even the weak criterion. Read off the positions of the value 3 from the table: the probability of landing in the first position is (4 + 4)/27 = 8/27, in the middle position 10/27, and in the last position 9/27. All three should have been 1/3. For an array of four elements the situation is even messier: 4⁴ = 256 paths are distributed over 24 permutations. 256/24 ≈ 10.67 is not an integer; an exact count made in Java showed permutations produced by at least 8 and at most 15 paths.

Common mistake

Checking the uniformity of a shuffle by eye. The outputs of the naive shuffle look perfectly random to the eye. The bias shows up only by counting or with a large number of trials. The correct pattern is rng.nextInt(i + 1): the range of choice shrinks in every round and stays limited to the elements not yet placed.

7.3.5A one-character bug: nextInt(i)

What happens if rng.nextInt(i) is mistakenly written in the Fisher–Yates code instead of rng.nextInt(i + 1)? In this case j can be at most i − 1; a[i] is always swapped with an element before it, and no element can stay in place. For the array [1, 2, 3], in the round i = 2 we have j ∈ {0, 1}, and in the round i = 1 we must have j = 0. There are only 2 · 1 = 2 paths.

Table 7.6: All paths for the array [1, 2, 3] with nextInt(i).
j at i = 2after the first swapj at i = 1result
0[3, 2, 1]0[2, 3, 1]
1[1, 3, 2]0[3, 1, 2]

Each of the two results comes up with probability 1/2. The other four permutations, including the sorted [1, 2, 3], are never produced. This modified method has a name of its own: Sattolo's algorithm. It produces, with equal probability, the (n − 1)! permutations that consist of a single cycle. In some applications exactly this is wanted; for example, when a loop is to be built in which every element is sent to another element and nobody lands on itself. But it is not a uniform shuffle. A difference of a single character completely changes the probability distribution of the output.

7.4BogoSort

7.4.1The algorithm

BogoSort is one of the worst-performing sorting algorithms known. It is also called "stupid sort" or permutation sort. Its logic can be stated in one sentence: shuffle the list at random until it is sorted. It is not used in real applications. But it is the simplest example of Las Vegas algorithms and of the geometric distribution; that is why it is instructive.

  1. Is the list sorted? If yes, stop.
  2. If not, shuffle the list at random and go back to step one.
static void bogoSort(int[] a) {
  while (!isSorted(a))
    shuffle(a);         // Fisher–Yates
}
static boolean isSorted(int[] a) {
  for (int i = 0; i + 1 < a.length; i++)
    if (a[i] > a[i + 1]) return false;
  return true;
}

The method isSorted checks adjacent pairs of elements from left to right. If in some pair the left element is larger than the right, the array is not sorted and the method immediately returns false. If all pairs are in order, it returns true. In the worst case it makes n − 1 comparisons: O(n). bogoSort shuffles an unsorted array with Fisher–Yates and repeats the check. It is important to use a correct method for shuffling; with the naive shuffle some permutations come up more rarely and the analysis becomes invalid.

sorted?yesstopnoshufflep = 1/n! → expected n! rounds
Figure 7.5: The BogoSort flow: if sorted, it stops; if not, it shuffles and asks again. The success probability of each round is p = 1/n! and the expected number of rounds is n!.

7.4.2One run

Example 7.5

Let the list [5, 2, 8, 4] be sorted with BogoSort. Each shuffle is done with Fisher–Yates. Table 7.7 gives all the steps of one run made with a seeded generator. In each row the first out-of-order adjacent pair found by isSorted is shown.

Table 7.7: A BogoSort run for [5, 2, 8, 4].
shufflearrayfirst inverted pairresult
0 (start)[5, 2, 8, 4]a[0] = 5 > a[1] = 2not sorted
1[5, 4, 2, 8]a[0] = 5 > a[1] = 4not sorted
2[8, 4, 5, 2]a[0] = 8 > a[1] = 4not sorted
3[4, 2, 8, 5]a[0] = 4 > a[1] = 2not sorted
4[2, 8, 4, 5]a[1] = 8 > a[2] = 4not sorted
5[5, 8, 2, 4]a[1] = 8 > a[2] = 2not sorted
6[8, 4, 2, 5]a[0] = 8 > a[1] = 4not sorted
7[2, 8, 5, 4]a[1] = 8 > a[2] = 5not sorted
8[2, 4, 5, 8]nonesorted, the algorithm stops

This run needed 8 shuffles. Of the 24 permutations of four elements only one is sorted; the expected number of shuffles is 24. This run was luckier than expected. Another run could finish in 3 shuffles or in 80. Note also that in most rounds isSorted stops at the first or second comparison. In a random array the probability that the first pair is inverted is 1/2; so the check takes far less than n − 1 comparisons on average. The shuffle, on the other hand, makes exactly n − 1 swaps in every round.

50218243permutation matrixcolumn: position · row: rank 20415283permutation matrixcolumn: position · row: rank
Figure 7.6: On the left the start [5, 2, 8, 4]; the red bars are the first inverted pair. On the right [2, 4, 5, 8] after the eighth shuffle. In the permutation matrix on the right, a dark cell shows the rank (row) and position (column) of a value; in the sorted array the diagonal fills in.

7.4.3Analysis

Let the elements be distinct. Since Fisher–Yates produces every permutation with probability 1/n!, the probability that a shuffle comes out sorted is p = 1/n!. The shuffles are independent of each other. The number of shuffles made until the sorted array is obtained follows the geometric distribution. Its expected value is 1/p = n!.

Each round contains one shuffle (O(n)) and one check (O(n)). The expected running time is therefore Θ(n · n!). In the literature this time is sometimes written as O((n + 1)!). The two expressions are of the same magnitude, because (n + 1)! = (n + 1) · n! and n + 1 and n differ only by a constant factor.

Table 7.8: The expected number of shuffles in BogoSort and the time on an imaginary machine that can make 10⁹ shuffles per second.
nexpected shuffles n!time
51200.12 µs
103,628,8003.6 ms
12479,001,6000.48 s
136,227,020,8006.2 s
151,307,674,368,000≈ 22 minutes
202,432,902,008,176,640,000≈ 77 years

The table shows what factorial growth means in practice. Twelve elements are sorted in half a second, fifteen elements take more than twenty minutes, and twenty elements take a human lifetime. The formula for the expected value was also checked by simulation. The trials were run with a fixed seed (new Random(42)) and from a shuffled, unsorted start. The average numbers of shuffles came out as follows: 23.9 for n = 4 (expected 24), 119.7 for n = 5 (expected 120), 714.5 for n = 6 (expected 720). 20,000 runs were made for each n.

Best case. If the array is already sorted, a single check is made and the algorithm finishes in O(n) time.

Worst case. Here there is no upper bound. The probability that all of k shuffles come out unsorted is (1 − 1/n!)ᵏ. This number approaches zero as k grows but is never zero for any k. So for every k a run lasting at least k rounds is possible. The expression O((n + 1)!) is a bound only for the expected time, not for the worst case. Unlucky shuffles can go on forever; the probability of this goes to zero.

Example 7.6

What is the probability that BogoSort on an array of four elements has still not finished after 24 shuffles, that is, after the expected value? All of the first 24 shuffles must come out unsorted: (23/24)²⁴ ≈ 0.36. More than a third of the runs exceed the expected value. The probability of not having finished after 100 shuffles is (23/24)¹⁰⁰ ≈ 0.014. The tail of the geometric distribution thins out exponentially, but it never breaks off.

Common mistake

Mistaking the expected-time bound for a worst-case bound. The sentence "BogoSort is O((n + 1)!)" is true only for the expected time. For Las Vegas algorithms the worst case is often unbounded. Which running time is being discussed should always be stated explicitly.

7.5Randomized QuickSort

7.5.1Pivot choice and its effect

Quicksort works briefly as follows. A pivot element is chosen from the array. The array is partitioned so that the elements smaller than or equal to the pivot stay on the left and the larger ones on the right, and the pivot settles between the two groups, in its final place. Then the two sides are sorted separately, recursively. Partitioning takes Θ(n) time. The total running time of the algorithm depends entirely on how evenly the pivot splits.

If the pivot splits the array into two equal halves every time, there are log₂ n levels and the time is Θ(n log n). If the pivot is every time the smallest or largest element of the subarray, one of the parts is empty and the other is just one element smaller. In this case there are n levels and the time rises to Θ(n²). The rule for choosing the pivot is therefore the most important design decision of the algorithm. Table 7.9 compares the common strategies.

Table 7.9: Pivot strategies. (*) For deterministic strategies, O(n log n) holds only if the input is in random order (average case).
Pivot strategyBad inputExpected / typicalWorst case
First or last elementsorted or reverse-sorted array (very common)O(n log n)*O(n²)
Median of threespecially crafted arraysO(n log n)*O(n²)
Random elementnone: badness comes only from bad luckO(n log n), for every inputO(n²)
True median (BFPRT)noneO(n log n)O(n log n)

Choosing the first or last element as pivot is the simplest rule, but it produces the worst case on an already sorted or reverse-sorted array. These inputs are very common in practice. The median-of-three rule chooses the median of the first, middle, and last elements as pivot. It works perfectly on a sorted array, but someone who knows the rule can craft special arrays that fool it. If the true median of the subarray is found and used as pivot, the split is always balanced. There is a deterministic algorithm that finds the median in linear time; it is known by the initials of its inventors, BFPRT (Blum, Floyd, Pratt, Rivest, Tarjan). But its constants are large and it is slow in practice.

The difference made by a random pivot is subtle but important. For deterministic strategies, O(n log n) rests on the assumption that the input is in random order. With a random pivot the expectation is over the algorithm's own choices; so it holds for every input. Still, the worst case does not disappear. If the algorithm picks an unlucky pivot every time, the time is again O(n²). What changes is that this case no longer depends on a particular input and that its probability is very small. In practice a random pivot or the median of three is preferred.

Common mistake

"A random pivot eliminates the worst case." This is false; the worst case is still O(n²). What a random pivot gives is that no input is consistently bad and that the probability of the bad case is very small.

7.5.2A run with random pivots

Let quicksort with a random pivot be run on the array [6, 5, 3, 1, 8, 7, 2, 4]. Suppose that in this run the pivots happen to be chosen as 3, 1, 4, 6, and 8, in that order. In the trace, partitioning is done with two pointers. i advances from the left and skips elements smaller than the pivot; it stops at the first element greater than or equal to it. j advances from the right and skips elements larger than the pivot; it stops at the first element smaller than or equal to it. If i < j, the two elements are swapped and the search continues. When the pointers meet, the pivot is in its final place. This method is based on Hoare's partitioning idea. The pivot itself may move during this process; its position is tracked.

Table 7.10: Quicksort with random pivots on the array [6, 5, 3, 1, 8, 7, 2, 4]. The pivots are 3, 1, 4, 6, 8.
subarraypivotpointers and swapsarray afterwardpivot position
a[0..7]3i = 0 (6), j = 6 (2): swap; i = 1 (5), j = 3 (1): swap; meet[2, 1, 3, 5, 8, 7, 6, 4]2
a[0..1]1i = 0 (2), j = 1 (1): swap; meet[1, 2, 3, 5, 8, 7, 6, 4]0
a[1..1]—single element, already sortedunchanged—
a[3..7]4i = 3 (5), j = 7 (4): swap; meet[1, 2, 3, 4, 8, 7, 6, 5]3
a[4..7]6i = 4 (8), j = 7 (5): swap; i = 5 (7), j = 6 (6): swap; meet[1, 2, 3, 4, 5, 6, 7, 8]5
a[4..4]—single elementunchanged—
a[6..7]8i skips 7 and stops at 8; j is already at 8; no swap[1, 2, 3, 4, 5, 6, 7, 8]7
a[6..6]—single elementarray sorted—

Let us trace the first partitioning in detail. The pivot is 3 and is at index 2. i stops immediately at a[0] = 6, because 6 is greater than the pivot. j starts from the right: 4 is greater than the pivot and is skipped; it stops at a[6] = 2. Since 0 < 6, 6 and 2 are swapped and the array becomes [2, 5, 3, 1, 8, 7, 6, 4]. The search continues: i skips 2 and stops at a[1] = 5; j skips 6, 7, and 8 and stops at a[3] = 1. 5 and 1 are swapped: [2, 1, 3, 5, 8, 7, 6, 4]. In the next step i skips 1 and stops at the pivot itself (index 2); j skips 5 and also arrives at index 2. The pointers have met. The pivot 3 is in its final place: only smaller elements (2, 1) are to its left and only larger ones to its right.

6051321384752647
2011325384756647
1021324354657687
Figure 7.7: Three moments of quicksort with a random pivot. Top, the start: the pivot 3 was chosen at random (black box); the dashed frame is the active subarray. Middle, the first partitioning is done: 3 is in its final place (index 2, green). Bottom, all elements are final.

In this run the pivots fell fairly evenly. The first pivot 3 split the eight elements into two parts of 2 and 5 elements. The depth of the recursion tree stayed at 4. If the smallest element had been chosen as pivot every time, the depth would have been 7. The final position of a pivot equals the number of elements in the array smaller than it; this is so whichever partitioning method is used. For example, there are five elements smaller than 6, so the position of 6 is index 5.

7.5.3Code and partitioning trace

The following code is the complete quicksort with a random pivot. For partitioning the Lomuto method is used: the randomly chosen pivot is first moved to the end of the subarray, and then in a single left-to-right pass the smaller elements are gathered on the left. It does the same job as the two-pointer method in the trace; the pivots go to the same final places, only the swaps in between differ.

static Random rng = new Random();

static void quickSort(int[] a, int lo, int hi) {
  if (lo < hi) {
    int p = partition(a, lo, hi); // random
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
  }
}

static int partition(int[] a, int lo, int hi) {
  int r = lo + rng.nextInt(hi - lo + 1);
  swap(a, r, hi);               // pivot to the end
  int pivot = a[hi], k = lo;
  for (int i = lo; i < hi; i++)
    if (a[i] <= pivot)
      swap(a, i, k++);          // small ones to the left
  swap(a, k, hi);               // pivot into place
  return k;
}

The method quickSort is the standard recursive skeleton. If the subarray has at least two elements, partition is called and the two sides of the returned pivot position are sorted separately. The randomness is only in the first line of partition: the expression lo + rng.nextInt(hi - lo + 1) gives a uniformly distributed index r between lo and hi (both included). This element is moved to the end by swapping it with a[hi] and becomes the pivot.

The loop invariant is this: at the start of each round, a[lo..k − 1] contains the elements less than or equal to the pivot and a[k..i − 1] contains the elements greater than the pivot. If a[i] is less than or equal to the pivot, it is swapped with a[k] and k increases by one; thus the "small" region grows by one element. When the loop ends, a[k] is the first element of the large region. The pivot is swapped with it to put it in its final place, and k is returned. partition makes hi − lo comparisons.

Example 7.7

Let partition(a, 0, 7) be called for a = [6, 5, 3, 1, 8, 7, 2, 4] and let rng.nextInt(8) return 2. The pivot is a[2] = 3. Table 7.11 gives each step of the partitioning.

Table 7.11: Lomuto partitioning, r = 2 (pivot 3).
stepia[i] ≤ 3?operationkarray
pivot to the end——a[2] ↔ a[7]0[6, 5, 4, 1, 8, 7, 2, 3]
106: no—0unchanged
215: no—0unchanged
324: no—0unchanged
431: yesa[3] ↔ a[0]1[1, 5, 4, 6, 8, 7, 2, 3]
548: no—1unchanged
657: no—1unchanged
762: yesa[6] ↔ a[1]2[1, 2, 4, 6, 8, 7, 5, 3]
pivot to its place——a[2] ↔ a[7]2[1, 2, 3, 6, 8, 7, 5, 4]

Seven comparisons were made and partition returned 2. The pivot 3 again settled at index 2; it had gone to the same place in the two-pointer trace. But the rest of the array differs: the two-pointer method had produced [2, 1, 3, 5, 8, 7, 6, 4], while Lomuto produces [1, 2, 3, 6, 8, 7, 5, 4]. The contract of partitioning fixes only the position of the pivot and the contents of the two sides; the order within the sides depends on the method. The code was run in Java and gave the same array. On 2000 random arrays the result of quickSort was compared with Arrays.sort and all matched.

7.5.4Best, worst, and expected case

Best: balanced splitnnnnlog₂ n levels × n work = O(n log n)Worst: always the smallest/largest pivotnn−1n−2…1n levels: n + (n−1) + … + 1 = O(n²)
Figure 7.8: Left, balanced splitting: each of the log₂ n levels does a total of n work, time O(n log n). Right, the smallest or largest pivot every time: n levels and n + (n − 1) + … + 1 = O(n²).
Table 7.12: Recurrences for the three cases of quicksort.
CaseRecurrenceTime
BestT(n) = 2T(n/2) + Θ(n)Θ(n log n)
Expected (random pivot)T(n) = (1/n) Σq [T(q) + T(n − 1 − q)] + Θ(n)Θ(n log n)
WorstT(n) = T(n − 1) + Θ(n)Θ(n²)

The expected-case recurrence reads as follows. The random pivot chooses each of the n elements of the subarray with probability 1/n. If the pivot is the q-th element in sorted order (counting from 0), the left part has q elements and the right part n − 1 − q. The recurrence averages over all values of q and adds the linear cost of partitioning. Its solution is Θ(n log n). Instead of solving this recurrence directly, it is easier to compute the number of comparisons with indicator variables.

First an intuitive observation can be made. If the pivot is one of the elements falling in the middle half in sorted order (that is, it is neither in the smallest quarter nor in the largest quarter), the larger of the two parts has at most 3n/4 elements. The probability of this "good pivot" event is 1/2. Every good pivot shrinks the part containing an element by at least a quarter. On the path of an element there can be at most log4/3 n good pivots, and good pivots come on average once in two tries. Each element takes part in O(log n) partitionings on average; the total work is O(n log n).

The probability of the worst case. For the worst case with a random pivot, the smallest or largest element of the subarray must be chosen in every partitioning. In a subarray of k elements the probability of this is 2/k. Since the choices are independent, the probabilities are multiplied:

P(worst case) = (2/n) · (2/(n − 1)) · … · (2/2) = 2ⁿ⁻¹ / n!

For n = 5 this value is 16/120 ≈ 0.133; for small arrays the worst case is not rare at all. In Python, with a fixed seed (random.Random(42)), an array of five elements was sorted 200,000 times. The fraction of runs in which the number of comparisons reached its maximum value, 10, came out as 0.134. For n = 10 the probability falls to 1.4 · 10⁻⁴, and for n = 20 to 2¹⁹ / 20! ≈ 2 · 10⁻¹³. For arrays of realistic size the worst case is practically never seen.

7.5.5Expected number of comparisons

The running time of quicksort is proportional to the number of comparisons it makes: each round of the partitioning loop makes exactly one comparison. Let this number be X. E[X] is computed with indicator variables and linearity.

Let the elements be named by their sorted order: z₁ < z₂ < … < zₙ. Here zᵢ is the i-th smallest element of the array; it has nothing to do with its position in the array. For each pair i < j define an indicator: Xᵢⱼ = 1 if zᵢ and zⱼ are compared during the algorithm, 0 if not. Two elements can be compared at most once, because comparisons are made only with the pivot, and after that partitioning the pivot never enters any subarray again. Therefore X = Σi<j Xᵢⱼ.

Theorem 7.3 (Probability of comparison)

In quicksort with a random pivot, zᵢ and zⱼ (i < j) are compared with probability exactly 2 / (j − i + 1).

Consider the set Zᵢⱼ = {zᵢ, zᵢ₊₁, …, zⱼ}; this set has j − i + 1 elements. As long as no element of this set is chosen as pivot, all the elements of the set stay in the same subarray, because every pivot chosen from outside is either smaller than all of them or larger than all of them. The moment the first pivot is chosen from the set is decisive. If this pivot is zᵢ or zⱼ, the other element is in the same subarray at that moment and is compared with the pivot. If the pivot is one of the elements in between, zᵢ falls to the left and zⱼ to the right; the two stay in separate parts and never meet. Since the pivot is chosen uniformly among the elements of the subarray, the first element chosen from the set is equally likely to be any element of the set. The probability of being one of the two wanted elements is 2 / (j − i + 1). □

z1z2z3z4z5z6z7z8first pivot{z₂, …, z₆}: 5 elementsPivot z₄ → z₂ goes left, z₆ right: they never meet.Only if z₂ or z₆ is the first pivot: P = 2/5.
Figure 7.9: If the first pivot from the set {z₂, …, z₆} is z₄, then z₂ falls to the left and z₆ to the right, and they are never compared. They are compared only if z₂ or z₆ is the first pivot: probability 2/5.

The two extreme cases of the theorem are interesting. Two elements adjacent in sorted order, that is, j = i + 1, are compared with probability 2/2 = 1, that is, always. This is natural: there is no other element between them, and no pivot can be found that separates them. The smallest and the largest element, on the other hand, meet only if the first pivot is one of the two: probability 2/n. Random arrays of eight elements were sorted 100,000 times in Python (seed 42). The fraction of runs in which the pair z₂–z₆ was compared was 0.399 (expected 0.4), for the pair z₁–z₈ 0.251 (expected 0.25), and for the adjacent pair z₃–z₄ exactly 1.

By linearity, the expected number of comparisons is the sum of the probabilities of the indicators:

E[X] = Σi<j 2 / (j − i + 1)

The sum is brought to closed form by grouping by the distance k = j − i + 1. The number of pairs with distance k is n − k + 1 (2 ≤ k ≤ n). Thus

E[X] = Σk=2..n (n − k + 1) · 2/k = 2(n + 1)(Hₙ − 1) − 2(n − 1) = 2(n + 1)Hₙ − 4n

is obtained. Here Hₙ = 1 + 1/2 + … + 1/n is the n-th harmonic number and is about ln n + 0.577. A crude upper bound is also easy to see: for each i the inner sum is less than 2(1/2 + 1/3 + …), hence E[X] < 2n Hₙ. Since 2n ln n = 2 ln 2 · n log₂ n, this bound is about 1.39 n log₂ n. Quicksort with a random pivot makes only about 39% more comparisons than the n log₂ n comparisons of perfectly balanced splitting. That the closed formula equals the sum itself for n ≤ 30 in exact rational arithmetic was checked with Python.

Table 7.13: The expected number of comparisons in quicksort with a random pivot (formula and simulation with new Random(42)) and the number of comparisons of the version that takes the first element as pivot on sorted input.
n2(n + 1)Hₙ − 4nsimulation averagesorted input, first element as pivot
1024.424.4 (20,000 sorts)45
100647.9648.0 (20,000)4,950
1,00010,985.911,003.6 (2,000)499,500
10,000155,771.7155,710.7 (200)49,995,000
10⁶≈ 2.48 · 10⁷—≈ 5.0 · 10¹¹

In the simulation a sorted array (1, 2, …, n) was sorted each time. This is the worst input for the deterministic first-element pivot; for a random pivot it is an ordinary input. The averages are very close to the formula; the small differences are random fluctuation from a limited number of repetitions. The last column is n(n − 1)/2: in a sorted array the first element is always the smallest, and at each level the part shrinks by just one. At n = 1000 the difference is about a factor of 45, and at n = 10⁶ about a factor of 20,000.

Common mistake

Confusing average case with expected time. The average case makes an assumption about the input distribution; if the assumption fails, the guarantee fails. The expected time, on the other hand, is computed for each fixed input over the algorithm's coin flips. The value 24.4 in Table 7.13 holds for every input of 10 elements, including a sorted array.

7.5.6Memory and repeated keys

Quicksort sorts the array in place; the extra memory is only the recursion stack. The stack depth is the height of the recursion tree. With a random pivot the expected depth is O(log n), but in the worst case it can reach n. A simple technique prevents this. Recurse first into the smaller part and process the larger part with a loop. Since the smaller part is at most half the size, the size at least halves with every recursive call. The stack depth stays O(log n) even in the worst case.

If the array has many equal keys, Lomuto partitioning behaves badly. In an array of all equal elements every element satisfies the condition "≤ pivot", the pivot always settles at the end, and one of the parts always stays empty. Even with a random pivot the time is Θ(n²). The solution is three-way partitioning: the array is divided into three regions, the elements smaller than the pivot, those equal to the pivot, and those larger than the pivot. The region of equal elements is in its final place and does not enter the recursion.

7.6Randomized selection (QuickSelect)

7.6.1The problem and the code

The selection problem is to find the k-th smallest element of an array. Questions such as the median, or the threshold of the ten smallest or largest elements, are examples of this problem. Sorting the array and reading position k takes O(n log n) time. But most of the sorting is unnecessary: only the place of a single element is asked for. The randomized selection (quickselect) algorithm uses the partitioning of quicksort, but each time descends only into the side where the sought element lies.

static int select(int[] a, int lo, int hi, int k) {
  if (lo == hi) return a[lo];
  int p = partition(a, lo, hi);
  if (k == p) return a[p];
  if (k < p) return select(a, lo, p - 1, k);
  return select(a, p + 1, hi, k);
}

k is a 0-based rank: k = 0 is the smallest element and k = n − 1 the largest. The method first checks the base case. If a single element is left in the range (lo = hi), it is the one sought. Otherwise the same randomized partition is called and the final position p of the pivot is learned. The final position of the pivot is its position in the sorted array. If k = p, the pivot is the one sought. If k < p, the sought element is to the left of the pivot; if k > p, it is to the right. Whichever side is descended into, k does not change, because the indices are relative to the whole array. The other side is never examined again.

This algorithm too is a Las Vegas algorithm. The result is always correct; what is random is only how many partitionings will be made. It also has a side effect: the method modifies the array in place. After it returns, a[k] is the sought element; those to its left are less than or equal to it and those to its right are greater.

7.6.2Code trace

Example 7.8

Let select(a, 0, 7, 5) be called on the array a = [6, 5, 3, 1, 8, 7, 2, 4]; the element sought is the 0-based 5th, that is, the 6th smallest. Let partition choose 3, 7, and 5 as pivots in turn. Table 7.14 gives the calls.

Table 7.14: Trace of select(a, 0, 7, 5).
callpivotarray after partitionpdecision
select(a, 0, 7, 5)3[1, 2, 3, 6, 8, 7, 5, 4]2k = 5 > 2: go right, [3, 7]
select(a, 3, 7, 5)7[1, 2, 3, 6, 4, 5, 7, 8]6k = 5 < 6: go left, [3, 5]
select(a, 3, 5, 5)5[1, 2, 3, 4, 5, 6, 7, 8]4k = 5 > 4: go right, [5, 5]
select(a, 5, 5, 5)—unchanged—lo = hi = 5: return a[5] = 6

In the first call the pivot 3 settles at index 2 by Lomuto partitioning. The position sought, 5, is to the right of the pivot; so only the range [3, 7] is descended into. The two elements on the left (1 and 2) are never examined again. In the second call the pivot is 7; since there are three elements smaller than 7 in the range 3..7 (6, 5, 4), 7 goes to index 6. The position sought is now to the left of the pivot. In the third call, in the three-element range [6, 4, 5], the pivot 5 is chosen and settles at index 4. In the last call a single element is left in the range: lo = hi = 5. The method returns a[5] = 6, and this value comes back unchanged along the chain of calls.

6051321384752647sactive range [0, 7]
1021324354657687s
Figure 7.10: Top, the first call: the active range is [0, 7] and the position sought, 5, is marked. Bottom, the result: the element at position 5 is 6. In this example the array ended up completely sorted; this is a coincidence, since the algorithm partitions only the parts it needs.

The code, run in Java with a scripted generator that made partition choose the same pivots, returned 6; the intermediate arrays also matched those in the table. In addition, on 2000 random arrays and random values of k, the result of select was compared with the k-th element of the sorted array; all were equal.

7.6.3Analysis

The expected running time of randomized selection is O(n). It differs from quicksort in that the recursion descends into one branch instead of two. A good pivot, that is, one that falls in the middle half, reduces the range to at most 3/4 of its size and occurs with probability 1/2. On average, once in two partitionings the range shrinks by at least a quarter. The range size falls from n to 3n/4, then to 9n/16. The expected cost of each stage is at most two partitionings, that is, twice the size at that stage. The total expected work is bounded by a geometric series:

E[T(n)] ≤ 2n (1 + 3/4 + (3/4)² + …) = 2n · 4 = 8n = O(n)

This is a crude bound. The exact value of the expected number of comparisons when looking for the median is about 2(1 + ln 2) n ≈ 3.39 n. The median was searched for 2000 times in Java (seed 42): for n = 1001 the average came out as 3.33 n comparisons and for n = 10,001 as 3.39 n. The difference at small n comes from lower-order terms in the formula.

The worst case is again O(n²). If the pivot falls at one end of the range every time, the range shrinks by only one at each step. Since partitioning already takes Θ(n), a time like O(log n) is impossible: every element must be read at least once. If linear time is wanted in the worst case as well, the pivot is chosen by the BFPRT method, that is, the "median of medians". In practice, however, the randomized version is faster.

Common mistake

Thinking the expected time of selection is O(n log n). Because it uses the same partitioning, one tends to expect the same time as quicksort. But selection continues with only one part at each level, and the work decreases geometrically: n + 3n/4 + 9n/16 + … The total is linear.

7.7Estimating π by Monte Carlo

7.7.1The method and the code

The Monte Carlo method estimates a number from the proportion of random samples. Its best-known example is the estimation of π. Consider the unit square with side 1 and a quarter circle of radius 1 centered at the lower-left corner of the square. The area of the square is 1 and the area of the quarter circle is π/4. If a uniformly random point is thrown into the square, the probability that it falls inside the quarter circle is the ratio of the areas: p = π/4 ≈ 0.785.

A point (x, y) is inside the quarter circle exactly when its distance from the origin is at most 1: x² + y² ≤ 1. There is no need to take a square root. n points are thrown and those falling inside are counted. The fraction of inside points estimates π/4; therefore

π ≈ 4 · inside / n

The method is a Monte Carlo algorithm with two-sided error. Its running time is exactly n steps, but its result can fall both below and above the true value.

static double estimatePi(int n) {
  int inside = 0;
  for (int t = 0; t < n; t++) {
    double x = rng.nextDouble(), y = rng.nextDouble();
    if (x * x + y * y <= 1) inside++;
  }
  return 4.0 * inside / n;
}

In each round rng.nextDouble() is called twice and produces two numbers uniformly distributed in [0, 1). If the point is in the quarter circle, inside increases by one. After the loop 4.0 * inside / n is returned. The 4.0 here is important: it moves the expression into double arithmetic. If 4 * inside / n were written, integer division would be performed and the fractional part dropped; for example, if 4 of 6 points are inside, the result would be 2 instead of 2.667. The method runs in O(n) time and O(1) extra memory.

Figure 7.11: 300 points thrown into the unit square. 239 of them are inside the quarter circle (green): π ≈ 4 · 239 / 300 ≈ 3.187.

7.7.2Code trace

Example 7.9

Let estimatePi(8) be called with rng = new Random(2024). Because the seed is fixed, the run produces the same points every time. Table 7.15 gives all eight points; the coordinates are rounded to four digits.

Table 7.15: estimatePi(8), seed 2024.
txyx² + y²resultinside
00.61850.18830.4179inside1
10.93100.09420.8756inside2
20.58210.49410.5830inside3
30.00080.49480.2448inside4
40.30280.70750.5921inside5
50.78370.71671.1279outside5
60.35060.97961.0825outside5
70.49630.36210.3774inside6

Six of the eight points landed inside. The method returns 4.0 · 6 / 8 = 3.0. The estimate is about 0.14 away from the true value. With so few points this is not surprising: the standard deviation of the estimate is about 1.64 / √8 ≈ 0.58. By this measure the estimate 3.0 is quite good. With the same seed the same code always gives 3.0; if the seed is changed, a different result comes out.

01point: 8inside: 6π ≈ 4 · 6 / 8= 3.0
Figure 7.12: When estimatePi(8) finishes: 8 points, 6 inside (green) and 2 outside (red). The estimate is 4 · 6 / 8 = 3.0.

7.7.3Error and the number of points

How reliable the estimate is can be found by a simple probability computation. Each point is an independent indicator that takes the value 1 with probability p = π/4 and 0 otherwise. The expected value of inside, the sum of n indicators, is np and its variance is np(1 − p). Since the estimate is 4 · inside / n, its expected value is exactly 4p = π; the method gives the correct value on average. Its standard deviation is

σ = 4 · √(p(1 − p) / n) = 1.642 / √n

The error decreases in inverse proportion to the square root of the number of points. The practical meaning of this is heavy: to reduce the error to a tenth, the number of points must grow a hundredfold. One more decimal digit of accuracy requires 100 times more work.

Table 7.16: Estimating π with different numbers of points. Each row was started from scratch with rng = new Random(42).
nestimate|estimate − π|σ = 1.642/√n
1003.160000.01840.164
1,0003.104000.03760.0519
10,0003.122400.01920.0164
100,0003.141280.000310.0052
1,000,0003.138630.002960.0016
10,000,0003.140660.000930.00052

The table shows that individual runs are noisy. The estimate with 100 points happened to come out very good; the estimate with 1,000,000 points is worse than that with 100,000. This is not a contradiction. σ gives not the error of a single run but the typical size of errors. To test this, the estimate with 1,000 points was repeated 2000 times (seed 42). The root mean square of the errors came out as 0.0514; the formula gives 0.0519. With the normal approximation, the error stays below 1.96 σ in about 95% of runs. For the error to be below 0.01 with 95% confidence, about 104,000 points are needed; to be below 0.001, about 10.4 million points.

Example 7.10

In an estimate made with 10,000 points the error is about 0.016. How many points are needed to bring the error down to about 0.0016? Since the error decreases as 1/√n, to reduce it to a tenth, √n must grow tenfold and n a hundredfold: 1,000,000 points. Raising the number of points to 100,000 reduces the error only by a factor of √10 ≈ 3.16.

Estimating π is not a good way to compute π; there are much faster deterministic formulas. But the method itself is very valuable. Complicated shapes whose area or volume cannot be computed by a formula, multidimensional integrals, particle simulations in physics, and risk calculations in finance are all done with the same idea. The error of the Monte Carlo method decreases as 1/√n regardless of the number of dimensions. In high-dimensional problems this property makes it superior to grid-based methods.

Common mistake

Integer division. In the expression 4 * inside / n all three operands are int, so the result is truncated to an integer. If four of six points are inside, the result is 2 instead of 2.667. Starting with 4.0 moves the division to double.

7.8The Miller–Rabin primality test

7.8.1The Fermat test and Carmichael numbers

The simplest way to tell whether a number is prime is to try dividing by all numbers up to √n. This method makes √n divisions. In terms of the number of digits of the number this is exponential time: for a number of 300 digits, 10¹⁵⁰ divisions are needed. Cryptography needs primes of exactly this size. A primality test checks the primality of a number without factoring it.

The idea comes from number theory. By Fermat's little theorem, if n is prime and 1 < a < n, then

aⁿ⁻¹ ≡ 1 (mod n)

holds. If this equality fails for some a, then n is certainly composite. This means that compositeness is proved without finding factors. If the equality holds, n is "maybe prime". The problem is this: some composite numbers satisfy the equality for every base coprime to themselves. These are called Carmichael numbers. The smallest is 561 = 3 · 11 · 17. For example 2⁵⁶⁰ mod 561 = 1. All bases coprime to 561, that is, all 320 numbers between 1 and 560, pass the Fermat test. The Fermat test can catch these numbers only by hitting a base that shares a factor. There are infinitely many Carmichael numbers.

7.8.2The square-root property and the Miller–Rabin sequence

The Miller–Rabin test adds a second check to the Fermat test. This check relies on the square roots of 1. If n is prime, the congruence x² ≡ 1 (mod n) has only two solutions: x ≡ 1 and x ≡ −1 ≡ n − 1. The reason is short. If the product x² − 1 = (x − 1)(x + 1) is divisible by n and n is prime, then n divides one of the factors. For composite numbers, however, 1 can have other square roots. In 561, for example, 67² = 4489 = 8 · 561 + 1; 67 is a "hidden" square root of 1.

The test is set up as follows. Let n be an odd number. n − 1 is even and is written as n − 1 = 2ˢ · d, where d is odd. For a random base a the following sequence is computed:

ad,   a2d,   a4d,   …,   a2s−1d   (mod n)

Each element is the square of the previous one. The next square after the sequence is a2sd = aⁿ⁻¹. If n is prime, by Fermat this last value is 1. Looking back along the sequence, the element before any square that reaches 1 is a square root of 1; in a prime modulus this element must be either 1 or n − 1. Consequently, if n is prime, the sequence either starts with 1 or takes the value n − 1 somewhere.

Definition 7.4

Let an odd number n and n − 1 = 2ˢ · d (d odd) be given. If ad mod n ≠ 1 and, for 0 ≤ r < s, no value a2rd is congruent to n − 1, then a is a witness to the compositeness of n. If n is composite but a is not a witness, a is called a strong liar for n.

ad²a2d²a4d²…²a2^(s−1)·dan−1→passes: the sequence starts with 1 or n − 1 appears somewherewitness: first element ≠ 1 and n − 1 never appears → n is certainly composite
Figure 7.13: The Miller–Rabin sequence: successive squares starting from ad. If the sequence starts with 1 or n − 1 appears somewhere, n passes the round. If the first element is not 1 and n − 1 never appears, a is a witness and n is certainly composite.

The power of the test comes from a number-theoretic result. Rabin showed that for an odd composite n, at most a quarter of the bases between 1 and n − 1 are strong liars. The proof of this theorem is not given here, but its consequence is easily tested on small numbers. For all odd composite numbers below 3000, the bases between 2 and n − 2 were tried one by one in Python. The highest liar fraction came out as 14/59 ≈ 0.237 for n = 1891 = 31 · 61; it is below 1/4. If the base is chosen at random, the probability that a composite number passes a round is at most 1/4. In k independent rounds the probability of error is at most 4⁻ᵏ.

7.8.3Code

static boolean isPrime(long n, int k) {
  if (n < 4) return n == 2 || n == 3;
  if (n % 2 == 0) return false;
  long d = n - 1; int s = 0;     // n-1 = 2^s·d
  while (d % 2 == 0) { d /= 2; s++; }
  for (int round = 0; round < k; round++) {
    long a = 2 + rng.nextLong(n - 3); // [2, n-2]
    long x = powMod(a, d, n);     // a^d mod n
    if (x == 1 || x == n - 1) continue;
    boolean witness = true;
    for (int r = 1; r < s && witness; r++) {
      x = x * x % n;
      if (x == n - 1) witness = false;
    }
    if (witness) return false;     // certainly composite
  }
  return true;                  // probably prime
}

The first two lines filter out small cases. If n < 4, only 2 and 3 are prime. Even numbers other than 2 are composite; 2 has already been caught in the first line. The next two lines bring n − 1 to the form 2ˢ · d: while d is even it is halved and s is counted. The main loop makes k rounds. In each round the expression 2 + rng.nextLong(n - 3) picks a uniform base from the range [2, n − 2]; nextLong(n - 3) gives a value between 0 and n − 4. (The bases 1 and n − 1 are useless because they pass the test for every number.)

x = powMod(a, d, n) is the first element of the sequence. If x is 1 or n − 1, this round is passed and continue goes to the next round. Otherwise witness is first set to true; the inner loop computes the remaining s − 1 elements of the sequence by successive squaring. If n − 1 appears, witness = false and the inner loop stops. If witness is still true when the inner loop ends, a is a witness and the method returns false. This answer is certain. If all rounds are passed, the method returns true: the number is "probably prime".

The code contains two details. First, the method rng.nextLong(long bound) was added in Java 17; it does not exist in older versions. Second, the product x * x % n is computed in the type long. Since x < n, the product is less than n². The largest value of long is about 9.22 · 10¹⁸; its square root is 3,037,000,499. The code is therefore safe only for n < 3 · 10⁹. For larger numbers BigInteger.modPow or directly BigInteger.isProbablePrime is used.

7.8.4Fast modular exponentiation

Computing ad mod n by multiplying a by itself d − 1 times is impossible for large d. The square-and-multiply method uses the binary representation of the exponent. The exponent is written in binary; at each step the base is squared to reach the next power of two. If that bit of the exponent is 1, that power is included in the result.

static long powMod(long a, long d, long n) {
  long result = 1;
  a %= n;
  while (d > 0) {
    if ((d & 1) == 1)          // if the bit is 1
      result = result * a % n;
    a = a * a % n;             // square
    d >>= 1;                   // next bit
  }
  return result;
}

The loop invariant is this: at the start of each round result · ad is equal to the value sought (mod n). If the bit is 1, a is multiplied into the result and that bit of d is consumed. Then a is squared and d is shifted right by one bit, that is, halved. When d = 0, the invariant says that result is the value sought. The loop runs as many times as d has bits, that is, ⌊log₂ d⌋ + 1 times. Each round makes at most two modular multiplications: the time is O(log d) multiplications.

Table 7.17: Trace of powMod(2, 35, 561). 35 = 100011₂ = 32 + 2 + 1.
rounddrightmost bitresulta (after squaring)note
start35—12a = 2¹
13511 · 2 = 242¹ included
21712 · 4 = 8162² included
3808256square only
440865,536 mod 561 = 460square only
5208211,600 mod 561 = 103square only
6118 · 103 = 824 mod 561 = 2635112³² included

The loop ends when d = 0 and returns 263: 2³⁵ mod 561 = 263. In the table the column a carries, in turn, the values 2¹, 2², 2⁴, 2⁸, 2¹⁶, 2³² (mod 561). In the rounds where the bit is 1, 2¹, 2², and 2³² are included in the result and 2¹ · 2² · 2³² = 2³⁵ is obtained. In total 6 squarings and 3 multiplications were made; plain multiplication would have needed 34 multiplications. The difference looks insignificant for small exponents. For an exponent of 300 digits, however, about 1000 squarings suffice, while the plain method needs about 10³⁰⁰ multiplications. The value a = 511 in the last round is computed but not used.

7.8.5Trace for the number 561

Example 7.11

Let isPrime(561, 1) be called and let the random base come out as a = 2. 561 is odd and greater than 4; the small-case checks are skipped. Table 7.18 gives the remaining steps.

Table 7.18: isPrime(561, 1), base a = 2.
stepoperationvalues
1d = n − 1, s = 0d = 560, s = 0
2–5while d is even, d /= 2, s++280/1, 140/2, 70/3, 35/4 → 560 = 2⁴ · 35
6round 0: the base is drawna = 2
7x = powMod(2, 35, 561)x = 263; neither 1 nor 560 → witness = true
8r = 1: x = 263² mod 56169,169 mod 561 = 166; not 560
9r = 2: x = 166² mod 56127,556 mod 561 = 67; not 560
10r = 3: x = 67² mod 5614,489 mod 561 = 1; not 560
11the inner loop ends (r = 4 = s)witness is still true → return false

The sequence is 263, 166, 67, 1 and never reaches 560. The method returns false: 561 is certainly composite. The last step of the sequence is especially instructive. 67² ≡ 1, but 67 is neither 1 nor 560. In a prime modulus there cannot be such a square root; so 67 is concrete evidence of compositeness. One square further along the sequence is 2⁵⁶⁰ ≡ 1. The Fermat test is fooled because it looks only at this last value. Miller–Rabin looks at how 1 was reached and is not fooled.

d = 35 = 100011₂13201608041211result = 263a = 511a becomes 2^1, 2^2, 2^4, 2^8 … (mod 561) in turn n − 1 = 560 = 24 · 35a = 2263a^d→166a^2d→67a^4d→1a^8d67² ≡ 1 but 67 ≠ ±1 → a = 2 is a witness: 561 is composite
Figure 7.14: Left, powMod(2, 35, 561) finished: 35 = 100011₂, result 263. Right, the Miller–Rabin sequence for 561: 263 → 166 → 67 → 1; 67² ≡ 1 but 67 is neither 1 nor −1; therefore 2 is a witness and 561 is composite.

7.8.6Examples and strong liars

Table 7.19: Miller–Rabin examples. Each row is a single round.
nn − 1aad, a2d, … (mod n)result
612² · 15211, 60passed (may be prime)
2212² · 5517447, 220passed (may be prime)
2212² · 55137188, 205composite (a is a witness)
5612⁴ · 352263, 166, 67, 1composite (a is a witness)
252³ · 3718, 24passed (may be prime)
252³ · 328, 14, 21composite (a is a witness)

61 is prime. 2¹⁵ = 32,768 = 537 · 61 + 11, so the sequence starts with 11. Its square is 121 = 61 + 60, that is, 60, which is n − 1. Since the sequence reaches n − 1, the round is passed. A prime number passes every round; Miller–Rabin never says "composite" for a prime.

221 = 13 · 17 is composite. For a = 174 the sequence starts with 47; 47² = 2209 = 9 · 221 + 220, that is, 220, which is n − 1. 174 is a strong liar: it makes the composite 221 look prime in this round. For a = 137 the sequence is 188 and 205; 220 does not appear and 137 becomes a witness. If isPrime(221, 2) is called with these two bases, the first round is passed and the second returns false. If one round were enough and only 174 were drawn, the answer would wrongly be "prime". This is why several rounds are needed. Of the 218 bases of 221 between 2 and 219, only four (21, 47, 174, 200) are strong liars. The error probability of a single round is 4/218 ≈ 0.018. In Python, 100,000 random bases were tried with a fixed seed; the fraction came out as 0.0185.

For 25 = 5², n − 1 = 24 = 2³ · 3. With a = 7, 7³ = 343 ≡ 18 and 18² = 324 ≡ 24 = n − 1; 7 is a strong liar for 25. Of the 22 bases of 25, only two (7 and 18) are liars. With a = 2 the sequence is 8, 14, 21; 24 never appears and the number is found composite.

These examples show that Rabin's bound is very pessimistic for most numbers. Of the 558 bases of 561, only 8 are strong liars, and of the 218 bases of 221, 4. Even the numbers that come closest to the bound do not exceed 1/4. So the true error probability is often even smaller than 4⁻ᵏ; 4⁻ᵏ is a guarantee for the worst case.

7.8.7Error, cost, and overflow

Miller–Rabin is a Monte Carlo algorithm with one-sided error. The answer "composite" is certain, because a witness has been found. The answer "prime" is only probably correct, and in k rounds the probability of error is at most 4⁻ᵏ. For a prime number the answer is always correct. The error can occur only in the form of calling a composite number "prime".

A round performs one modular exponentiation and at most s − 1 squarings. Together these are O(log n) modular multiplications. For numbers of b bits, one multiplication by the schoolbook method takes O(b²) bit operations. Since b = log n, one round is O(log³ n) and k rounds are O(k log³ n) bit operations. This is polynomial in the number of digits of the number. Compared with the exponential time of trial division, the gap is enormous.

The code was tested in Java. With a generator seeded new Random(42), isPrime(n, 20) was compared with BigInteger.isProbablePrime for every number between 2 and 200,000; no wrong answer appeared. In the same range with a single round (k = 1), 46 composite numbers were wrongly found "prime". The numbers 1,000,000,007, 2³¹ − 1 = 2,147,483,647, and 2,999,999,929 were found prime with 20 rounds; BigInteger gives the same result.

Common mistake

Overflow in modular multiplication. If x * x % n is written with int, the product exceeds 2³¹ − 1 when x reaches 46,341: 46,341² = 2,147,488,281. So for n > 46,341 the result silently becomes wrong. With long the limit is n < 3.037 · 10⁹. For larger numbers, a 128-bit product via Math.multiplyHigh or BigInteger.modPow is used.

Common mistake

Treating a Monte Carlo answer as certain. The answer "prime" from Miller–Rabin means "probably prime". The number of rounds k determines the error bound and is chosen according to the needs of the application. If a certain answer is needed, a deterministic test is used (for example AKS, or fixed sets of bases proven for specific ranges of numbers).

7.9Karger's minimum cut algorithm

7.9.1The minimum cut problem

Consider an undirected, connected graph. Let the vertices of the graph be split into two nonempty groups. The edges remaining between the two groups, that is, the edges with one endpoint in one group and the other endpoint in the other group, form a cut. If these edges are deleted, the graph falls into two pieces. The minimum cut problem is to find the cut with the fewest edges. This number is the smallest number of edges that must be deleted to disconnect the graph; it is a measure of network reliability. It is used in computer networks, circuit design, and segmenting images into regions.

Definition 7.5

Let G = (V, E) be an undirected multigraph. A partition of V into two nonempty, complementary subsets is called a cut (S, V − S). The size of the cut is the number of edges with one endpoint in S and the other in V − S. A cut of smallest size is called a minimum cut (global minimum cut).

This problem differs from the s–t cut in network flow. There two special vertices are given and only cuts separating them are sought. Here, in contrast, which vertices are separated is free. It is possible to solve it deterministically: fix one vertex and solve an s–t maximum flow problem with each of the other vertices. But this means n − 1 flow computations and code that is both long and complicated. The algorithm Karger gave in 1993, on the other hand, consists of a loop of a few lines.

7.9.2Edge contraction

The only operation of the algorithm is edge contraction. When an edge (u, v) is contracted, u and v merge into a single "supervertex". The edges between them now become self-loops from a vertex to itself and are deleted. Edges going from u or v to other vertices are attached to the supervertex. If several edges arise between the same two supervertices, all are kept; the graph becomes a multigraph. These parallel edges matter, because each is counted as a separate edge in the cut.

The algorithm is as follows: until two supervertices remain in the graph, a uniformly random edge is chosen among the remaining edges and contracted. The two supervertices that remain in the end give the partition of the vertices into two groups; the number of edges left between them is a cut. The algorithm always makes exactly n − 2 contractions. Its result is sometimes not minimum. That is why it is a Monte Carlo algorithm.

Example 7.12

Consider a graph with six vertices and eight edges. The edges are (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 5), (0, 2), and (1, 5). The minimum cut is 2. Vertices 3 and 4 are connected to the graph only by the edges (2, 3) and (4, 5); the set {3, 4} is separated by these two edges. {3} alone or {4} alone is also a cut with 2 edges. This graph has three minimum cuts. Let the algorithm choose the edges (0, 2), (1, 5), (3, 4), and (0, 1) in turn. Table 7.20 gives the contractions.

Table 7.20: A successful Karger run. The remaining edges are counted including parallel edges.
stepedge contractedsuperverticesself-loops deletededges remaining
0—{0} {1} {2} {3} {4} {5}—8
1(0, 2){0, 2} {1} {3} {4} {5}(0, 2)7
2(1, 5){0, 2} {1, 5} {3} {4}(1, 5)6
3(3, 4){0, 2} {1, 5} {3, 4}(3, 4)5
4(0, 1){0, 1, 2, 5} {3, 4}(0, 1), (1, 2), (0, 5)2

After the first contraction, two parallel edges arise between the supervertex {0, 2} and 1: the old (0, 1) and (1, 2). After the third contraction there are three parallel edges between {0, 2} and {1, 5}: (0, 1), (1, 2), and (0, 5). In the fourth step one of them, (0, 1), is chosen. All three become self-loops at once and are deleted. Two supervertices remain: {0, 1, 2, 5} and {3, 4}. Between them are the edges (2, 3) and (4, 5). The cut found is 2; this run is successful.

012345 ×20,21345
×30,21,53,4 ×20,1,2,53,4
Figure 7.15: A Karger run. Top left, the starting graph (6 vertices, 8 edges). Top right, (0, 2) has been contracted; two parallel edges (×2) between {0, 2} and 1. Bottom left, three supervertices and 5 edges after three contractions. Bottom right, two supervertices remain; 2 edges between them: the minimum cut was found. The dark vertex is the supervertex formed in the last contraction.

Another sequence of random choices gives another result. Let the algorithm choose the edges (1, 2), then (4, 5), (3, 4), and (0, 1). This time the supervertices are {0, 1, 2} and {3, 4, 5}. The edges (2, 3), (0, 5), and (1, 5) remain between them: the cut is 3 and is not minimum. The error arose from contracting (4, 5), an edge of a minimum cut. When an edge of a minimum cut is contracted, the two sides of that cut merge and this cut can no longer be found.

7.9.3Code

The code for this algorithm is not given in the slides. The following short version shows the whole algorithm on an edge list. The supervertices are tracked with a group array: each vertex is linked to a "representative" vertex, and the method find follows these links to find the representative. If two vertices have the same representative, they are in the same supervertex.

static int kargerCut(int n, int[][] edges) {
  int[] group = new int[n];             // group[v]: vertex v links to
  for (int v = 0; v < n; v++) group[v] = v;
  int remaining = n;                   // number of supervertices
  while (remaining > 2) {
    int[] e = edges[rng.nextInt(edges.length)];
    int g1 = find(group, e[0]), g2 = find(group, e[1]);
    if (g1 == g2) continue;            // self-loop: draw again
    group[g1] = g2;                    // contract the edge
    remaining--;
  }
  int cut = 0;
  for (int[] e : edges)
    if (find(group, e[0]) != find(group, e[1])) cut++;
  return cut;
}
static int find(int[] group, int v) {
  while (group[v] != v) v = group[v];
  return v;
}

The loop draws a uniformly random edge from the edge list. If both endpoints of the edge are already in the same supervertex, this edge is a self-loop; it is skipped and drawn again. Otherwise the two groups are merged and the number of supervertices decreases by one. This "redraw" method gives the correct distribution. Every edge that is not a self-loop is chosen with equal probability, and parallel edges between two supervertices are counted separately. This is the same as the choice in the definition of the algorithm. When two supervertices remain, the edge list is scanned once and the edges whose endpoints lie in different groups are counted.

static int kargerRepeat(int n, int[][] edges, int T) {
  int best = Integer.MAX_VALUE;
  for (int t = 0; t < T; t++)
    best = Math.min(best, kargerCut(n, edges));
  return best;
}

kargerRepeat runs the algorithm T times independently and returns the smallest cut found. Karger's error is one-sided: the cut found can never be smaller than the minimum. So taking the smallest result is correct. The code is written to be readable, not fast. In a simple implementation a single run takes O(n²) time.

The code was tested in Java on the example graph. With a scripted generator, the order (0, 2), (1, 5), (3, 4), (0, 1) returned 2; the order (1, 2), (4, 5), (3, 4), (0, 1) returned 3. Then 200,000 independent runs were made with rng = new Random(42). 91,392 runs found a cut of 2 edges, 88,725 runs a cut of 3, and 19,883 runs a cut of 4. The success rate is 0.457.

7.9.4Success probability

Theorem 7.4 (Karger)

In a connected multigraph with n vertices, a single run of Karger's algorithm finds a particular minimum cut with probability at least 2 / (n(n − 1)).

Let a particular minimum cut be C and let it have c edges. If the algorithm contracts no edge of C, it finds exactly C in the end. Every vertex has degree at least c; otherwise the cut separating that vertex alone would be smaller than c. Contractions preserve cuts, so in the remaining graph too every supervertex has degree at least c. When k supervertices remain, the sum of the degrees is at least kc and the number of edges at least kc/2. At that moment the probability that an edge of C is chosen is at most c / (kc/2) = 2/k. The probability that C is left untouched is the product over the steps:

(1 − 2/n)(1 − 2/(n − 1)) … (1 − 2/3) = (n − 2)/n · (n − 3)/(n − 1) · … · 1/3 = 2 / (n(n − 1))

In the product most numerators and denominators cancel; only n(n − 1) remains in the denominator and only 2 · 1 in the numerator. □

For n = 6 the lower bound is 2/30 = 1/15 ≈ 0.067. On the example graph the true success probability is much higher than this. All contraction sequences were computed one by one in Python with rational arithmetic: the probability of finding any minimum cut is exactly 16/35 ≈ 0.457. This agrees with the 0.457 in the simulation. There are two reasons for the difference. First, the graph has three minimum cuts and finding any one counts as success. Second, the bound "every vertex has degree at least c" in the proof is loose on this graph: the degrees are between 2 and 3.

The theorem has an interesting corollary. The events of finding different minimum cuts are mutually exclusive and each has probability at least 2/(n(n − 1)). Since the probabilities cannot sum to more than 1, a graph can have at most n(n − 1)/2 distinct minimum cuts. This bound is tight: in a cycle graph with n vertices, every choice of two edges gives a minimum cut, and there are exactly n(n − 1)/2 minimum cuts. In the six-vertex cycle, Karger finds a minimum cut in every run, but finds a particular cut with probability only 1/15.

Example 7.13

What is the lower bound for a graph with five vertices? The product in the proof is (1 − 2/5)(1 − 2/4)(1 − 2/3) = 3/5 · 2/4 · 1/3 = 1/10; the formula also gives 2/(5 · 4) = 1/10. The true success may be higher depending on the graph.

7.9.5Amplification by repetition

The success probability of a single run, p ≥ 2/(n(n − 1)), is small. If the algorithm is run T times independently and the smallest result is taken, the probability that all runs fail is at most (1 − p)ᵀ. Using the inequality 1 − x ≤ e⁻ˣ, we get

(1 − 2/(n(n − 1)))ᵀ ≤ e−2T/(n(n − 1))

is obtained. If T = n(n − 1)/2 · ln n is chosen, the right-hand side becomes e−ln n = 1/n. The total time is O(n² log n) runs × O(n²) = O(n⁴ log n). This is the running time of a simple implementation. The recursive version developed by Karger and Stein exploits the observation that the first steps of contraction are safe and the last steps are risky, and reduces the time to O(n² log³ n).

Example 7.14

On a graph with six vertices the success probability is at least 1/15. How many repetitions suffice to push the failure probability below 1/6? With the exponential bound, the condition (14/15)ᵀ ≤ e−T/15 ≤ 1/6 gives T ≥ 15 ln 6 ≈ 26.9; 27 repetitions suffice. Computed directly without the bound, (14/15)²⁶ ≈ 0.1663 is already below 1/6 ≈ 0.1667; 26 repetitions also suffice, 25 do not. The exponential bound makes the computation easier, at the price of one extra repetition.

These bounds are for the worst graphs. Since the true success on the example graph is 16/35, the probability that all of 27 repetitions fail is (19/35)²⁷ ≈ 6.9 · 10⁻⁸. In Java, kargerRepeat(6, G, 27) was called 20,000 times (seed 42) and returned 2 every time. With only 3 repetitions the success rate came out as 0.836; the exact value is 1 − (19/35)³ ≈ 0.840.

Common mistake

Not choosing the edge uniformly. If a random vertex is chosen first and then a random neighbor of it, the edges are not equally likely. Edges of vertices with small degree are chosen more often. These vertices, in turn, often carry exactly the edges of the minimum cut. The proof assumes each edge is chosen with equal probability; parallel edges must also be counted separately.

7.10Other applications

Randomness is used in many areas of algorithm design. The following examples are a few of them.

Graph coloring. Different colorings are tried with random decisions. The goal is to find good colorings with few colors without giving adjacent vertices the same color. Local improvements made from a random start help escape the bad solutions in which a deterministic order gets stuck.

Randomized depth-first search. Neighbors are visited in a random order. Results such as connectivity and spanning trees do not change, but the tree obtained is different every time. Maze generation is based on this idea: a random spanning tree of a grid is a maze with a single path from every cell to every other cell.

Matching. Randomized incremental algorithms take the edges in a random order and produce solutions approaching the maximum matching. The random order prevents a bad input order from fooling the algorithm.

Approximate counting. Data structures such as the Count-Min Sketch work with randomly chosen hash functions. In a very large data stream they estimate how many times each element occurs, with little memory and a controlled error.

Matrix operations. Randomized matrix methods quickly produce low-rank approximations of a large matrix. Dimensionality reduction and data compression use these approximations.

Computational geometry. There are randomized incremental algorithms for the convex hull, the closest pair of points, and Delaunay triangulation. The points are added in a random order and the expected time is O(n log n).

Metaheuristics such as randomized scheduling (job assignment), simulated annealing, and genetic algorithms also exploit randomness in search. These methods find good solutions in large search spaces, but they do not guarantee reaching the optimum. In this respect they differ from Las Vegas and Monte Carlo algorithms: for those, the correctness or the error probability is given by a proven bound.

7.11Pseudorandom numbers

Throughout these notes we kept saying "a random number is chosen". But a computer is a deterministic machine; it does not produce true randomness. Programs use pseudorandom numbers instead. These are numbers produced by a deterministic formula that nevertheless behave like random numbers in statistical tests. The starting value of the formula is called the seed.

The oldest and simplest method is the linear congruential generator (LCG):

Xₖ₊₁ = (a · Xₖ + c) mod m

Example 7.15

Let a = 5, c = 3, m = 16, and seed X₀ = 7. The sequence runs 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4 and returns to 7 after 16 steps. For example, 5 · 7 + 3 = 38 and 38 mod 16 = 6. This generator produces every value in 0..15 once; the sequence looks irregular at first sight. But looking at the last bits the weakness is seen at once: the numbers come alternately odd, even, odd, even. The low bits of LCGs have a short period.

java.util.Random is an LCG. Its parameters are a = 25,214,903,917, c = 11, and m = 2⁴⁸. Because of the weakness seen in the example, the class uses only the upper bits of its 48-bit state as output. Such a generator is sufficient for algorithm experiments and simulations. But from a few consecutive outputs its internal state can be computed and all later numbers predicted.

The same seed always gives the same sequence. This is not a weakness but a valuable property. A program started with new Random(42) makes the same "random" decisions on every run. In this way a bug can be reproduced when debugging, experiments can be repeated, and tests give the same result every time. All the simulations in these notes were also made with fixed seeds. The eight points in the π trace are obtained again every time with new Random(2024).

Different generators are used depending on the purpose. In cryptography, that is, when generating keys, passwords, or session tokens, unpredictability is essential; for this java.security.SecureRandom is used. In multithreaded programs, sharing a single Random object makes the threads wait for each other; ThreadLocalRandom.current() gives each thread its own generator.

Table 7.21: Commonly used random ranges (rng is a Random object).
expressionrange of values
rng.nextInt(n)0 … n − 1
lo + rng.nextInt(hi - lo + 1)lo … hi
rng.nextDouble()[0, 1)
rng.nextInt(6) + 1a die roll: 1 … 6

The second row of the table is the pattern used in choosing a random pivot. The range has hi − lo + 1 values; this number is given to nextInt and the result is shifted by lo. If the + 1 is forgotten, hi is never chosen. This is the same bug as nextInt(i) in Fisher–Yates.

Common mistake

new Random() on every call. Creating a new generator wherever a random number is needed produces unnecessary objects. Worse, the seeds of generators created one after another can be close to each other and correlated. A single Random object is shared throughout the program; this is why static Random rng in the code of these notes is at class level.

7.12Common mistakes

Mistakes in randomized algorithms often give no compile error and do not show in a single run. The program runs and produces plausible-looking results, but the probability distribution or the analysis is wrong. The following list collects the mistakes met throughout the notes.

Common mistake

The naive shuffle. Swapping with nextInt(n) for every i is biased: nⁿ equally likely paths cannot be distributed evenly over n! permutations. The correct form is nextInt(i + 1). nextInt(i) gives Sattolo's algorithm and produces only single-cycle permutations.

Common mistake

"A random pivot eliminates the worst case." The worst case is still O(n²). What changes is that no input is consistently bad and that the probability of the bad case is very small: about 2 · 10⁻¹³ at n = 20.

Common mistake

Confusing average case with expected time. The average case assumes a distribution of inputs. The expected time is computed for each fixed input over the algorithm's coin flips and holds for the worst input too.

Common mistake

Treating a Monte Carlo answer as certain. In Miller–Rabin the answer "prime" is only probably correct; the number of rounds k sets the error bound at 4⁻ᵏ. A single run of Karger's algorithm often gives a cut that is not minimum; the smallest of many runs is taken.

Common mistake

Overflow. x * x % n with int can overflow for n > 46,341; with long the limit is about 3 · 10⁹. For larger moduli Math.multiplyHigh or BigInteger.modPow is used.

Common mistake

A new generator on every call, and a non-uniform choice. Creating new Random() on every call is wasteful and the seeds may be correlated; a single Random is shared. In Karger's algorithm the edge is chosen directly and uniformly; choosing a vertex first and then a neighbor is not uniform.

Common mistake

Off by one at the range boundary. If lo + rng.nextInt(hi - lo) is written, hi is never chosen. For a random pivot this means the last element can never be the pivot; the assumption "every element with probability 1/n" in the analysis breaks.

7.13Summary

  • A randomized algorithm uses random bits in addition to its input. The running time and sometimes the output is a random variable. The expected time is taken, for every input, over the algorithm's own choices.
  • The basic tools of the analysis are linearity of expectation, indicator variables, the geometric distribution (1/p trials), independent repetition (qᵏ), and Markov's inequality.
  • A Las Vegas algorithm is always correct and its running time is random. A Monte Carlo algorithm has bounded running time and its answer is wrong with a small probability. A Monte Carlo algorithm with a verifiable answer is turned into Las Vegas by repetition; Las Vegas is turned into Monte Carlo by Markov's inequality.
Table 7.22: Summary of the algorithms studied in these notes.
TopicWhat to remember
Fisher–Yatesj = nextInt(i + 1), Θ(n), each of the n! outcomes has probability 1/n!; the naive shuffle is biased
BogoSortp = 1/n!, expected n! shuffles and Θ(n · n!) time; best case O(n), worst case unbounded
Randomized QuickSortP(zᵢ, zⱼ compared) = 2/(j − i + 1); expected 2(n + 1)Hₙ − 4n ≈ 1.39 n log₂ n comparisons, for every input; worst case O(n²)
QuickSelectdescends into one side; expected O(n) (≈ 3.39 n for the median), worst case O(n²)
π estimation4 · inside / n; standard deviation 1.642/√n; 100 times the points for one more digit
Miller–Rabinn − 1 = 2ˢd; the sequence must start with 1 or contain n − 1; error ≤ 4⁻ᵏ; "composite" is certain; O(k log³ n)
Kargerrandom edge contraction; success ≥ 2/(n(n − 1)); with n(n − 1)/2 · ln n repetitions failure ≤ 1/n
  • The error probability of an algorithm is reduced exponentially fast by independent repetition. With one-sided error a single certain answer suffices; in Karger's algorithm the smallest result is taken.
  • The numbers a computer produces are pseudorandom. A fixed seed makes experiments reproducible; cryptography needs SecureRandom.

7.14Key terms

  • randomized algorithm
  • expected value
  • expected running time
  • average case
  • indicator random variable
  • geometric distribution
  • Markov's inequality
  • Las Vegas algorithm
  • Monte Carlo algorithm
  • amplification
  • Fisher–Yates shuffle
  • pivot
  • partition
  • quickselect
  • primality test
  • witness, strong liar
  • Carmichael number
  • minimum cut
  • edge contraction
  • pseudorandom number
  • seed

7.15Test Yourself

  1. The Fisher–Yates shuffle is applied to the array [1, 2, 3, 4, 5, 6]. For i = 5, 4, 3, 2, 1 the drawn values of j are 2, 4, 0, 1, 0 in turn. What is the array after each step?

    Answer

    i = 5, j = 2: [1, 2, 6, 4, 5, 3]. i = 4, j = 4: unchanged. i = 3, j = 0: [4, 2, 6, 1, 5, 3]. i = 2, j = 1: [4, 6, 2, 1, 5, 3]. i = 1, j = 0: [6, 4, 2, 1, 5, 3]. Five swaps were made; one of them left the element in place.

  2. If the naive shuffle is applied to an array of five elements, how many equally likely paths are there? How can one tell that the result cannot be uniform? How many paths does Fisher–Yates have?

    Answer

    There are 5⁵ = 3125 paths and 5! = 120 permutations. 3125 / 120 ≈ 26.04 is not an integer; 3125 is odd and 120 is even. The permutations cannot be produced by equal numbers of paths. Fisher–Yates has 5 · 4 · 3 · 2 = 120 paths and each permutation is obtained exactly once.

  3. What is the expected number of shuffles of BogoSort on an array of eight distinct elements? What is the approximate probability that the algorithm has still not finished after this many shuffles?

    Answer

    8! = 40,320 shuffles. The probability of not having finished is (1 − 1/40,320)⁴⁰³²⁰ ≈ e⁻¹ ≈ 0.368. In the geometric distribution the probability of not being done by the expected value is, for large n, about 1/e.

  4. For a = [9, 4, 7, 1, 6, 3, 8], partition(a, 0, 6) is called and rng.nextInt(7) returns 4. What are the array after partitioning, the return value, and the number of comparisons?

    Answer

    The pivot is a[4] = 6 and is moved to the end: [9, 4, 7, 1, 8, 3, 6]. 4, 1, and 3 are moved to the left in turn: [4, 9, 7, 1, 8, 3, 6], [4, 1, 7, 9, 8, 3, 6], [4, 1, 3, 9, 8, 7, 6]. The pivot settles at k = 3: [4, 1, 3, 6, 8, 7, 9]. The return value is 3 and the number of comparisons is hi − lo = 6.

  5. In quicksort with a random pivot, with what probability are z₃ and z₇ compared in an array of 10 elements? What is the expected number of comparisons for an array of five elements?

    Answer

    The set {z₃, …, z₇} has 5 elements; the first pivot must be z₃ or z₇: 2/5. The probability does not depend on the size of the array. For five elements, H₅ = 137/60 and E[X] = 2 · 6 · 137/60 − 20 = 7.4. The worst case is 5 · 4/2 = 10 comparisons.

  6. With the Monte Carlo method, 7,860 of 10,000 points fell inside the quarter circle. What is the estimate of π? What is the approximate standard deviation of the estimate at this number of points?

    Answer

    4 · 7,860 / 10,000 = 3.144. The standard deviation is 1.642 / √10,000 ≈ 0.016. The true error is |3.144 − π| ≈ 0.0024; it is smaller than the typical error.

  7. What does the Fermat test say for n = 91 and a = 3? What does Miller–Rabin say with the same base?

    Answer

    Since 3⁹⁰ ≡ 1 (mod 91), the Fermat test is passed; 3 is a Fermat liar for 91. In Miller–Rabin, 90 = 2¹ · 45, that is, s = 1 and d = 45. 3⁴⁵ ≡ 27 (mod 91); 27 is neither 1 nor 90, and since s = 1 no further squaring is done. 3 is a witness: 91 = 7 · 13 is certainly composite.

  8. In the call powMod(3, 13, 17), what are result and a after each round? What is the return value?

    Answer

    13 = 1101₂. Bit 1: result = 3, a = 9. Bit 0: result = 3, a = 81 mod 17 = 13. Bit 1: result = 39 mod 17 = 5, a = 169 mod 17 = 16. Bit 1: result = 80 mod 17 = 12, a = 256 mod 17 = 1. The return value is 12: 3¹³ mod 17 = 12.

  9. What is the lower bound on the success probability of a single run of Karger's algorithm on a graph with eight vertices? How many repetitions suffice, with the exponential bound, to bring the failure probability below 1/8? How many repetitions does the exact computation give?

    Answer

    The lower bound is 2/(8 · 7) = 1/28. For e−T/28 ≤ 1/8, T ≥ 28 ln 8 ≈ 58.2, that is, 59 repetitions. Solving (27/28)ᵀ ≤ 1/8 directly gives T ≥ ln 8 / ln(28/27) ≈ 57.2, so 58 repetitions suffice.

  10. A Las Vegas algorithm with expected running time 100 ms is stopped after 300 ms. What can be said about the probability of no answer? If the algorithm is restarted independently at most five times with this rule, what is the largest probability that no answer is obtained at all?

    Answer

    By Markov's inequality, P(T ≥ 300) ≤ 100/300 = 1/3. The probability that all five independent trials give no answer is at most (1/3)⁵ ≈ 0.0041. The total time is at most 1.5 seconds; this new algorithm is a Monte Carlo algorithm.

7.16Further reading

  • R. Motwani and P. Raghavan, Randomized Algorithms (1995): the classic reference on randomized algorithms; covers the Las Vegas and Monte Carlo types, Karger's algorithm, and primality tests with proofs.
  • M. Mitzenmacher and E. Upfal, Probability and Computing (2nd ed., 2017): teaches probability tools such as indicator variables and the Markov and Chernoff bounds through algorithm examples.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 5, 7, and 9: probabilistic analysis, a detailed analysis of quicksort with a random pivot, and selection in expected linear time.
  • D. E. Knuth, The Art of Computer Programming, Volume 2 (3rd ed., 1997): examines pseudorandom number generators, the theory of linear congruential generators, and the shuffling algorithm in detail.

7.17References

  1. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
  2. M. Mitzenmacher, E. Upfal, Probability and Computing, 2nd ed., Cambridge University Press, 2017.
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapters 5, 7, 9, 31).
  4. C. A. R. Hoare, “Quicksort”, The Computer Journal 5(1), 1962.
  5. M. O. Rabin, “Probabilistic Algorithm for Testing Primality”, Journal of Number Theory 12(1), 1980.
  6. D. R. Karger, “Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm”, SODA, 1993.
  7. D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997 (Section 3.4.2: shuffling).

Related pages: Chapter 7 slides · © Sercan Külcü. All rights reserved.