The UTokyo Mathematical Informatics Exam
A study guide for the entrance exam of the Department of Mathematical Informatics (数理情報学専攻) at the University of Tokyo: three hours, five problems, answer three. Every past problem from 2020 to 2026 is restated here with hints and a full solution, grouped by topic. Each topic is a few short modules: background shared with the book pages on this site (your answers carry over between them), a toolkit with an interactive figure and concept checks, then the practice problems.
Built from the department's published past papers (master's 2020 and 2023–2026, and the 2021–2022 report assignments), its 2026 statement of what the exam is meant to test (出題の意図), its sample problems, and the 2027 application guide. Problem numbers match the papers; the statements are restated in our own words, so check the official PDFs for exact wording. Books are from the department's recommended list; the symmetric matrices, differential equations, optimization, analysis and algorithms topics each also cite one standard book (Horn and Johnson, Strogatz, Boyd and Vandenberghe, Stein and Shakarchi, Kleinberg and Tardos) by result number, with a set of each book's exercises restated and solved. Related pages here: Linear Algebra, Real Analysis, High-Dimensional Probability, Markov Chains, Gradient Flows.
The exam and its patterns
Twenty-five problems in five papers are enough to see the shape of the exam. Problem 1 is usually linear algebra, Problem 4 is usually probability, and Problem 5 has been an algorithms problem every year. The middle two rotate through differential equations, analysis and optimization.
The idea
The department's statement of intent names five areas, linear algebra, differential equations, optimization, probability and statistics, and algorithms, and three abilities: computing and proving accurately, seeing the mathematical model behind a phenomenon, and designing algorithms. The papers match it closely. Several problems end with a part that asks what the mathematics means for the application (2025 P2(4) on phase separation is the clearest), and their sample problems ask where a matrix comes from as well as how to compute with it.
Three habits pay off on every paper:
- Read all five first. Spend ten minutes; pick the three whose last part you can see a route to. That leaves about 55 minutes each.
- Parts are a staircase. Later parts almost always use earlier ones. If you can't prove (2), say "by (2)" and use it in (3): you still earn (3).
- Read the other language when wording looks odd. In 2024 P1(2) the English says "min tr(PXYᵀ)" but the Japanese says max, and only max is correct (see the symmetric matrices topic).
In 2021 and 2022 the written exam was replaced by take-home report assignments (an essay on a concept you find important, a research survey and plan, and an essay on how mathematical informatics can address COVID-19, carbon neutrality, digital transformation or an ageing society). They are good practice for the screening essay.
Everything you need, by topic
This guide is a collection: each topic gathers the modules it needs from the book pages on this site (your answers carry over between them), then adds its own toolkit and the past-exam problems. The last column lists the rest of what is worth knowing, on the full subject pages.
Explore
Mock exam
Draws five past problems in the exam's usual slots: linear algebra, two from differential equations, analysis and optimization, probability, then algorithms. Choose three, work on paper, and open the solutions only when the clock stops.
A twelve-week plan
For someone starting from a solid undergraduate background, about ten hours a week. The order follows how often each area appears: the guaranteed slots (Problems 1, 4 and 5) first, then the rotating middle. Each week: read the module's idea section and the book sections, do the worked example and quizzes, then the past problems timed (55 minutes each, on paper, before opening any hint), then the book exercises. Keep a list of every step you got stuck on, and redo those problems a week later.
Weeks 1–2: symmetric matrices
The symmetric matrices topic: the spectral theorem first if it's rusty, then the toolkit and its past problems; Horn and Johnson §§4.1, 7.1–7.2, 7.7. Past problems 2020 P1, 2024 P1, 2025 P1, 2026 P1, then the six book exercises. Goal: diagonalize-first becomes automatic.
Weeks 3–4: probability and statistics
The probability and statistics and concentration and random walks topics (each starts with background modules shared with the book pages), with a standard probability text from the department's list (伏見 or Grimmett and Welsh) for transforms, the exponential and Poisson families, and maximum likelihood. Six past problems. Goal: change of variables, memorylessness, first-step analysis and Chernoff bounds without notes.
Weeks 5–6: algorithms
The algorithms topic; Kleinberg and Tardos §§3.6, 4.4, 6.8–6.10, 7.1–7.5, 11.1. Five past problems (including 2023 P5 from the algebra topic), then the three book exercises. Goal: every algorithm answer has the four parts (algorithm, invariant, correctness, running time).
Week 7: differential equations
The differential equations topic; Strogatz §§2.5, 6.3–6.5, 7.2. Four past problems and five book exercises. Goal: for any planar system, find the fixed points, a conserved or decreasing quantity, and the long-run behaviour.
Week 8: analysis
The analysis topic, with uniform convergence as background; Stein and Shakarchi Ch. 2 §4 and Ch. 3 §§1–2, 7. Four past problems and four book exercises.
Week 9: optimization, and algebra
The optimization topic with Boyd and Vandenberghe §§2.6, 3.1, 5.2, 8.1, and the algebra topic. 2024 P2, 2020 P3, and the five book exercises.
Weeks 10–12: full mock exams
Two full papers a week, three hours each, choosing three of five under exam conditions, then marking against the solutions: the three practice exams first, then mock exams from the generator above (past problems you may have seen, so treat them as timing practice). Spend the days in between on the stuck-list. In the final week, redo one full real paper (2026 or 2025) cold.
Words worth knowing in Japanese
Answers in English are fine, but reading the Japanese statement settles ambiguities. These terms come up on the papers above.
Check your understanding
Which problem slot has been an algorithms problem on every paper from 2020 to 2026?
- Problem 1Problem 1 is usually linear algebra (four of five papers).
- Problem 3The middle slots rotate between differential equations, analysis, optimization and algebra.
- Problem 5
You cannot prove part (2) but can see how (3) follows from it. What should you write?
- Skip (3) as well, since it depends on (2).Graders mark each part. A correct (3) that cites (2) earns its marks.
- Answer (3), stating clearly that you are using the result of (2).
- Prove a weaker version of (2) and stop.Worth doing if you have time, but don't let it cost you (3).
The 2027 guide says the written exam draws on algebraic, analytic, geometric, discrete, probabilistic, statistical and algorithmic methods. How many problems must you answer?
- All five.Five are set, but you choose.
- Three of the five.
- One from each area.There is no per-area requirement.
Reading
From the department's recommended list, the books that match these papers most closely (◎ marks the department's "standard" level):
- Linear algebra: Horn and Johnson, Matrix Analysis, Chapters 2, 4 and 7 (used in the symmetric matrices topic); 室田・杉原『線形代数 I・II』◎.
- Differential equations: Strogatz, Nonlinear Dynamics and Chaos, §§2.5, 6.3–6.5, 7.2 (used in the differential equations topic). Not on the department's list, which has no ODE book, but the exam's phase-plane and Lyapunov questions come straight from this material.
- Analysis and complex analysis: Stein and Shakarchi, Complex Analysis, Chapters 2–3 (used in the analysis topic); 杉浦『解析入門 I・II』◎; 森・杉原『複素関数論』◎; Ahlfors, Complex Analysis.
- Optimization: Boyd and Vandenberghe, Convex Optimization, §§2.6, 3.1, 5.2, 8.1 (used in the optimization topic; free from the authors); 寒野・土谷『最適化と変分法』◎; Matoušek and Gärtner, Understanding and Using Linear Programming.
- Probability and statistics: 伏見『確率と確率過程』◎; 東京大学教養学部統計学教室『自然科学の統計学』◎; Grimmett and Welsh, Probability: An Introduction.
- Algorithms: Kleinberg and Tardos, Algorithm Design, §§3.6, 6.8–6.10, 7.1–7.5, 11.1 (used in the algorithms topic); 渋谷『アルゴリズム』◎; Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms.
- Algebra and discrete mathematics: 伊理・藤重『応用代数』◎; Lidl and Pilz, Applied Abstract Algebra.
Practice exams
The department has published only five written papers, and you will want to save the real ones for last. These three papers are new problems in the same shape: five problems, answer three, three hours. Problem 1 is linear algebra, Problems 2 and 3 come from the rotating middle (differential equations, analysis, optimization), Problem 4 is probability and statistics, and Problem 5 is an algorithm with a proof.
How to use them
Sit each paper in one go. Pick your three problems in the first ten minutes, work on paper, and open a hint only after you have been stuck on a part for fifteen minutes. Mark against the solutions afterwards, part by part: the real exam gives credit for each part, so a clean (1) and (2) are worth more than a half-finished (4).
These papers were written for this page, not by the department. Each problem follows a theme the real papers test, at a similar length and difficulty, and every numerical claim in the solutions was checked by computation. They are not predictions of what will be asked.
Paper A
Linear algebra, differential equations, analysis, probability, algorithms.
Paper A, Problem 1Sums of the largest eigenvalues
Let
Hint
(2) Write
Solution
(1) Let
(2)
using
(3) Take
(4) By (2) and (3),
Paper A, Problem 2A damped oscillator with cubic friction
Consider
Hint
(3)
Solution
(1)
(2) The right-hand side is smooth, so a unique local solution exists. By (1),
(3)
(4) The Jacobian is
Paper A, Problem 3A sector contour
For an integer
Hint
(2) Only one zero of
Solution
(1)
(2) The zeros of
(3)
(4) Let
Paper A, Problem 4Estimating the end of a uniform distribution
Hint
(1) Write the likelihood as a function of
Solution
(1)
(2)
(3)
(4) For
Paper A, Problem 5Stabbing intervals
You are given
Hint
(1) Sort by right endpoint. When you reach an interval with no point in it, where should its point go so that it helps as many later intervals as possible? Then look at the intervals that caused a new point.
Solution
(1) Sort the intervals by right endpoint. Go through them in that order, keeping the last chosen point
Every interval is stabbed: when it is reached, either a new point is placed at its right end, or
(2) Sorting takes
(3) If
(4) Sort by right endpoint,
Paper B
Linear algebra, optimization, differential equations, probability, algorithms.
Paper B, Problem 1Schur complements
Let
Hint
(1) Find an invertible block upper-triangular
Solution
(1) Let
(2) The case
(3) By (2), the epigraph
(4) Let
Paper B, Problem 2Projection onto the simplex
Let
Hint
(2) Write the KKT conditions with a multiplier
Solution
(1)
(2) The constraints are linear, so the KKT conditions are necessary and sufficient:
Algorithm: sort
(3) Let
(4) Let
Paper B, Problem 3Gradient flow of a strongly convex function
Let
Hint
(2) Minimize both sides of the strong convexity inequality over
Solution
(1) By the chain rule,
(2) The right-hand side of the inequality is minimized over
(3) Let
(4) Adding the strong convexity inequality to the same inequality with
Paper B, Problem 4The coupon collector
Each draw gives one of
Hint
(1) Split
Solution
(1) Let
(2) The
(3) Chebyshev's inequality with (1) and (2).
(4)
Paper B, Problem 5Two-colouring a graph
Let
Hint
(2) Breadth-first search from each uncoloured vertex, colouring by the parity of the distance. (3) If an edge joins two vertices at the same BFS level, follow both BFS tree paths back to where they meet.
Solution
(1) Along a cycle
(2) For each vertex not yet coloured, run BFS from it, giving each vertex the colour
(3) If the colouring is valid,
(4)
Paper C
Linear algebra, analysis, differential equations, probability, algorithms.
Paper C, Problem 1The Schur product theorem and kernels
For
Hint
(2) Write
Solution
(1)
(2) By the spectral theorem,
(3) By (2) and induction, every entrywise power
(4)
Paper C, Problem 2Fourier series and Parseval
Use the conventions
Hint
(3)
Solution
(1)
(2)
(3)
(4)
Paper C, Problem 3The Lyapunov equation
A real
Hint
(2) The integrand is
Solution
(1)
(2)
(3) If
(4) Write
Paper C, Problem 4A Poisson count with a gamma prior
A rate
Hint
(1) Multiply prior by likelihood and recognise the shape. (3) Use
Solution
(1) The posterior density is proportional to
(2)
(3) The gamma prior has mean
(4) The posterior mean is
Paper C, Problem 5Longest increasing subsequences
Let
Hint
(2) Keep, for each length
Solution
(1)
(2) Maintain
(3) Let
(4) An increasing subsequence meets each decreasing subsequence in at most one element, so at least
The spectral theorem and SVD
Self-adjoint operators are diagonal in an orthonormal basis: perpendicular axes, real stretch factors. Every linear map, self-adjoint or not, is diagonal between two orthonormal bases, which is the singular value decomposition, and it is why every invertible map sends circles to ellipses.
The idea
Geometrically (Axler 7.99):
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Adjoint
- The operator that moves
from one side of an inner product to the other. In an orthonormal basis its matrix is the conjugate transpose. - Self-adjoint
- Describes an operator equal to its own partner on the other side of the inner product; for real matrices, symmetric. Its eigenvalues are real.
- Normal operator
- One that commutes with its adjoint. Over the complex numbers these are exactly the ones with an orthonormal basis of eigenvectors; rotations are examples that are not symmetric.
- Spectral theorem
- A guarantee that certain operators are completely described by perpendicular directions that they only stretch: over the reals, the symmetric ones; over the complex numbers, the ones that commute with their adjoint.
- Singular value decomposition
- Any linear map, even between different spaces, is a rotation, then a stretch along perpendicular axes, then another rotation.
- Singular values
- How much a linear map stretches along its principal directions: the lengths of the semi-axes of the ellipse (or ellipsoid) it makes from the unit circle (or ball).
Explore
Worked example
Find the singular values of the shear
Compute
. .Its eigenvalues?
Trace 3, determinant 1:
.Singular values, and a sanity check.
: the golden ratio and its reciprocal. Their product is , the area scale. The eigenvalues of are both 1, very different from the singular values: is not normal.
Check your understanding
For a self-adjoint operator, the singular values are
- the absolute values of its eigenvalues.
- its eigenvalues.Singular values are never negative.
Which matrices are normal?
- Rotations.
- The shear
. here.
The best rank-1 approximation of
.- the rank-1 piece with the smallest singular value.Keep the biggest, drop the rest.
Practice
Eigenvalues of self-adjoint operators are realAxler 7.12
Prove it, and prove eigenvectors for distinct eigenvalues are orthogonal.
Solution
Operator normAxler 7.85
Show
Solution
With
From Axler, Linear Algebra Done Right (4th ed., Springer, 2024; open access)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Exercise 7A.4Invariant subspaces and the adjoint
For
Hint
Use
Solution
Suppose
Conversely, if
Exercise 7E.1Zero singular values
Show
Hint
The singular values are the square roots of the eigenvalues of
Solution
If
Exercise 7E.3Eigenvalues 0, 0 but singular values 5, 0
Give
Hint
A nilpotent map with a large entry.
Solution
Symmetric matrices and the PSD cone
Four of the five Problem 1s are about real symmetric matrices. Almost every part yields to the same move: diagonalize the symmetric matrix with an orthogonal change of basis, and see what the question says about eigenvalues.
The idea
Change basis first. (Sylvester's theorem, H&J 2.4.4.1, is the general form:
Projection onto the PSD cone. With the inner product
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Positive semidefinite (PSD)
- A symmetric matrix that never produces a negative "energy": put the same vector on both sides and the answer is zero or more. Equivalently, all its eigenvalues are zero or positive. It is the matrix version of a non-negative number.
- Spectral theorem
- Every real symmetric matrix just stretches space along some perpendicular directions. Rotate to those directions and the matrix becomes diagonal, with the stretch factors (the eigenvalues) on the diagonal. Most exam parts get easy once you do that rotation first.
- Loewner order
- A way of saying one symmetric matrix is at least as big as another: their difference is PSD. Unlike numbers, two matrices often can't be compared at all, because each can be bigger in a different direction.
- Congruence
- Sandwiching a matrix between another matrix and its transpose, which is what happens to a quadratic form when you change variables. It keeps PSD matrices PSD and keeps the order between two matrices, so you can turn one of them into the identity first.
- PSD square root
- The only matrix with no negative eigenvalues that, multiplied by itself, gives back a given matrix of that kind: keep the same perpendicular directions and replace each stretch factor by its positive root.
- Operator monotone
- Describes a function that respects the matrix order: if one matrix is above another, applying the function to both keeps it that way. Square roots and logarithms do; squaring does not, which surprises most people.
- Orthogonal Procrustes
- Finding the rotation (or reflection) that best lines up one set of points with another, in the least-squares sense. The answer comes straight from a singular value decomposition.
Explore
Worked example
2025 P1(4): find
Why must
and fail to commute?If
they diagonalize in a common basis, and gives . So the counterexample needs tilted axes, as in the second preset above.Take
and . Check . with , which is PSD. is PSD. So .Compute
and decide. , , so with determinant . One eigenvalue is negative, so . Writing out the matrices and the determinant is a complete answer for a "false" part.
Check your understanding
If
The worked example above is a counterexample. need not even be symmetric when they don't commute.
or , . is singularThe same example gives .
What is the nearest PSD matrix to
That flips the sign. It is at distance 4, while clipping gives distance 2. Clipping only touches negative eigenvalues.
Practice: symmetric matrices
The past problems in this area, restated, then a set of exercises from Horn and Johnson, Matrix Analysis, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problems
Restated in our own words. Official statements: 2020, 2024, 2025, 2026.
2020 Problem 1The equation BC + CB = A
Hint
(1) Change to the eigenbasis of
Solution
(1) Write
(2) If
2024 Problem 1Orthogonal Procrustes
Let
A note on the wording
The English paper prints "min" in (2); the Japanese paper says 最大化 (max). Only max is right, as the solution shows. When something looks off, read the other version.
Hint
(1) Scale the columns. (2) Expand the square;
Solution
(1)
(2)
(3)
2025 Problem 1True or false for the Loewner order
For real symmetric
Hint
(5) Reduce to the case
Solution
(1) True.
(2) False.
(3) True. For any
(4) False. The worked example above, padded with zeros for
(5) True.
2026 Problem 1Projection onto the PSD cone
Hint
(2) In the eigenbasis of
Solution
(1)
(2) Write
(3) Let
(4) First, if
(i)⇒(ii): if
From Horn and Johnson, Matrix Analysis (2nd ed., Cambridge, 2013)
Numbers match the book, which works over
Problem 2.4.P13Sylvester's equation by eigenvalues (the engine of 2020 P1)
Let
Hint
Solution
For 2020 P1,
Problem 7.2.P26(a)A two-sided bound on tr AB
For PSD
Hint
Move the square root of
Solution
Problem 7.7.P6A bigger matrix has a bigger range
If
Hint
Compare null spaces, then take orthogonal complements.
Solution
If
Problem 7.7.P21(a, b)How much must A be scaled to dominate B?
Let
Hint
Congruence by
Solution
Problem 7.7.P44Inverses reverse the order, from the definition
If
Hint
Expand the square, use
Solution
Expanding,
Problem 7.7.P45One block matrix, two Schur complements
For
Hint
If
Solution
Differential equations: what never increases
The exam rarely asks you to solve a nonlinear equation outright. It asks what the solution does in the long run, and the answer comes from a quantity you can track: one that is conserved, one that only decreases, or a Fourier mode that decays at a known rate.
The idea
Gradient flows. The Allen–Cahn equation
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Equilibrium
- A state where nothing changes: start there and you stay there forever. You find these by setting the right-hand side of the equation to zero.
- Lyapunov function
- An "energy" you design so that it goes down along every solution and is lowest at a resting state. If you can find one, solutions must slide downhill toward that state, without ever solving the equation.
- Conserved quantity
- Something that stays exactly constant along every solution, like total energy without friction. The paths then lie on its level curves, so drawing those curves draws the trajectories.
- Blow-up
- When a solution reaches infinity after a finite time, rather than just growing forever. Comparing with a simpler equation you can solve, such as
, shows it happens. - Linearization
- Zooming in on a resting state until the equation looks linear, then reading the behaviour off the eigenvalues of the matrix of partial derivatives. It works except in borderline cases, such as eigenvalues on the imaginary axis.
- Fourier mode
- A simple wave shape that a linear equation with constant coefficients only stretches or shrinks, never distorts. Split the starting state into these waves and each one evolves on its own.
- Gradient flow
- Always moving in the direction in which some energy falls fastest, like a ball rolling downhill through thick syrup. The energy can then only go down.
Explore: an epidemic in the phase plane
Explore: phase separation
Worked example
2026 P3(3): start with
Find a conserved quantity.
, so . Check: has .Show the limits
, exist, with and .From (2),
, so strictly decreases and is bounded below: exists. decreases ( ) and is bounded below, so it has a limit and ; with converging (as the difference of convergent functions), . Finally , which stays bounded, so .Use
to locate .Let
, which decreases on and increases on . Conservation gives . If , then and increasing there gives , a contradiction. So always, and no such solution exists.In epidemic terms,
is the herd-immunity threshold ( ); the outbreak always overshoots it. Drag the starting point above to watch this.
Check your understanding
Along solutions of
, which is why in (2). , not zero in general.
Linearize
- When
- Always: the reaction term pushes away from 0Diffusion damps short waves at rate
, which can beat the reaction's rate 1. - Never: diffusion smooths everythingMode 0 (and other long waves) grow at rate
.
If
blows up at some . grows at least exponentially, but exists for all time.Compare with , whose solution blows up at 1.- Nothing without an upper bound on
.A lower bound is exactly what forces blow-up.
Practice: differential equations
The past problems in this area, restated, then a set of exercises from Strogatz, Nonlinear Dynamics and Chaos, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problems
Restated in our own words. Official statements: 2020, 2023, 2025, 2026.
2020 Problem 4Discrete heat equation on a ring
Hint
Solution
(1) Substituting,
(2) By orthogonality
(3) For
2023 Problem 2Stability of a Lotka–Volterra system
Hint
Use
Solution
(1)
(2)
(3) Take
2025 Problem 2Allen–Cahn and phase separation
(A):
Hint
(1) Differentiate under the integral and integrate
Solution
(1)
(2) Each term must solve (B):
(3)
(4)(i) Points to make: diffusion alone (B) mixes everything to the average, erasing structure. Reaction alone (C) pushes each point independently to a pure phase
2026 Problem 3An epidemic-type system
Hint
(2) Write
Solution
(1)
(2)
(3) No; see the worked example:
(4)
From Strogatz, Nonlinear Dynamics and Chaos (2nd ed., CRC Press)
Exercise numbers match the book. Each is restated in our own words; the hints and solutions are written for this page.
Exercise 6.5.6The epidemic model in the phase plane (2026 P3 with general rates)
Healthy
Hint
(c) Form
Solution
(a)
(b)
(c)
(d) Every trajectory in the open quadrant ends on the line of fixed points at some
(e)
Exercise 2.5.2Blow-up without an exact solution
Show that every solution of
Hint
Don't solve it. Compare with
Solution
Since
Exercise 6.4.1Two competing species
For
Hint
Look at
Solution
Fixed points:
Globally, for
Exercise 7.2.10A Lyapunov function rules out cycles
Show that
Solution
Exercise 7.2.11When is a quadratic form a valid Lyapunov candidate?
Show that
Solution
If
Optimization and acceleration
Convergence proofs for first-order methods follow one template: write down an energy that mixes the gap
The idea
The continuous-time picture. Letting the step size shrink, Nesterov's method tracks
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Convex function
- A function whose graph lies above every one of its tangent lines or planes. So any local minimum is the global one, and the tangent at any point gives a guaranteed lower bound.
- L-smooth
- Describes a function whose slope can't change too abruptly: the gradient moves at most a fixed multiple of how far the point moves. It tells you how big a downhill step is safe.
- Gradient descent
- Repeatedly take a small step in the direction where the function decreases fastest. On smooth convex problems the gap to the best value shrinks like one over the number of steps.
- Nesterov acceleration
- Downhill steps with momentum: before each step, keep moving a little in the direction you were already going. It improves the guaranteed rate from
to , the best possible using only gradients. - Proximal operator
- A compromise step for a function that may have corners: find the point that keeps the function small while staying close to where you are. For the absolute value it shrinks numbers toward zero; for a set it gives the nearest point of the set.
- LP duality
- Every linear program that maximizes has a partner that minimizes, and each feasible point of the partner gives an upper bound on the original. At the optimum the two values meet, so a pair of solutions with equal values proves both are optimal.
- Complementary slackness
- At the optimum of a linear program and its partner, every constraint with room to spare has price zero, and every positive price belongs to a constraint with no room to spare. It is the quick test of whether a candidate pair is optimal.
Explore
Worked example
2024 P2(1): show
Differentiate each term of
. .Substitute the dynamics.
and . The terms cancel: .Finish with convexity.
The bracket is
by . So , and : take .
Check your understanding
In the proof above, which property of
- Convexity, in the form
- Strong convexityNot assumed; with it you would get a linear rate.
- A Lipschitz gradientNeeded for discrete step-size choices in general, but not in the continuous-time argument.
What is the guaranteed rate of plain gradient descent (step
That is the accelerated rate.- Linear,
Only with strong convexity, and then the rate depends on the condition number: compare large and small κ in the figure.
What is
That is the prox of . That is projection onto , the prox of its indicator.
Practice: optimization
The past problems in this area, restated, then a set of exercises from Boyd and Vandenberghe, Convex Optimization, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problem
Restated in our own words. Official statement: 2024. 2024 P1 and 2026 P1 are optimization problems too; they are worked under symmetric matrices.
2024 Problem 2Accelerated gradient as a differential equation
Hint
Write
Solution
(1) The worked example.
(2) With
Now
- Convexity between
and : , so . - The
update: .
Adding, the
(3)
Fresh practiceThe dual of a transportation LP
Supplies
Solution
Primal: minimize
From Boyd and Vandenberghe, Convex Optimization (Cambridge, 2004)
Exercise numbers match the book (freely available from the authors). Each is restated in our own words; the hints and solutions are written for this page. The book covers gradient descent (§9.3) but not acceleration, which is why 2024 P2 is worth working on its own terms.
Exercise 8.1Projections onto closed convex sets are unique
Let
Hint
Existence: compactness. Uniqueness: the midpoint of two nearest points, and the parallelogram law.
Solution
Pick any
Exercise 8.3 (a, b)Projections onto the orthant and the PSD cone
(a) Show that the Euclidean projection of
Hint
(a) The problem separates coordinate by coordinate. (b) The Frobenius norm doesn't change under
Solution
(a)
Exercise 2.28The PSD cone in coordinates
Describe
Hint
A symmetric matrix is PSD if and only if all principal minors are non-negative (leading ones are not enough for semidefiniteness).
Solution
Exercise 5.4The LP dual as the best bound from a single inequality
For the LP
Solution
(a) Minimizing a linear function over a half-space is
Exercise 5.5The dual of a general LP
Find the dual function and dual problem of
Solution
Uniform convergence
Pointwise limits of continuous functions can be discontinuous. Uniform convergence is the fix, and it is just convergence in the metric
The idea
In the language of the story:
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Pointwise convergence
- At each single input the values settle down eventually, but some inputs may take far longer than others.
- Uniform convergence
- The whole graph settles down together: from some step on, every input is within
of the limit at once. - Sup norm
- The largest gap between two functions anywhere on the domain. Convergence in it is exactly the "whole graph settles down together" kind.
- Uniform limit theorem
- If continuous functions converge with the whole graph settling down together, the limit is continuous too. Limits taken one point at a time can break continuity, as
on shows. - Weierstrass approximation theorem
- Any continuous function on a closed interval can be matched as closely as you like, everywhere at once, by a polynomial.
- Complete metric space
- A space with no holes: every sequence whose terms bunch up together has a limit inside the space.
Explore
Worked example
Prove Rudin 7.12: a uniform limit of continuous functions is continuous.
Fix
and . Which do you use?One with
. This is where uniformity matters: the same is good at and at every nearby .Now use continuity of that
at .Pick
with when . Then . This " argument" is the template for many proofs in analysis.
Examples
Check your understanding
- Yes, since each
is continuous.Continuity of the doesn't force uniform convergence. - No: a uniform limit of continuous functions would be continuous.
- tends to 0.Look at
. - equals
for every .
Practice
Exercise 7.1The Weierstrass M-test (Rudin 7.10)
Show that
Solution
Exercise 7.2Limits and integrals: when can you swap them?
For
Solution
From Rudin, Principles of Mathematical Analysis (3rd ed., McGraw–Hill, 1976)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Rudin 7.1Uniform limits of bounded functions
Prove that every uniformly convergent sequence of bounded functions is uniformly bounded.
Hint
Use one
Solution
Let
Rudin 7.2Sums and products
If
Hint
For the product, add and subtract
Solution
Sums:
Products: by Rudin 7.1 there is
Without boundedness it fails: on
Rudin 7.9Uniform convergence and moving points
Let
Hint
Split
Solution
The converse fails. Take
Analysis: approximation and integrals
The analysis problems are about numerical mathematics seen through classical tools: how fast a quadrature rule converges and why, what fast approximation says about smoothness, and how a change of variables turns a question about densities into one about convex functions.
The idea
Parametrize the circle. On
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Residue theorem
- To integrate a complex function around a closed loop, you don't need the whole loop: add up one number for each pole inside and multiply by
. It turns many hard real integrals into a little algebra. - Residue
- The single number that summarizes a function's behaviour at a pole: the coefficient of
in its expansion there. At a simple pole of it equals at that point. - Trapezoid rule
- Approximating an integral by averaging the function at equally spaced points. For smooth periodic functions it is astonishingly accurate: the error shrinks exponentially with the number of points.
- Trigonometric polynomial
- A finite sum of sines and cosines up to some highest frequency: the periodic counterpart of an ordinary polynomial.
- Bernstein's inequality
- A finite sum of waves can't wiggle faster than its highest frequency allows: its derivative is at most the degree times its largest value. That is why approximating a function quickly by such sums forces it to be smooth.
- Quantile function
- The inverse of the distribution function: for each fraction
, the value below which that fraction of the probability lies. The median is its value at one half, and the mean is its average over . - Exchanging limits
- Swapping the order of two limits, a limit and a sum, or a limit and an integral. It is often allowed, but it needs a reason (such as uniform convergence), and the exam expects you to give it.
Explore
Worked example
2023 P3(4): show the constant
Which simple
does the -point rule get completely wrong? . Its integral over the circle is , but at every node , so . The error is .Compute the ratio for this
. , so . Hence the sup is at least for every .Combine with the upper bound.
From (3), the quantity is at most
. With the lower bound , the limsup (in fact the limit) is .
Check your understanding
The
is not a nonzero multiple of is the worst case: error .- alwaysThe nodes can't tell
from the constant 1.
If
is continuously differentiable is analyticAnalyticity needs geometric rates , not polynomial ones.- Nothing beyond continuityBernstein's inequality converts the approximation rate into control of derivatives.
A density is strictly decreasing on
- mean > median
- mean < medianThe long tail is on the right.
- It depends on the density2025 P3(3) proves the strict inequality in general.
Practice: analysis
The past problems in this area, restated, then a set of exercises from Stein and Shakarchi, Complex Analysis, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problems
Restated in our own words. Official statements: 2023, 2024, 2025.
2023 Problem 1A log-average dissimilarity
For finite real sequences
Hint
(2)
Solution
(1)
(2) Write
(3) As
(4)
2023 Problem 3The trapezoid rule for analytic functions
For
Hint
(3) Express both
Solution
(1) With
(2) The poles are the zeros of
(3) Fix
(4) The worked example.
2024 Problem 3Fast approximation implies differentiability
Solution
(1)
(2)
(3)
2025 Problem 3Mean versus median
Solution
(1) The three pieces have mass
(2)
(3)
(4) Contrapositive. Suppose
From Stein and Shakarchi, Complex Analysis (Princeton Lectures in Analysis II, 2003)
Exercise numbers are from the exercises at the end of Chapter 3. Each is restated in our own words; the hints and solutions are written for this page.
Exercise 3.8An integral over the circle by residues
Show that
Hint
Substitute
Solution
For
Connection to the figure above: the integrand is analytic in the annulus
Exercise 3.7Differentiate the previous answer
Show that
Hint
A pole of order 2 works (Theorem 1.4), but there is a shortcut through Exercise 3.8.
Solution
By Exercise 3.8 with
Exercise 3.1The poles of 1/sin πz
Using
Solution
Exercise 3.11An integral that vanishes by the mean-value property
Show that
Hint
Solution
For
Discrete random variables
A random variable's law says how likely each value is; its mean and variance summarise where the values sit and how far they spread. Draw samples below and watch the histogram settle onto the law and the running average settle onto the mean.
The idea
Three laws that come up again and again:
- Binomial
: the number of successes in independent trials, ; mean , variance . - Poisson
: for ; mean and variance both . It is the limit of as : many trials, each rarely a success. - Geometric: the number of the trial on which the first success happens,
for ; mean , variance .
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Random variable
- A number determined by the outcome of a random experiment, such as the number of heads in ten coin flips.
- Probability mass function
- For a variable with countably many values, the list of possible values with the chance of each.
- Cumulative distribution function
- For each number
, the chance that the variable is at most . It climbs from 0 to 1. - Expectation
- The long-run average value: each possible value weighted by its chance. The one for a sum is the sum of the individual ones, always.
- Variance
- The average squared distance from the mean: how spread out the values are. For independent variables it adds up.
- Binomial distribution
- The number of successes in a fixed number of independent tries, each with the same chance of success.
- Poisson distribution
- The number of rare events in a fixed window when there are many chances, each unlikely. Its mean and variance are equal.
- Geometric distribution
- The number of tries up to and including the first success.
Explore
Worked example
A batch contains 200 chips, each defective with probability 0.01 independently of the others. Let
What is the law of
? Find . , so .Approximate the same probability with a Poisson law. Which
?Match the means:
. Then , within about 1% of the exact value.Estimate
both ways.Use the complement. Exactly:
. Poisson: . They agree to four decimal places.Compare the variances. Why is the Poisson variance a little larger?
The binomial variance is
; the Poisson variance is . The factor is the only difference, and it tends to 1 as with fixed. That is the regime in which the Poisson approximation is good.
Check your understanding
Adding the two counts adds the numbers of trials, not the success probabilities. can be as large as 20.- It is not binomial.Think of
and as counting successes in two separate runs of independent trials.
In the simulator, the running mean wanders around
- 4That would be true of the variance of
, not its standard deviation. - 2
- It doesn't shrink; each draw is as random as the last.Each draw is, but the average of many draws is much less variable.
- They are independent, because they are uncorrelated.Uncorrelated only says
. Compare with . - They are uncorrelated but not independent.
- They are correlated, since
is a function of .Compute .
Practice
Mean of the geometric lawDifferentiating a series
Show that if
Hint
Differentiate
Solution
Differentiating gives
Thinning a Poisson countTotal probability with random variables
The number of emails arriving in an hour is
Hint
Given
Solution
where
From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Exercise 5.22Uncorrelated but dependent
Hint
Compute
Solution
The joint law puts mass
But
Exercise 5.23Defective items
Fifteen items are each defective with probability 0.3, independently. Find the probability that (a) exactly three are defective; (b) more than four are; (c) more than 11 are not defective; (d) fewer than five are defective; (e) between two and six (inclusive) are defective.
Hint
Solution
(a)
(b)
(c) More than 11 good means at most 3 defective:
(d)
(e)
Exercise 5.36Poisson plus Poisson
If
Hint
Convolve, and recognise the binomial theorem.
Solution
Densities and the central limit theorem
Add up many independent random quantities and, whatever their own shape, the sum looks normal. That is the central limit theorem, and it is why the bell curve is everywhere. Pick a lopsided distribution below, add
The idea
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Probability density
- A curve whose area over an interval is the chance of landing in that interval. Its height is not itself a probability, and can be bigger than 1.
- Chebyshev's inequality
- A variable is rarely many standard deviations from its mean: the chance of being at least
away is at most the variance divided by . - Weak law of large numbers
- The average of many independent copies of a variable gets close to its true mean, with probability tending to one.
- Normal distribution
- The bell curve, fixed by its centre and its spread. Subtracting the centre and dividing by the spread turns any one of them into the standard one.
- Central limit theorem
- Add up many independent copies of almost any variable, then centre and rescale the total: its distribution approaches the bell curve, whatever the original shape.
- Differential entropy
- A measure of how spread out or unpredictable a continuous distribution is. Among distributions with a given variance the bell curve has the most; unlike the discrete version, it can be negative.
Explore
Worked example
A fair die is rolled 100 times. Estimate the probability that the total is at least 380.
Find the mean and variance of a single roll.
, and , so .Find the mean and standard deviation of the total
. and , so the standard deviation is about .Standardise and use the normal approximation.
takes whole-number values, so " " is the same as " " (a continuity correction). ThenThe exact value, from convolving the die's law 100 times, is 0.0420.
What does Chebyshev's inequality give? Why is it so much weaker?
, and that bounds both tails together. Chebyshev uses only the variance, so it must hold for every distribution with that variance, including very spread-out ones. The CLT uses the fact that is a sum of many independent pieces.
Check your understanding
- It is approximately
. - It is approximately
.Those are the mean and variance of one term. For a sum of independent terms, means add and variances add. - It is approximately uniform on
.Run the simulator with the uniform law and : the sum is already a triangle, not flat.
Can a probability density function take values bigger than 1?
- Yes
- No, because
is a probability. is a probability per unit length. Only its integrals are probabilities. - Only at finitely many points.The uniform density on
is 2 on the whole interval.
What is the entropy
bit- It can't be negative, so 0.That is true for discrete entropy, where each
. A density can exceed 1, which makes negative. - 1 bitCheck the sign:
and .
Practice
Four hundred tossesNormal approximation to the binomial
A fair coin is tossed 400 times. Estimate the probability that the number of heads is between 190 and 210 inclusive.
Solution
The count is
From uniform to exponentialThe distribution-function method
Let
Hint
Compute
Solution
For
From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Exercise 8.19Chebyshev's estimate
Hint
Without more information, Chebyshev is the tool.
Solution
Exercise 8.34Heads between 45% and 55%
A coin lands heads with probability 0.45. Estimate the probability that in 25 throws the proportion of heads is between 45% and 55%.
Hint
Between
Solution
With the continuity correction,
Exercise 8.37Entropy of the exponential distribution
Find the entropy of
Hint
Solution
Probability and statistics
The probability problems are built from a small kit: transform a variable and differentiate its distribution function, use memorylessness, write a likelihood and show it has one peak, compute a transform, or couple two variables on one probability space. Know each tool well enough to use it without hesitating.
The idea
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Distribution function method
- To find the law of a new variable built from an old one, ask for the probability that it is at most
, rewrite that in terms of the old variable, then differentiate. - Memorylessness
- Having already waited tells you nothing about how much longer you will wait: the remaining time has the same distribution as the original. The exponential is the only continuous distribution like this.
- Poisson process
- Arrivals at random times, independently, at a constant average rate. The gaps between arrivals are exponential, and the number in any time window has a Poisson distribution.
- Maximum likelihood
- Choose the parameter value that makes the data you actually saw most probable: write that probability as a function of the parameter and maximize it.
- Censored observation
- A data point you only know partly, such as "the machine was still working when we stopped watching". It contributes the probability of what you saw, not a density.
- Characteristic function
- The average of
: a transform that turns sums of independent variables into products. If these transforms converge, the distributions converge. - Coupling
- Building two random variables from the same source of randomness so that they agree as often as possible. The chance they disagree then bounds how different their distributions are.
Explore
Worked example
2024 P4(4):
Find the distribution of
. means . Conditioning on (Gamma density) and using independence: . So (and directly).Maximize the likelihood.
, . For the unique maximizer is . For , decreases on and the supremum is approached at ; the formula is the natural boundary value, and worth a sentence in an answer.Mean and variance.
(unbiased) and .
Check your understanding
That is the minimum. That is the sum.
- It has the same distribution as
for every . - It tends to 0 by the law of large numbers.
, and the scaling is , not . - It becomes normal after centring.The variance is infinite; the central limit theorem doesn't apply.
Le Cam's inequality bounds
That is what you get from . The coupling does better: about per trial. That is the Berry–Esseen rate for the normal approximation.
Practice: probability and statistics
The past problems in this area, restated, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problems
Restated in our own words. Official statements: 2020, 2023, 2024, 2025.
2020 Problem 2Lifetimes censored at birth
Hint
(3) Given which
Solution
(1)
(2)
(3) Choose the censored set (
(4) With
2023 Problem 4The reciprocal of a squared normal
Hint
(2) Write
Solution
(1)
(2) Differentiating under the integral (dominated for
(3) Solving with
(4) The characteristic function of the scaled sum is
2024 Problem 4Exponential clocks and a Poisson count
Solution
(1)
(2)
(3) By induction on convolutions,
(4) The worked example:
2025 Problem 4Poisson approximation by coupling
(1) Show the sum of independent Poisson(
Solution
(1)
(2) Let
(3)
(4) Build
Concentration of sums
A sum of
The idea
All of these come from one move: apply Markov to
a Gaussian tail for moderate
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Hoeffding's inequality
- A sum of independent bounded variables rarely strays far from its mean: the chance of straying by
falls off like , scaled by the ranges of the variables. - Chernoff bound
- A sharper tail bound for sums of independent yes-or-no variables, especially when successes are rare: it behaves like a Poisson tail.
- Subgaussian
- Describes a random variable whose tails die off at least as fast as a normal distribution's. Bounded variables and normal ones are examples.
- ψ₂ norm
- A single number measuring the spread of a variable with normal-like tails: the scale at which its tails look like a normal's.
- Subexponential
- Describes a variable whose tails may be heavier than a normal's but still fall off exponentially, like the square of a normal variable.
- Bernstein's inequality
- A tail bound for sums of independent variables with exponential tails: it looks like a normal tail for moderate deviations and only exponential far out.
Explore
Worked example
An A/B test estimates a click rate
Use Chebyshev, knowing only
. . Setting this to gives .Use Hoeffding (each click indicator lies in
).Two-sided:
. We need , i.e. . Sixty-five times fewer users.Suppose you also know
. Bernstein's inequality for variables with reads . What does it give?Here
and , so the exponent is . We need it to be at least :Another factor of 11. Hoeffding pays for the worst-case variance
; Bernstein pays only for the actual variance.How does each answer scale with the failure probability
?Chebyshev needs
; Hoeffding and Bernstein need . Asking for instead of multiplies the Chebyshev answer by 1000, but the Hoeffding answer by less than 2.
Check your understanding
Which of these random variables is not subgaussian?
- A random variable with
almost surelyBounded variables are subgaussian: , which is at most 2 for large . The Gaussian is the model subgaussian variable, with a constant times .- An exponential random variable
- A sum of 100 independent random signsThat sum is bounded by 100, and better, it has
norm of order .
- It only uses that each term lies in
, not that each term is almost always 0. - Hoeffding needs identically distributed terms.It doesn't, and these terms are identically distributed anyway.
- Hoeffding needs symmetric terms.The version for bounded variables needs only independence and the ranges.
- Hoeffding only holds for large
.It holds for every . It is a true bound here, just a useless one.
Let
- For
- For
Compare with : which is smaller when is large? - For all
Then would be subgaussian, but alone already decays like . - Only for
is the typical size of the sum, but the Gaussian regime extends much further.
Practice
Two subgaussian normsComputing ψ₂ from the definition
(a) Show that if
Hint
For (b),
Solution
(a)
From MGFs to a tail boundThe exponential moment method
Suppose
Solution
For
From Vershynin, High-Dimensional Probability (2nd ed., Cambridge, pre-publication version, 2025)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Exercise 2.13Chernoff for Poisson
Let
Hint
Solution
(a) For
(b) For
(c) At
(d)
Exercise 2.25Distributions that aren't subgaussian
Explain why the exponential, Poisson, geometric, chi-squared, Gamma, Cauchy and Pareto distributions are not subgaussian.
Hint
Subgaussian means
Solution
For each, find a lower bound on the tail that decays slower than any
- Exponential:
. - Geometric:
, again exponential. - Poisson:
, which is . - Chi-squared with
degrees of freedom: , and . - Gamma
: density , tail of order . - Cauchy:
; it doesn't even have a mean. - Pareto: polynomial tail
.
Since
Lipschitz concentration and Johnson–Lindenstrauss
Any Lipschitz function of a high-dimensional Gaussian (or of a uniform point on the sphere) is nearly constant, whether or not it is a sum. One consequence:
The idea
The target dimension depends on
The dimension enters only as the factor
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Lipschitz function
- A function that can't change faster than a fixed rate: moving the input by a distance
moves the output by at most a fixed multiple of . - Gaussian concentration
- Any gently varying function of many independent normal variables is almost constant: it stays near its average with very high probability.
- Concentration on the sphere
- For a random point on a high-dimensional sphere, every gently varying function is almost constant, even though the coordinates are not independent. The cause is the sphere's geometry.
- Random projection
- Multiplying data by a random matrix to get a shorter version of each point. Done right, it keeps distances nearly the same without looking at the data first.
- Johnson–Lindenstrauss lemma
- Any set of points can be squashed by a random linear map into a number of dimensions that grows only like the logarithm of the number of points, with every distance nearly preserved.
- Matrix Bernstein inequality
- A tail bound for sums of independent random matrices: the size of the total concentrates, and the dimension costs only a logarithmic factor.
Explore
Worked example
Let
Bound
. (Hint: .)By Jensen,
. So , and gives . For that is about 5.26.Show that
is 1-Lipschitz for the Euclidean norm.If the max of
is at , then . Swap the roles of and for the other direction.What does Gaussian concentration give?
for every . The maximum of a million Gaussians grows like , but it fluctuates by regardless of . (Its true fluctuations are even smaller, but the theorem needs no work to give .) Independence was never used in step 3; only the Lipschitz property was.The same reasoning applies to
as a function of the Gaussian entries of . Compute its Lipschitz constant and explain why JL needs .With
a unit vector and , , and is 1-Lipschitz in the Frobenius norm of . So deviates from its mean (which is close to 1) by more than with probability , roughly. For all pairs to succeed we need , i.e. .
Check your understanding
In the Johnson–Lindenstrauss lemma, what does the target dimension
- Only on the number of points
and the accuracy - On the ambient dimension
The proof handles one difference vector at a time, and the law of is the same in every dimension. - On how the points are arrangedThe projection is chosen without looking at the data. Switch data sets in the explorer.
- Only on
More points mean more pairs that could fail; the union bound charges .
stays within of with high probability. is approximately Gaussian.Concentration controls the size of fluctuations, not their shape. Think of . is bounded independently of . is 1-Lipschitz and . .The variance is at most of order 1 (in fact at most 1), but it can be much smaller, e.g. 0 for a constant .
Fix the target dimension
- Like
- It stays the same.Each new pair is another chance for an unlucky ratio.
- Like
That would follow from Chebyshev-type tails. The per-pair tail is Gaussian. - Like
The number of pairs grows like , but the distortion only like the square root of its logarithm.
Practice
Sizing a projectionUnion bound arithmetic
Suppose that for each fixed difference vector, a random projection to
Solution
There are fewer than
The norm of a Gaussian imageLipschitz constant of x ↦ ‖Ax‖
Let
Hint
Solution
From Vershynin, High-Dimensional Probability (2nd ed., Cambridge, pre-publication version, 2025)
Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.
Exercise 5.9The maximum of Gaussians concentrates
(a) For independent
Hint
Gaussian concentration for Lipschitz functions. Write jointly normal variables as
Solution
(a)
(b) Write
Exercise 5.14Johnson–Lindenstrauss with subgaussian matrices
Let
Hint
For a fixed unit vector
Solution
Fix a unit vector
Apply this to
A matrix with i.i.d.
Concentration and random walks
Two 2026 problems come from modern probability: the Johnson–Lindenstrauss lemma, proved with a Chernoff bound, and fixation in the Moran process, solved by first-step analysis. Both are standard theorems taught as a sequence of short steps, which is how the exam presents them.
The idea
For more, the High-Dimensional Probability and Markov Chains pages go further in each direction.
Key terms in plain words
The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.
- Chernoff's method
- To bound the chance that a sum is large: exponentiate it, apply Markov's inequality, and use independence to split the average into a product. Then choose the free parameter to make the bound small.
- Markov's inequality
- A non-negative quantity can't often be much bigger than its average: the chance that it exceeds
is at most its average divided by . - Moment generating function
- The average of
. It packs every moment of into one function, and for independent variables the one for a sum is the product of the individual ones. - Chi-squared distribution
- The law of a sum of squares of independent standard normal variables, for example the square of the length of a random Gaussian vector.
- Union bound
- The chance that at least one of several bad events happens is at most the sum of their chances. Crude, but it is how a bound for one pair of points becomes a bound for every pair.
- First-step analysis
- To find a probability or an expected time for a random process, condition on what happens at the very first step. That gives an equation linking neighbouring starting points, which you then solve.
- Absorbing state
- A state a process can enter but never leave, like going broke in a gambling game.
Explore: random projection
Explore: the Moran process
Worked example
2026 P2(3): for
Apply (1) and (2) of the problem.
is a sum of independent terms, so and for .Use the hint on
. Where does it apply?With
, i.e. : . So the bound is at most .Choose
.The exponent is minimized at
, which is because . Its value is . That is where the condition comes from.
Check your understanding
In Johnson–Lindenstrauss, how must the target dimension
- Like
- Like
The union bound over pairs only costs a logarithm, since each pair fails with probability . - Like the original dimension
doesn't appear at all.
In the neutral Moran process (
Larger starting groups are more likely to win. That would be right if each A lineage independently had probability ; they aren't independent.
A single mutant (
That is the neutral answer; selection helps a lot.- Close to 1Early on there is only one mutant, and it is easily lost by chance.
Practice: concentration and random walks
The past problems in this area, restated, each with a hint and a full solution. Try them after working through the toolkit module.
Problems
Past problems
Restated in our own words. Official statement: 2026.
2026 Problem 2The Johnson–Lindenstrauss lemma
(1) For
Solution
(1)
(2)
(3)
(4) For a pair with
2026 Problem 4Fixation in the Moran process
A population of
Hint
(5) With
Solution
(1) Let
(2) First-step analysis:
(3) The differences satisfy
(4)