Difficulty: Intermediate | Prerequisites: Basic probability (expectation, indicator random variables), Markov's inequality, permutations
Randomized algorithms use random choices during execution, and their performance is measured in expectation or with probabilistic guarantees rather than worst-case deterministic bounds. This review covers two problems from the EECS 376 final review: analysing Bogosort's expected running time (a classic exercise in geometric random variables) and the Colorful-Triangle problem (which brings together indicator random variables, linearity of expectation, approximation ratios, and Markov's inequality). You should be comfortable computing expected values and using linearity of expectation before working through this material.
Bogosort randomly permutes an array and checks if it is sorted, repeating until it succeeds. Its expected time is O(n · n!). For Colorful-Triangle, randomly colouring vertices with 4 colours makes each triangle colourful with probability 3/8, giving a 3/8-approximation in expectation. Markov's inequality then bounds the probability that fewer than a quarter of triangles are colourful.
Bogosort (permutation sort, stupid sort)
A randomized sorting algorithm that repeatedly generates a uniformly random permutation of the input and checks whether the result is sorted. Think of it as shuffling a deck of cards and checking if they landed in order, over and over.
Expected time complexity
The average running time of a randomized algorithm, weighted by the probability of each random outcome. In simple terms, it is how long the algorithm takes "on average" over all its coin flips.
Geometric random variable
The number of independent trials needed to get the first success, where each trial succeeds with probability p. The expected value is 1/p. Think of it as counting how many times you roll a die before you get a six.
Indicator random variable
A random variable that takes the value 1 if an event occurs and 0 otherwise. Useful because E[X] = Pr[X = 1], and linearity of expectation lets you sum them easily.
Linearity of expectation
For any random variables X₁, ..., Xₙ (even dependent ones), E[X₁ + ... + Xₙ] = E[X₁] + ... + E[Xₙ]. This is the workhorse of randomized algorithm analysis.
Colourful triangle
A triangle in a graph whose three vertices are all assigned pairwise distinct colours. In the Colorful-Triangle problem you want to maximise the count of such triangles.
Approximation ratio
For a maximisation problem, the ratio E[algorithm's output] / OPT, where OPT is the value of an optimal solution. A ratio of α means the algorithm achieves at least an α fraction of the best possible value, in expectation.
Markov's inequality
For a non-negative random variable X and any a > 0: Pr[X ≥ a] ≤ E[X] / a. A simple but broadly useful tail bound.
Bogosort works on an array of n distinct integers. Each iteration: generate a uniformly random permutation (O(n) time), then check if it is sorted (O(n) time). Repeat until sorted.
There are n! possible permutations, and exactly 1 is sorted. So the probability of success on any single trial is 1/n!.
The number of trials until the first success follows a geometric distribution with parameter p = 1/n!. The expected number of trials is therefore 1/p = n!.
Each trial costs O(n) time (permutation + check). So the expected total time is:
E[time] = E[number of trials] × O(n) = n! × O(n) = O(n · n!)
Each trial is independent (the permutation is chosen uniformly at random, with no memory of previous attempts). The probability of success is the same in every trial. These are exactly the conditions for a geometric random variable.
The problem: given a graph G = (V, E), assign one of 4 colours to each vertex to maximise the number of colourful triangles (triangles whose three vertices all have distinct colours). The algorithm simply assigns each vertex a uniformly random colour from {1, 2, 3, 4}, independently.
Let T = {u, v, w} be any triangle. We need all three vertices to have pairwise distinct colours.
Fix u's colour: it can be anything (probability 1).
v must differ from u: probability 3/4.
w must differ from both u and v: probability 2/4 = 1/2.
So Pr[X_T = 1] = 1 × (3/4) × (1/2) = 3/8.
Let t be the total number of triangles in G, and let OPT be the maximum number of colourful triangles under any colouring (OPT ≤ t).
By linearity of expectation, the expected number of colourful triangles is:
E[colourful triangles] = sum over all triangles T of Pr[X_T = 1] = t × (3/8) = (3/8) · t.
Since OPT ≤ t, we have:
E[colourful triangles] / OPT ≥ (3/8) · t / t = 3/8.
The algorithm achieves a 3/8-approximation ratio in expectation.
Let Y be the fraction of triangles that are colourful. From part (b), E[Y] = 3/8.
We want a lower bound on Pr[Y ≥ 1/4]. Use the complement: Pr[Y ≥ 1/4] = 1 - Pr[Y < 1/4].
To bound Pr[Y < 1/4], consider the random variable (1 - Y), which is non-negative and has E[1 - Y] = 1 - 3/8 = 5/8.
Pr[Y < 1/4] = Pr[1 - Y > 3/4].
By Markov's inequality: Pr[1 - Y > 3/4] ≤ E[1 - Y] / (3/4) = (5/8) / (3/4) = 5/6.
Therefore: Pr[Y ≥ 1/4] ≥ 1 - 5/6 = 1/6.
So with probability at least 1/6, at least a quarter of all triangles are colourful.
Students sometimes multiply probabilities assuming independence when the events are not independent. In the Colorful-Triangle problem, different triangles sharing vertices are dependent. Linearity of expectation still works, though, because it does not require independence.
For Bogosort, students occasionally compute the expected number of trials (n!) but forget to multiply by the cost per trial (O(n)), giving O(n!) instead of the correct O(n · n!).
When applying Markov's inequality to get a lower bound on Pr[Y ≥ c], students sometimes apply Markov directly to Y, which gives an upper bound. To get a lower bound, you need to work with the complement (1 - Y) or use the identity Pr[Y ≥ c] = 1 - Pr[Y < c] and bound the latter from above.
The approximation ratio for a maximisation problem is at most 1. If your calculation gives a number greater than 1, something has gone wrong.
⚠️ Linearity of expectation is used in nearly every randomized-algorithm question on the exam. Know it cold and know that it works even for dependent random variables.
⚠️ The "indicator variable + linearity" pattern (define an indicator for each small event, sum them, take expectation) is the standard approach. Expect to use it.
⚠️ The complement trick for turning Markov's inequality into a lower bound (instead of an upper bound) is a common exam technique.
⚠️ Approximation ratios may appear alongside randomized algorithms. Understand what the ratio means for maximisation vs. minimisation problems.
True or false: The expected number of trials in Bogosort is n!. (True.)
Fill in the blank: Each Bogosort trial costs O(______) time. (n.)
True or false: Linearity of expectation requires the random variables to be independent. (False.)
Fill in the blank: For the Colorful-Triangle problem with 4 colours, the probability a single triangle is colourful is ______. (3/8.)
True or false: Markov's inequality can be applied to any random variable, including those that take negative values. (False, the variable must be non-negative.)
Q: Derive the expected time complexity of Bogosort on an array of n distinct integers.
A: The probability of generating the sorted permutation on any trial is 1/n!. The number of trials is geometric with expectation n!. Each trial costs O(n). So E[time] = n! × O(n) = O(n · n!).
Q: In the Colorful-Triangle problem with 4 colours, compute Pr[X_T = 1] for a triangle T.
A: Pr[X_T = 1] = 1 × (3/4) × (2/4) = 3/8. The first vertex can be any colour; the second must differ (3 out of 4 choices); the third must differ from both (2 out of 4 choices).
Q: What approximation ratio does the random 4-colouring achieve for Colorful-Triangle?
A: 3/8. By linearity of expectation, the expected number of colourful triangles is (3/8) · t, and since OPT ≤ t, the ratio is at least 3/8.
Q: Using Markov's inequality, give a lower bound on Pr[Y ≥ 1/4] where Y is the fraction of colourful triangles.
A: Pr[Y ≥ 1/4] = 1 - Pr[Y < 1/4] = 1 - Pr[1 - Y > 3/4] ≥ 1 - E[1 - Y]/(3/4) = 1 - (5/8)/(3/4) = 1 - 5/6 = 1/6.
Q: Why does linearity of expectation still work in the Colorful-Triangle problem even though the indicator variables for different triangles are not independent?
A: Linearity of expectation holds for any random variables, regardless of dependence. It is a property of the expectation operator itself, not of the joint distribution.
The geometric-random-variable analysis of Bogosort is a toy version of the same technique used to analyse randomised algorithms like the coupon collector problem and randomised leader election. The indicator-variable approach to Colorful-Triangle generalises to MAX-CUT and MAX-SAT approximation analyses. Markov's inequality is the starting point for stronger concentration inequalities (Chebyshev, Chernoff) that appear later in the course and in algorithms research.
Randomized algorithm, expected running time, Bogosort, permutation sort, geometric random variable, indicator random variable, linearity of expectation, colourful triangle, graph colouring, approximation ratio, approximation algorithm, Markov's inequality, concentration inequality, Chebyshev's inequality, MAX-CUT, MAX-SAT, probabilistic analysis, EECS 376, Foundations of Computer Science, UMich