Difficulty: Intermediate | Prerequisites: Basic probability (expectation, indicator random variables), graph theory basics
Randomised algorithms use random choices as part of their logic, trading deterministic guarantees for simplicity or speed. This section of the final review covers two problems: Bogosort (a toy sorting algorithm whose expected runtime is derived from the geometric distribution) and the COLORFUL-TRIANGLE problem (a graph-colouring optimisation analysed with indicator random variables, linearity of expectation, and Markov's inequality). These are the core probabilistic tools that EECS 376 expects you to apply fluently on exam problems. You should be comfortable with basic probability, expected value, and indicator random variables before diving in.
Bogosort randomly shuffles an array until it happens to be sorted; its expected runtime is O(n · n!) because only 1 out of n! permutations is correct. The COLORFUL-TRIANGLE problem shows how a random 4-colouring makes each triangle colourful with probability 3/8, giving a 3/8-approximation via linearity of expectation, and Markov's inequality bounds the probability of getting at least a 1/4 fraction colourful at ≥ 1/6.
Randomised algorithm
An algorithm that makes random choices during execution. Its output or runtime (or both) may vary across runs on the same input.
Expected value (E[X])
The probability-weighted average of all possible values of a random variable X. In simple terms, the long-run average outcome if you repeated the experiment many times.
Geometric distribution
The distribution of the number of independent trials needed to get the first success, where each trial succeeds with probability p. Its expected value is 1/p. Think of it as: how many coin flips until you get heads.
Indicator random variable
A random variable that equals 1 if a particular event occurs and 0 otherwise. Useful because E[Xᵢ] = Pr[Xᵢ = 1], and summing indicators counts how many events happen.
Linearity of expectation
E[X₁ + X₂ + ... + Xₙ] = E[X₁] + E[X₂] + ... + E[Xₙ], regardless of whether the variables are independent. This is the single most useful tool for analysing randomised algorithms in this course.
Markov's inequality
For a non-negative random variable X and any a > 0: Pr[X ≥ a] ≤ E[X]/a. It gives an upper bound on the probability that a non-negative variable exceeds a threshold. The bound is often loose but requires no assumptions beyond non-negativity.
Reverse Markov's inequality
If 0 ≤ Y ≤ 1, then Pr[Y > t] ≥ (E[Y] − t) / (1 − t). Useful for lower-bounding the probability that a bounded random variable exceeds a threshold.
Approximation ratio
The worst-case ratio between the value achieved by an algorithm and the optimal value. For a maximisation problem, a c-approximation satisfies c · OPT ≤ E[ALG] (or ALG ≥ c · OPT in every run).
Colourful triangle
A triangle in a graph whose three vertices are assigned pairwise distinct colours. The COLORFUL-TRIANGLE problem asks for a colouring that maximises the number of such triangles.
Bogosort works as follows: generate a uniformly random permutation of the array, check whether it is sorted, and repeat until it is. Both the shuffle and the sorted-check take O(n) time.
Let X be the number of iterations until the array is sorted. There is exactly one sorted permutation out of n! total permutations, so each iteration succeeds with probability 1/n!.
X follows a geometric distribution with success probability p = 1/n!. The expected value of a geometric random variable is 1/p, so:
E[X] = 1 / (1/n!) = n!
Each iteration costs O(n) time (one shuffle plus one check), so the overall expected time complexity is:
O(n · n!)
Nobody uses Bogosort in practice. Its value is pedagogical: it is a clean example of applying the geometric distribution to compute the expected number of trials before a rare event occurs. The same reasoning applies to any randomised process that repeats independent trials until success.
Given an undirected graph G = (V, E), assign one of four colours to each vertex to maximise the number of colourful triangles (triangles whose three vertices all have different colours). The algorithm: assign each vertex a uniformly random colour, independently.
Let X_T be the indicator for whether triangle T is colourful. There are two equivalent ways to compute Pr[X_T = 1].
Counting approach: 4 · 3 · 2 = 24 colourful assignments out of 4³ = 64 total, so Pr[X_T = 1] = 24/64 = 3/8.
Conditional approach: Fix the first vertex's colour (probability 1). The second vertex must differ from the first: probability 3/4. The third must differ from both: probability 2/4. So Pr[X_T = 1] = 1 · (3/4) · (2/4) = 3/8.
Let X = the total number of colourful triangles = the sum of X_T over all triangles T. Let t = total number of triangles in the graph. By linearity of expectation:
E[X] = Σ E[X_T] = (3/8) · t
Linearity of expectation does not require independence, which is important here because triangles sharing an edge are not independent.
Let OPT = the maximum number of colourful triangles under any colouring. Since OPT ≤ t (at most all triangles are colourful):
(3/8) · OPT ≤ (3/8) · t = E[X] = E[ALG]
So the random colouring is a 3/8-approximation algorithm in expectation. That means, on average, the algorithm achieves at least 3/8 of the best possible result.
Let Y = X / t, the fraction of triangles that are colourful under the random 4-colouring. From the previous section, E[Y] = E[X] / t = 3/8.
The question: give a lower bound on Pr[Y ≥ 1/4].
Define Z = 1 − Y (the fraction of non-colourful triangles). Z is non-negative and E[Z] = 1 − 3/8 = 5/8.
Observe that Y ≥ 1/4 is equivalent to Z ≤ 3/4. Apply Markov's inequality to Z:
Pr[Z ≥ 3/4] ≤ (5/8) / (3/4) = 5/6
Therefore:
Pr[Y ≥ 1/4] = Pr[Z ≤ 3/4] = 1 − Pr[Z ≥ 3/4] ≥ 1 − 5/6 = 1/6
Since 0 ≤ Y ≤ 1, the reverse Markov inequality applies directly:
Pr[Y > 1/4] ≥ (E[Y] − 1/4) / (1 − 1/4) = (3/8 − 1/4) / (3/4) = (1/8) / (3/4) = 1/6
And since Pr[Y ≥ 1/4] ≥ Pr[Y > 1/4], we get Pr[Y ≥ 1/4] ≥ 1/6.
The bound tells us that with probability at least 1/6, a single random colouring makes at least a quarter of all triangles colourful. Combined with the 3/8-approximation result, this gives both an expected-value guarantee and a probability guarantee for the randomised algorithm.
Students sometimes try to use independence when applying linearity of expectation. Linearity holds whether or not the random variables are independent. You never need to prove independence to use it.
Markov's inequality only applies to non-negative random variables. Applying it to a variable that can be negative gives a meaningless result. If you need to bound a variable that is not non-negative, transform it first (as with the Z = 1 − Y trick).
When counting colourful assignments, students sometimes forget that order matters in the numerator (4 · 3 · 2 = 24) but forget to account for order in the denominator (4³ = 64, not 4 · 3 · 2). Both numerator and denominator must use the same counting convention.
Students often confuse the approximation ratio direction. For a maximisation problem, a 3/8-approximation means E[ALG] ≥ (3/8) · OPT, not OPT ≥ (3/8) · ALG.
⚠️ Linearity of expectation is the most commonly tested tool in the randomised algorithms section. Be ready to define indicator variables, compute their individual expectations, and sum them.
⚠️ Know how to identify a geometric distribution: independent, repeated trials with constant success probability. The expected number of trials is 1/p.
⚠️ Markov's inequality questions often require a trick: bound the complement variable, or use the reverse form for bounded random variables. Practise both.
⚠️ Approximation-ratio arguments follow a standard template: define ALG and OPT, use linearity of expectation to compute E[ALG], and relate OPT to the total count.
⚠️ When asked for a probability bound, state clearly which inequality you are using and verify its preconditions (non-negativity for Markov, boundedness for reverse Markov).
True or False: Linearity of expectation requires the random variables to be independent. (False.)
Fill in the blank: Bogosort's expected number of iterations is ______ because only one permutation out of n! is sorted. (n!)
True or False: Markov's inequality can be applied to any random variable, including those that take negative values. (False, it requires non-negativity.)
Fill in the blank: The probability that a single triangle is colourful under a random 4-colouring is ______. (3/8)
True or False: A 3/8-approximation for a maximisation problem means the algorithm's expected output is at most 3/8 of optimal. (False, it means at least 3/8 of optimal.)
Q: Derive the expected time complexity of Bogosort for an array of n distinct integers.
A: Each iteration generates a random permutation and checks if it is sorted, both in O(n). The number of iterations follows a geometric distribution with p = 1/n!, so E[iterations] = n!. Total expected time = O(n · n!).
Q: Why can we use linearity of expectation to compute the expected number of colourful triangles, even though triangles sharing an edge are not independent?
A: Linearity of expectation holds for any sum of random variables, whether or not they are independent. We only need E[X] = Σ E[X_T], and each E[X_T] = 3/8.
Q: Using the random 4-colouring, what approximation ratio does the algorithm achieve for COLORFUL-TRIANGLE?
A: 3/8. Since OPT ≤ t and E[ALG] = (3/8)t, we have (3/8) · OPT ≤ E[ALG].
Q: Use Markov's inequality to show that Pr[Y ≥ 1/4] ≥ 1/6, where Y is the fraction of colourful triangles.
A: Define Z = 1 − Y (non-negative). E[Z] = 5/8. Markov gives Pr[Z ≥ 3/4] ≤ (5/8)/(3/4) = 5/6. So Pr[Y ≥ 1/4] = 1 − Pr[Z ≥ 3/4] ≥ 1/6.
Q: What precondition must you verify before applying Markov's inequality?
A: The random variable must be non-negative. If it is not, you cannot apply Markov directly. Transform it (e.g. use Z = 1 − Y) or use a different bound.
The indicator-variable technique used in COLORFUL-TRIANGLE is the same approach used to analyse randomised algorithms throughout EECS 376, including hashing, load balancing, and randomised quicksort.
Markov's inequality is the foundation for stronger tail bounds (Chebyshev, Chernoff) covered later in the course. Understanding when and why Markov is loose prepares you for appreciating what the stronger bounds add.
The approximation-ratio framework connects directly to the NP-hardness material in the reductions unit: when a problem is NP-hard, we settle for approximation algorithms, and analysing their ratio is the payoff of the randomised-algorithms toolkit.
randomised algorithm, randomized algorithm, expected value, expectation, geometric distribution, indicator random variable, linearity of expectation, Markov inequality, reverse Markov, Bogosort, bogo sort, colourful triangle, colorful triangle, graph colouring, approximation ratio, approximation algorithm, NP-hard approximation, EECS 376, foundations of computer science, University of Michigan, final review, probability, random variable