VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

The Gold Standard of Randomized Algorithms

A randomized algorithm deliberately uses random choices while it computes. Those choices can simplify a procedure, avoid consistently unlucky decisions or reduce the work needed to check an answer. The gold standard is a precise guarantee: what remains correct, what can fail, how likely failure is, and what time or memory the guarantee costs.

Randomness does not automatically make an algorithm approximate or unreliable. Random-pivot quicksort sorts exactly but has a variable running time; a randomized matrix check has a bounded chance of accepting an incorrect product. Understanding that distinction lets you choose a method for the actual task instead of trusting the word “random”.

This guide develops the subject through small calculations that can be checked by hand, then connects them to graph contraction, random sketches and reproducible experiments. The examples are constructed teaching cases. For the wider learning map, visit The Gold Standard and Education: learning transfers into life. The How X Works hub provides complementary explanations of mechanisms in practice.

CHAPTER 1 OF 14 · Understand the guarantee

1. Locate the randomness before judging the algorithm

Back to contents

Fixed input, changing choices

Imagine sorting the same five records twice. A deterministic procedure follows the same decisions when the input and execution conditions are unchanged. A randomized procedure may choose different pivots because it reads a sequence of random choices. We can describe it as A(x, r): x is the input and r is the random sequence. Fix both, and the abstract computation is determined.

This separates two questions. Does an algorithm perform well on inputs drawn from a particular distribution? Does it perform well on every fixed input when we average over its own choices? The second statement is a typical randomized-algorithm guarantee. An awkwardly ordered input need not ruin random-pivot quicksort’s expected comparison count. The analysis does not require the user to supply a randomly ordered list.

State a contract that could be checked

A useful contract names the input domain, random experiment, returned object, correctness condition and resource measure. For a small sorting study, use distinct integer keys, a uniform pivot from each current subarray, a sorted permutation as output and key comparisons as cost. Do not quietly substitute elapsed seconds for comparisons. Allocation, caching and recursion overhead affect elapsed time even when the comparison analysis is correct.

For matrix verification, the contract needs an arithmetic domain as well. Exact integers, a finite field and floating-point arithmetic are different settings. A guarantee proved using exact equality does not directly justify accepting a small numerical residual. That change requires a numerical error analysis, not just a larger number of random trials.

Write the source of chance in a sentence before running an experiment: “The data remain fixed; only the pivot choices change.” If you cannot say what is random, a reported average has no clear interpretation. The Gold Standard of Randomness develops probability models, independence and generators. Here the focus is how those ideas support computational procedures and their guarantees.

Contents · Next chapter

CHAPTER 2 OF 14 · Understand the guarantee

2. Separate uncertain runtime from uncertain answers

Back to contents

Las Vegas and Monte Carlo

A Las Vegas algorithm returns a correct answer when it returns one; randomness affects resources such as running time. Analyses normally also establish termination and an expected resource bound. Random-pivot quicksort is a familiar example: any permitted pivot sequence produces a sorted result, although some sequences produce much more work than others.

A Monte Carlo algorithm has a bounded resource budget but may return an incorrect answer with a stated probability. This terminology describes an algorithmic guarantee, rather than every everyday use of “Monte Carlo”. An estimator may instead have an accuracy statement such as “within the requested error with probability at least 0.99”. Always read what the probability refers to.

For a decision problem, distinguish one-sided from two-sided error. In exact Freivalds verification, a correct matrix product always passes. An incorrect product can also pass, but only with a bounded probability under the sampling assumptions. A detected mismatch is conclusive. A pass is evidence with a failure bound, not a deterministic proof of equality.

A deadline changes the contract

Suppose a correct randomized search has expected cost at most 200 operations. Stopping it at 800 operations creates a new outcome: timeout. If the procedure reports “not found” on timeout, that answer may be false. If it reports “budget exhausted”, it remains honest, but it no longer always supplies the requested answer within the budget.

The reverse transformation also needs care. Repeating a fallible procedure until its output passes an exact, inexpensive certificate check can sometimes yield a Las Vegas procedure. It works only when the certificate check really establishes correctness and success arrives with adequate probability. Repeating until two guesses agree does not establish that either guess is right.

In a practical decision, ask which uncertainty is acceptable. A batch computation may tolerate variable completion time. A monitoring pipeline may require a strict work budget and a documented error allowance. The distinction is part of the problem specification, not a ranking in which one label is always better. The broader Algorithm Design root connects these contracts to correctness arguments and resource constraints.

Previous chapter · Contents · Next chapter

CHAPTER 3 OF 14 · Understand the guarantee

3. Calculate expectations without inventing independence

Back to contents

Small variables make a large calculation manageable

An indicator variable is 1 when an event occurs and 0 otherwise. Its expectation equals the event’s probability. If a total cost is the sum of indicator variables, its expectation is the sum of their probabilities. This use of linearity of expectation does not require the indicators to be independent.

For a constructed diagnostic example, suppose two warning lights always turn on together. Each is on with probability 1/4. The number of illuminated lights is either 0 or 2, so its expectation is 0 × 3/4 + 2 × 1/4 = 1/2. Adding the individual expectations also gives 1/4 + 1/4 = 1/2. Multiplying their probabilities to claim that both are on with probability 1/16 would be wrong: that event actually has probability 1/4.

The lesson matters in algorithm analysis. Comparisons within a sorting run depend on shared pivot choices. That dependence does not prevent adding their expected contributions. It does prevent freely multiplying arbitrary event probabilities. When multiplying probabilities along a process, use conditional probabilities or justify independence explicitly.

An expectation is not a deadline

For a nonnegative cost T and a positive threshold b, Markov’s inequality gives Pr(T ≥ b) ≤ E[T]/b. The reason is direct: outcomes costing at least b contribute at least b times their total probability to the expectation. If E[T] ≤ 200, the bound at b = 800 is at most 1/4. It does not say the actual tail probability equals 1/4.

This is a deliberately weak bound that requires little information. A stronger concentration result needs additional structure. A measured mean alone cannot justify claims such as “almost every run finishes close to the mean”. A rare expensive execution can contribute greatly to the expectation, and a service deadline depends on the tail, not only the average.

Keep three entries separate in an experiment: the theoretical expectation bound, the empirical mean across the sampled runs and the largest observed cost. None of the three is automatically interchangeable with a worst-case guarantee. Princeton’s randomization notes give the probability tools behind this style of analysis.

Previous chapter · Contents · Next chapter

CHAPTER 4 OF 14 · Analyse exact sorting

4. Work through random-pivot quicksort on five keys

Back to contents

Count the operation you actually specified

Use the distinct keys 3, 8, 12, 19 and 27. At each nontrivial recursive call, choose one of its keys uniformly as pivot and compare every other key in that call with it exactly once. Exclude comparisons used for implementation bookkeeping. The first partition always costs four key comparisons.

If 12 is the first pivot, the two remaining groups each have two keys. Each group takes one further comparison, giving six in total. If the smallest remaining key is chosen at every stage, the comparison count is 4 + 3 + 2 + 1 = 10. Both outcomes sort correctly. Randomization changes the frequency of the costly paths rather than making those paths impossible.

Let E(n) denote the expected comparisons for n distinct keys, with E(0) = E(1) = 0. Conditioning on the first pivot’s rank gives E(n) = n − 1 + (1/n) × Σ[E(k) + E(n − 1 − k)], where k runs from 0 to n − 1. The rank is uniform because the pivot is uniform among the current keys.

Resolve the recurrence numerically

E(2) = 1. For three keys, the middle pivot costs two comparisons in total, while either endpoint costs three, so E(3) = 8/3. Then E(4) = 3 + (2/4) × [0 + 0 + 1 + 8/3] = 29/6. Finally E(5) = 4 + (2/5) × [0 + 0 + 1 + 8/3 + 29/6] = 37/5 = 7.4.

No individual run uses 7.4 comparisons. The expectation is a weighted average of integer costs. An exhaustive calculation can enumerate pivot choices recursively and check both the output order and the cost distribution; a random experiment should approach this value with enough independent runs, subject to sampling variation.

Repeated keys require a fresh implementation check. A partition routine that repeatedly sends equal keys into one large recursive branch can behave poorly on an all-equal input. The distinct-key calculation has not established a guarantee for that routine. State the equality handling, test duplicate-heavy lists, and use the analysis appropriate to that partition rule.

Previous chapter · Contents · Next chapter

CHAPTER 5 OF 14 · Analyse exact sorting

5. Understand why pair counting gives an efficient expectation

Back to contents

Follow one pair until it separates

Order the distinct keys by value as z₁ through zₙ. Consider zᵢ and zⱼ with i < j. Until a pivot is selected from the rank interval i through j, both keys remain in the same active subproblem. If the first pivot from that interval is an interior key, it separates the pair. If it is either endpoint, the pair is compared. Each of the j − i + 1 keys is equally likely to be first, giving comparison probability 2/(j − i + 1).

Adding that probability over all pairs yields the expected comparison count, because each pair is compared at most once. The resulting expression is 2(n + 1)Hₙ − 4n, where Hₙ = 1 + 1/2 + … + 1/n. Harmonic growth gives O(n log n). CMU’s algorithm lectures develop randomized quicksort and probabilistic analysis.

Inspect the five-key contributions

For our five keys, there are four adjacent pairs. Each must eventually be compared, contributing four. There are three pairs separated by one intervening key; each contributes 2/3, giving two more. Two pairs have an interval of four keys and contribute 1/2 each, giving one. The extreme pair contributes 2/5. The total is 4 + 2 + 1 + 0.4 = 7.4, independently matching the recurrence calculation.

This decomposition explains where comparisons are spent. Nearby ranks are difficult to separate without direct comparison; distant ranks have more opportunities for an interior pivot to separate them. It also gives a debugging strategy. Instrument a five-key implementation to record pairs, not only total comparisons. A pair appearing twice violates the model used in this calculation, even if the final list is sorted.

Do not interpret O(n log n) as a fixed time in milliseconds or as a guarantee for every random sequence. Nor does the proof say this exact implementation is the best practical sorting routine. Its value is a transparent connection between local random choices and a global expected cost, with an experiment small enough to audit completely.

Previous chapter · Contents · Next chapter

CHAPTER 6 OF 14 · Verify and amplify

6. Verify a matrix product through random directions

Back to contents

A worked exact-arithmetic check

Take A with rows (1, 2) and (0, 1), and B with rows (2, 1) and (3, 4). Their true product has rows (8, 9) and (3, 4). Suppose a program instead reports C with rows (8, 10) and (3, 4). We want to test the claim without recomputing every entry of a large product.

Choose a column vector r whose two entries are independent fair bits. Compare A(Br) with Cr, using this parenthesization. For r = (1, 0), Br = (2, 3), and both sides give (8, 3). The incorrect product passes. For r = (0, 1), Br = (1, 4), A(Br) = (9, 4), and Cr = (10, 4). The mismatch exposes the error.

The four possible vectors are (0, 0), (1, 0), (0, 1) and (1, 1). The first two pass and the last two fail, so this particular wrong matrix passes with probability exactly 1/2. The zero vector is uninformative but is included in the stated fair-bit experiment. Removing it changes the distribution and requires a correspondingly different analysis.

Why any nonzero error is detectable

Let D = AB − C over an exact field. If D is nonzero, select a row containing a nonzero coefficient dⱼ. Hold every random bit except rⱼ fixed. At most one of rⱼ = 0 and rⱼ = 1 can make that row’s dot product zero, since their difference is dⱼ. Thus Pr(Dr = 0) ≤ 1/2. If AB = C, every vector passes.

Three dense matrix–vector products require O(n²) arithmetic operations per trial; computing AB first would defeat the intended shortcut. Bit costs still matter for large integers. The Freivalds specialist article extends the mechanism. The algebraic techniques reference covers the underlying fingerprinting method. Neither the time bound nor the error bound excuses overflow or an unjustified floating-point equality test.

Previous chapter · Contents · Next chapter

CHAPTER 7 OF 14 · Verify and amplify

7. Spend an error budget across repeated checks

Back to contents

Independent repetition has a measurable price

For a fixed incorrect product, each fresh independent Freivalds trial passes with probability at most 1/2. Accept only if every trial passes. After t independent trials, the chance of false acceptance is at most 2⁻ᵗ. A single mismatch rejects immediately, so an incorrect candidate may be rejected before the full trial budget is spent.

Suppose the target is at most one false acceptance per million in the probability bound for one fixed check. Twenty trials suffice because 2⁻²⁰ = 1/1,048,576, approximately 0.000000954. Nineteen trials do not meet that target. This is an upper bound over the algorithm’s random choices, not a promise that precisely one in a million submitted products will be wrong or accepted incorrectly.

Now suppose a constructed batch has 10,000 fixed products to check, and the desired probability of any false acceptance across the batch is at most 0.001. The union bound gives at most 10,000 × 2⁻ᵗ. Twenty-four trials per check suffice: the bound is about 0.000596. Twenty-three give about 0.001192 and miss the target. Independence between different products is not needed for this union bound, although each product still needs its valid per-check guarantee.

Repetition is not automatic amplification

Reinitialising a generator with the same seed before every trial can produce the same vector each time. In our two-by-two example, repeating the same chosen vector twenty times leaves false acceptance probability at 1/2, not 2⁻²⁰. Calling the procedure repeatedly does not prove that the random experiments are independent.

Two-sided error also needs a different aggregation rule. If an algorithm is correct with probability 2/3 independently per run, a majority vote across three runs is wrong with probability 3 × (1/3)² × (2/3) + (1/3)³ = 7/27. Requiring unanimous agreement and silently accepting whichever answer appears is a different procedure. First identify which outputs are conclusive, then select and analyse the aggregation rule.

Keep the failure budget attached to the scope of the claim: one query, a fixed batch, or an ongoing process. An indefinitely growing number of queries cannot inherit a fixed whole-system guarantee merely by repeating a per-query slogan.

Previous chapter · Contents · Next chapter

CHAPTER 8 OF 14 · Verify and amplify

8. Preserve a graph cut while contracting random edges

Back to contents

What contraction retains

In an undirected graph, a cut partitions the vertices into two nonempty groups. Its size is the number of edges joining the groups. A global minimum cut minimises that count. Karger’s basic procedure repeatedly chooses a current edge uniformly and merges its endpoints until two supernodes remain. Preserve parallel edges and discard self-loops; the final two supernodes represent a cut of the original graph.

For a fixed minimum cut of size λ, every current vertex has degree at least λ while that cut survives. With r vertices, there are at least rλ/2 edges, so the next contraction hits the fixed cut with probability at most 2/r. Multiplying conditional survival bounds from r = n down to 3 gives success probability at least 2/[n(n − 1)]. Stanford’s lecture on Karger’s algorithm explains this argument.

A complete four-vertex audit

Take the complete graph on vertices A, B, C and D: every pair has one edge. Isolating a single vertex gives a cut of size three; a two-versus-two partition gives size four. By symmetry, suppose the first selected edge is AB. After contraction, five edges remain: two from AB to C, two from AB to D and one from C to D.

If the next choice is any of the first four edges, the final partition isolates one vertex and has size three. Choosing CD instead produces the partition AB versus CD and size four. Therefore this graph’s probability of finding some minimum cut in one run is 4/5. This is larger than the general lower bound 1/6 for n = 4. A lower bound need not be tight on a particular input.

Repeating complete independent runs and retaining the smallest actual cut is appropriate: no valid cut can have a size below the true minimum. But a returned cut is not automatically a certificate that no smaller cut exists. Keep the distinction between verifying its edge count and verifying global optimality.

Deleting parallel edges would change the five-way selection experiment into a three-way one. The error is therefore mathematical as well as representational. The Karger specialist article gives further contraction investigations. Disconnected graphs can first be recognised as having a zero cut; the positive-λ survival argument above is intended for connected graphs.

Previous chapter · Contents · Next chapter

CHAPTER 9 OF 14 · Implement and transfer

9. Use a random subspace without confusing error measures

Back to contents

Compress the directions of variation

Large matrices sometimes have most of their useful variation concentrated in a modest-dimensional subspace. A randomized range finder forms Y = AΩ, where Ω has fewer columns than A and is drawn from a specified random distribution. An orthonormal basis Q for Y gives the approximation QQᵀA. Subsequent computation can operate on the smaller representation QᵀA.

The Halko, Martinsson and Tropp paper develops this framework and its error analysis. The important design choices include the target rank, extra sampling columns and the distribution of Ω. Power iterations can improve separation between dominant and weaker singular directions, at the cost of additional passes and numerical considerations. An algorithm is not fully specified by saying “multiply by a random matrix”.

A two-dimensional warning case

Let A be the diagonal matrix with entries 6 and 1. Its columns point along the coordinate axes, with very different magnitudes. For a one-column teaching illustration, choose Ω = (1, 1). Then Y = (6, 1), and Q is that vector divided by √37. This choice demonstrates the projection mechanics; it is not a substitute for a guarantee under a prescribed random distribution.

The total squared Frobenius norm of A is 36 + 1 = 37. The squared norm captured by QᵀA is (36² + 1)/37 = 1297/37. The squared residual is therefore 37 − 1297/37 = 72/37, approximately 1.946. Choosing the first coordinate axis alone gives squared residual 1, the best rank-one value for this diagonal example. A plausible-looking direction need not be optimal.

If Ω were instead (0, 1), the sampled range would miss the dominant direction entirely, leaving squared residual 36. This is why a sampling theorem, not a visual intuition, must justify confidence. More sampled directions, a different distribution or additional iterations change the procedure and the applicable bound.

The Randomized SVD specialist article connects the mechanism to numerical practice. Distinguish squared Frobenius error, Frobenius error and spectral error when comparing outputs. A small reconstruction error also does not by itself establish that a compressed representation preserves the feature needed by a downstream decision.

Previous chapter · Contents · Next chapter

CHAPTER 10 OF 14 · Implement and transfer

10. Make implementations reproduce the intended experiment

Back to contents

A seed is a record of a run

A pseudorandom generator produces a deterministic sequence from its initial state. A seed can help reproduce a failure, but the full experiment also depends on the generator implementation, code, data ordering and how random draws are consumed. In concurrent code, scheduling can change which task receives which draw. Record enough of the execution to reconstruct the relevant choices.

For a sorting experiment, retain the input, pivot-selection routine, seed or recorded pivot sequence, comparison-counting convention and software version. Use several seeds to study variability, but do not describe a short list of seed labels as proof of independence. The mathematical analysis concerns a particular distribution of random choices; the implementation must be evaluated against that assumption.

Uniform selection can be broken by a small shortcut

Suppose a teaching generator returns each integer 0 through 7 with probability 1/8, and an algorithm needs one of three indices uniformly. Taking the value modulo 3 gives index 0 from 0, 3 and 6; index 1 from 1, 4 and 7; and index 2 from 2 and 5. The probabilities are 3/8, 3/8 and 2/8, not 1/3 each.

One correction is to reject 6 and 7, then reduce the accepted value modulo 3. Each index now has two accepted preimages. Acceptance probability is 6/8 = 3/4, so the expected number of independent draws per accepted index is 4/3. This demonstrates the trade-off: exact uniformity can require variable work. Use an appropriate tested bounded-integer routine in real software rather than assuming remainder arithmetic is unbiased.

Decide what the input can depend on

Many proofs fix the input before the algorithm’s fresh random choices. If someone sees those choices and then constructs the input to exploit them, the proof’s order of quantifiers has changed. The matrix example in Chapter 12 makes that failure concrete. Randomization may protect against a fixed awkward input while offering no protection against an adversary who knows all future choices.

Reproducibility, statistical simulation and unpredictability are different requirements. A generator suitable for one is not automatically suitable for the others. Specify the purpose and threat model before selecting an implementation. A deterministic seed that is useful for a classroom experiment should not be presented as an unpredictability guarantee.

Previous chapter · Contents · Next chapter

CHAPTER 11 OF 14 · Implement and transfer

11. Learn when randomness can be removed

Back to contents

An expectation can prove that a good solution exists

Consider an undirected graph with m edges and no self-loops. Independently place each vertex in one of two groups with equal probability. An edge crosses the partition when its endpoints receive different labels, which happens with probability 1/2. The expected cut size is m/2 by linearity of expectation. Therefore at least one assignment has a cut of at least m/2; otherwise the average would be smaller.

This is a maximum-cut argument, unlike the minimum-cut problem in Chapter 8. The objective is now to make the crossing set large. Since the maximum possible cut is at most m, a cut of at least m/2 achieves at least half of the optimum. The statement does not say every random partition achieves that value.

Resolve a triangle one decision at a time

Take a triangle A–B–C–A. There are eight equally likely assignments of its three vertices. Two put all vertices together and cut zero edges; six split them and cut two. The expectation is (2 × 0 + 6 × 2)/8 = 1.5, whereas the maximum is two.

Fix A in the left group. The conditional expected cut remains 1.5. If B also goes left, edge AB contributes zero, and the expected total from AC and BC is one. If B goes right, AB contributes one and the other two edges contribute one in expectation, giving two. Choose B right. Either placement of C then gives a cut of two. Each decision retained a conditional expectation at least as large as before.

The general method chooses a value that does not decrease the conditional expectation. The average of the two possible next expectations equals the current one, so at least one choice qualifies. When those expectations can be computed efficiently, this produces a deterministic algorithm. CMU’s conditional-expectation exercise develops the max-cut setting.

This does not prove that randomness can always be removed cheaply. Calculating the conditional expectations may itself be difficult, or the desired property may need another argument. The useful habit is to ask whether a probability proof only establishes existence or also suggests an efficient way to construct the promised object.

Previous chapter · Contents · Next chapter

CHAPTER 12 OF 14 · Implement and transfer

12. Transfer the reasoning when one assumption changes

Back to contents

Case A: the candidate sees the test vector

Return to matrix verification, but reveal r = (1, 1) before the candidate product is chosen. Let the error matrix D have first row (1, −1) and second row (0, 0). D is nonzero, yet Dr = (0, 0). A candidate C = AB − D is incorrect and passes this particular test with certainty. The original statement fixed C before drawing r; it did not promise protection against a candidate chosen after seeing r.

Repair the experimental order: commit to the candidate first, then draw the fresh test vectors under the required assumptions. Repeating the already revealed vector cannot repair the issue. This example is a check on the scope of a theorem, not a claim that every practical verification system uses the same protocol.

Case B: a modulus hides the error

Suppose an integer candidate differs from the true product by five in one entry, but you verify all arithmetic modulo 5. The error becomes zero in that field. Every random vector passes, no matter how many trials you perform. The finite-field algorithm has correctly tested equality modulo 5; it has not established equality over the integers.

A repair requires a justified arithmetic strategy, such as exact computation or a modular scheme with proven reconstruction or error-detection conditions and suitable bounds on possible values. Merely selecting a convenient modulus does not establish those conditions. More randomness within the same blind arithmetic domain cannot reveal an error that the domain has erased.

Case C: a batch becomes adaptive

The 10,000-product calculation in Chapter 7 concerned a fixed batch. If each next candidate is chosen using information leaked by earlier tests and the same hidden random structure is reused, the original per-check bound may no longer apply conditionally. A union bound remains valid for events with valid individual bounds; the weak point is assuming those bounds without checking the adaptive setting.

For each changed case, write three sentences: the old assumption, the new behaviour and the replacement argument. This is a more demanding transfer test than reproducing 2⁻ᵗ from memory. It distinguishes knowing a formula from knowing when the formula describes the actual experiment.

Previous chapter · Contents · Next chapter

CHAPTER 13 OF 14 · Diagnose and continue

13. Diagnose misleading results and answer common questions

Back to contents

Symptoms and repairs

If every seed produces exactly the same pivot sequence, inspect where the generator is initialised and whether the seed is actually used. If a matrix checker accepts a deliberately corrupted matrix in every trial, test whether the candidate is fixed, the sampled vectors vary, the arithmetic preserves the error and the code computes A(Br) rather than reusing a cached wrong result.

If graph contraction often returns impossible cut counts, carry original vertex memberships through each merge and independently count crossing edges in the original graph. If measured quicksort counts disagree with 7.4 for five distinct keys, compare the counting convention and partition procedure before blaming random fluctuation. If the procedure is different, the correct theoretical expectation may also be different.

For randomized low-rank approximation, inspect both the residual and the metric used to measure it. A reported “error of two” is incomplete without the norm, scaling and whether the value is squared. Repeatability alone does not validate a computation: a deterministic bug can be perfectly reproducible.

Does a randomized algorithm give a different answer every time?

No. Sorting has the same ordered result for distinct keys regardless of the pivot choices. Different runs can change intermediate states or cost while preserving the answer. Some graph problems have several equally optimal answers, so different valid outputs need not indicate error.

Is a low failure probability the same as being probably correct after a pass?

Not automatically. A bound on accepting a fixed wrong candidate is a statement about the test’s behaviour conditional on that candidate. A posterior probability that a candidate is correct after passing also depends on how candidates are produced and on other evidence. Do not reverse the conditioning without a model.

Is one successful benchmark enough?

No. It checks one input and some random choices. Use small exact oracles, adversarially selected but fixed test inputs, edge cases and recorded random sequences. Experiments can expose bugs and measure practical performance; they do not replace an all-input proof.

Are randomized algorithms always faster?

No. Random-number generation, repetition, validation and data movement all cost resources. Deterministic alternatives may be better for the workload. Compare complete implementations under the same correctness and accuracy requirements, including setup and failure handling. Randomization is a design option with a proof obligation, not a universal optimisation switch.

Previous chapter · Contents · Next chapter

CHAPTER 14 OF 14 · Diagnose and continue

14. Build a learning route with independently checkable results

Back to contents

Four practical stages

Begin with probability and exact small experiments. Enumerate all eight assignments of a triangle and all four bit vectors in the matrix example. State which outcomes are equally likely and why. An answer that lists outcomes without a distribution is not yet a probability calculation. Check the resulting fractions before moving to code.

Next, implement a small instrumented sorting routine. For each run, retain the pivot choices, compared pairs and sorted output. Compare the five-key recurrence with the pair-counting calculation and with an exhaustive or carefully sampled experiment. Then introduce duplicate keys and explain exactly which part of the old model no longer applies.

Third, build a matrix verification notebook using exact small integers. Include correct products, a one-entry error, a cancellation error and a repeated-seed failure. Compute the number of trials from a declared batch error budget. The deliverable is a short explanation that distinguishes the arithmetic guarantee from the sampling guarantee, supported by reproducible cases.

Finally, study one extension in depth. Use the Streaming Algorithms root for sampling and sketches under memory limits, or the Randomized SVD article for numerical matrix compression. Explain which resource is saved, which information is lost and what independently measured quantity would reveal failure.

Sources and further technical reading

CMU: Probabilistic Analysis and Randomized Quicksort, in Lectures 1–10 supports the distinction between random input assumptions and internal random choices, and the expected comparison analysis.

Princeton: Randomized Algorithms provides probability tools and algorithmic applications. Stanford: Karger’s Min-Cut Algorithm and Random-Pivot Quicksort develops contraction and pair-counting arguments. Preserve the inequalities in these guarantees: a lower or upper bound is not automatically an equality for a specific input.

Algebraic Techniques: Fingerprinting and Freivalds’ Technique provides the matrix-checking foundation. CMU: Randomization and Derandomization gives a route into conditional expectations. Halko, Martinsson and Tropp: Finding Structure with Randomness is the primary technical reference for randomized low-rank matrix approximation.

For an advanced research extension, Shinkar and Singh’s 2025 paper on error-correcting matrix multiplication uses randomized verification within a more specialised theoretical problem. Its stronger machinery is unnecessary for the small examples here, but it shows why verification remains a productive research tool.

A completed learning project should leave a reader able to change one assumption and predict what breaks. Return to Education: learning transfers into life for that broader standard, then choose the next subject through the Gold Standard master.

Previous chapter · Contents · Gold Standard master