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.

InteractivePast papers 2020–2026, 2027 application guide

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 written exam (専門科目「数理情報学」). Three hours, 10:00–13:00. Five problems, of which you answer any three, one answer sheet per problem (you may use the back). The booklet has every problem in both Japanese and English; answer in either. Only a pencil, eraser and a plain watch are allowed.
Where it sits (2027 guide). Document screening first, with a two-page essay on why you want to join and one research theme you care about: its background, recent progress, what you would hope to find and why it matters. Those who pass take the school-wide general mathematics exam, then this specialized exam, then an online oral exam. English is assessed by TOEFL. There is no winter master's exam.
Dates. For 2027 entry the specialized exam was on 24 August 2026 and the oral on 27 August. For 2028 entry, expect the same late-August pattern in 2027; the guide for 2027 entry appeared in April 2026. Check the current guide before planning around any date here.

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.

TopicIn this guideGo deeper on this site
Symmetric matricesusually Problem 1The spectral theorem and SVD
Symmetric matrices and the PSD cone
Practice
Linear Algebra: eigenvalues, inner products and projection, Jordan form
Gradient Descent: quadratics and eigen-directions
Differential equationsProblems 2–3, rotatingWhat never increases
Practice
Gradient Flows: curves of maximal slope, λ-convexity and contraction
Markov Chains: generators, the forward equation
OptimizationProblems 2–3, rotatingOptimization and acceleration
Practice
Gradient Descent: directional derivatives and momentum, convexity and convergence rates
Information Theory: Lagrange multipliers (maximum entropy)
AnalysisProblems 2–3, rotatingUniform convergence
Approximation and integrals
Practice
Real Analysis: sequences and series, compactness, the mean value theorem, integrals
Fourier Analysis: Fourier series, decay and smoothness
Probability and statisticsusually Problem 4Discrete random variables
Densities and the CLT
Probability and statistics
Practice
Probability: counting, Bayes, random vectors, Markov chains
Markov Chains: absorption and hitting
Concentration and random walkswith probabilityConcentration of sums
Johnson–Lindenstrauss
Concentration and random walks
Practice
High-Dimensional Probability: tail bounds, random vectors, random matrices
Bandits, MDPs and RL: how fast an empirical mean settles
AlgorithmsProblem 5, every yearDesign and proof
Practice
No subject page on this site yet; the toolkit here follows Kleinberg and Tardos.
Algebra and number representationsoccasionalAlgebra and number representations
Practice
Computer Systems: integers, floating point

Explore

Highlight an area
Pick a problem to see what it tests and where it is worked in this guide.

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.

    3:00:00
    The clock runs in this tab only and nothing is saved.

    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.

    1. 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.

    2. 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.

    3. 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).

    4. 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.

    5. 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.

    6. 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.

    7. 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.

    正定値 / 半正定値positive definite / semidefinite
    固有値・固有ベクトルeigenvalue, eigenvector
    特異値分解singular value decomposition
    一意に定まるis uniquely determined
    必要十分条件necessary and sufficient condition
    同値であることを示せshow that … are equivalent
    反例を与えよgive a counterexample
    単調非増加monotonically non-increasing
    狭義単調減少strictly decreasing
    漸近挙動asymptotic behaviour
    確率密度関数probability density function
    期待値・分散expectation, variance
    最尤推定量maximum likelihood estimator
    分布収束(法則収束)convergence in distribution
    特性関数・モーメント母関数characteristic / moment generating function
    正則関数・留数holomorphic function, residue
    一様収束uniform convergence
    多項式時間・線形時間polynomial time, linear time
    帰着reduction
    最短経路問題shortest path problem
    非巡回向き付けacyclic orientation
    イデアル・剰余環・同型ideal, quotient ring, isomorphic
    相分離phase separation
    概略図を示せsketch a conceptual picture

    Check your understanding

    Which problem slot has been an algorithms problem on every paper from 2020 to 2026?

    1. Problem 1Problem 1 is usually linear algebra (four of five papers).
    2. Problem 3The middle slots rotate between differential equations, analysis, optimization and algebra.
    3. Problem 5
    2020 isotonic regression, 2023 non-adjacent form, 2024 makespan scheduling, 2025 tropical matrix powers, 2026 acyclic orientations. Each asks for an algorithm with a running-time guarantee and a correctness proof.

    You cannot prove part (2) but can see how (3) follows from it. What should you write?

    1. Skip (3) as well, since it depends on (2).Graders mark each part. A correct (3) that cites (2) earns its marks.
    2. Answer (3), stating clearly that you are using the result of (2).
    3. Prove a weaker version of (2) and stop.Worth doing if you have time, but don't let it cost you (3).
    The parts are designed as a staircase, and the later parts are often the more valuable ones.

    The 2027 guide says the written exam draws on algebraic, analytic, geometric, discrete, probabilistic, statistical and algorithmic methods. How many problems must you answer?

    1. All five.Five are set, but you choose.
    2. Three of the five.
    3. One from each area.There is no per-area requirement.
    Answer three of five in three hours. That freedom is why a breadth-first plan works: be solid in the three or four areas that appear every year, so a bad draw in one never forces you into a problem you can't finish.

    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.
    PracticeThree papers written for this page in the style of 2020–2026

    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.

    3:00:00
    The clock runs in this tab only and nothing is saved.

    Paper A

    Linear algebra, differential equations, analysis, probability, algorithms.

    Paper A, Problem 1Sums of the largest eigenvalues

    Let A be a real symmetric n×n matrix with eigenvalues λ1≥λ2≥⋯≥λn, and let 1≤k≤n. Write Uk for the set of real n×k matrices U with U⊤U=Ik. (1) Show that max‖x‖=1x⊤Ax=λ1. (2) Show that tr(U⊤AU)≤λ1+⋯+λk for every U∈Uk. (3) Show that the bound in (2) is attained. (4) Let sk(A)=λ1(A)+⋯+λk(A). Show that sk(A+B)≤sk(A)+sk(B) for symmetric A,B, and that sk is a convex function on symmetric matrices.

    Hint

    (2) Write A=QΛQ⊤ and V=Q⊤U. Then tr(U⊤AU)=∑iλiwi, where wi is the squared length of row i of V. Find the range of each wi and their sum. (4) Use (2) and (3) to write sk as a maximum.

    Solution

    (1) Let A=QΛQ⊤ with Q orthogonal. With y=Q⊤x, ‖y‖=1 and x⊤Ax=∑iλiyi2≤λ1∑iyi2=λ1. Equality holds for x the first column of Q.

    (2) V=Q⊤U also satisfies V⊤V=Ik, and tr(U⊤AU)=tr(V⊤ΛV)=∑iλi∑jVij2=∑iλiwi. Extend the columns of V to an orthogonal n×n matrix; row i of that matrix has length 1 and contains row i of V, so 0≤wi≤1. Also ∑iwi=‖V‖F2=tr(V⊤V)=k. Now

    ∑iλiwi−∑i≤kλi=∑i≤kλi(wi−1)+∑i>kλiwi≤λk∑i≤k(wi−1)+λk∑i>kwi=λk(∑iwi−k)=0,

    using wi−1≤0 with λi≥λk for i≤k, and wi≥0 with λi≤λk for i>k.

    (3) Take U to be the first k columns of Q. Then U⊤AU=diag(λ1,…,λk).

    (4) By (2) and (3), sk(A)=maxU∈Uktr(U⊤AU). Hence sk(A+B)=maxU(tr(U⊤AU)+tr(U⊤BU))≤sk(A)+sk(B). Since sk(tA)=tsk(A) for t≥0, for 0≤θ≤1 we get sk(θA+(1−θ)B)≤θsk(A)+(1−θ)sk(B). Equivalently: a maximum of functions that are linear in A is convex. For k=1 this says λmax is convex; for k=n, sn=tr is linear.

    Paper A, Problem 2A damped oscillator with cubic friction

    Consider x˙=y, y˙=−x−y3 with any starting point (x(0),y(0)). (1) Show that E=12(x2+y2) is non-increasing along solutions. (2) Show that every solution exists for all t≥0 and stays in the disc of radius 2E(0). (3) Show that (x(t),y(t))→(0,0) as t→∞. (4) Find the eigenvalues of the linearization at the origin, and explain why they alone do not decide (3).

    Hint

    (3) E(t) decreases to a limit c. Apply LaSalle's invariance principle: the limit points of the solution form an invariant set on which E˙=0. What does E˙=0 force, and what does invariance then force?

    Solution

    (1) E˙=xx˙+yy˙=xy+y(−x−y3)=−y4≤0.

    (2) The right-hand side is smooth, so a unique local solution exists. By (1), x2+y2≤2E(0) on its interval of existence, so the solution cannot leave a bounded set, and it extends to all t≥0.

    (3) E(t) is non-increasing and bounded below, so it has a limit c≥0. The solution is bounded, so its ω-limit set Ω is non-empty, compact and invariant under the flow, and E=c on Ω by continuity. A solution starting in Ω stays in Ω, where E is constant, so E˙=−y4=0 along it: y≡0. Then y˙=−x=0, so x≡0. Hence Ω={(0,0)}, c=0, and x2+y2=2E(t)→0. (This is LaSalle's invariance principle; quoting it and checking its hypotheses is enough.)

    (4) The Jacobian is (01−1−3y2), which is (01−10) at the origin, with eigenvalues ±i. Purely imaginary eigenvalues are the borderline case: the linear system is a center, whose orbits are circles that never approach the origin, and the nonlinear term decides. Here −y3 removes energy. With +y3 instead, the linearization is the same but E˙=+y4 and solutions spiral outwards.

    Paper A, Problem 3A sector contour

    For an integer n≥2 let In=∫0∞dx1+xn. (1) Show that In converges and In≤1+1n−1. (2) By integrating f(z)=11+zn around the boundary of the sector {z:|z|≤R, 0≤arg⁡z≤2π/n}, show that In=πnsin⁡(π/n). (3) Find limn→∞In, and confirm it directly from the integral without using (2). (4) Show that for integers 1≤s≤n−1, ∫0∞xs−11+xndx=πnsin⁡(πs/n).

    Hint

    (2) Only one zero of 1+zn lies inside the sector: ω=eiπ/n. On the second edge, substitute z=e2πi/nx and notice that zn=xn.

    Solution

    (1) ∫01dx1+xn≤1 and ∫1∞dx1+xn≤∫1∞x−ndx=1n−1.

    (2) The zeros of 1+zn are ei(2j+1)π/n. Only ω=eiπ/n has argument in [0,2π/n]. Since 1+zn has a simple zero there, Resωf=1nωn−1=ωnωn=−ωn. On the arc, |f|≤1Rn−1 and the length is 2πR/n, so the arc contributes nothing as R→∞ (because n≥2). On the second edge, z=e2πi/nx, zn=xn, traversed inwards, contributing −e2πi/nIn. So (1−ω2)In=2πi⋅(−ω/n), and

    In=−2πiωn(1−ω2)=−2πin(ω−1−ω)=−2πin(−2isin⁡(π/n))=πnsin⁡(π/n).

    (3) nsin⁡(π/n)→π, so In→1. Directly: 11+xn→1 for 0≤x<1 and →0 for x>1. For n≥2 it is dominated by 1 on [0,1] and by x−2 on [1,∞), which is integrable, so by dominated convergence In→∫01dx=1.

    (4) Let J be the integral, and use the same contour with g(z)=zs−11+zn. Now Resωg=ωs−1nωn−1=−ωsn. On the arc |g|≤Rs−1Rn−1, and multiplied by the length 2πR/n this is O(Rs−n)→0 since s≤n−1. On the second edge, zs−1dz=e2πis/nxs−1dx. So (1−ω2s)J=−2πiωs/n, and J=−2πin(ω−s−ωs)=πnsin⁡(πs/n). Part (2) is the case s=1.

    Paper A, Problem 4Estimating the end of a uniform distribution

    X1,…,Xn are independent and uniform on (0,θ), where θ>0 is unknown. Let M=maxiXi. (1) Find the maximum likelihood estimator of θ. (2) Find the distribution function of M and E[M]. (3) Show that θ^=n+1nM is unbiased with Var(θ^)=θ2n(n+2), and compare it with the unbiased estimator 2X¯. (4) Show that n(θ−M)/θ converges in distribution to the exponential distribution with mean 1.

    Hint

    (1) Write the likelihood as a function of θ, including the indicator that every observation is below θ. (4) Compute P(n(θ−M)/θ>t) exactly.

    Solution

    (1) L(θ)=θ−n if θ≥M and 0 otherwise. It is decreasing on [M,∞), so the MLE is M. (It is biased low, since M<θ always.)

    (2) P(M≤m)=P(all Xi≤m)=(m/θ)n for 0≤m≤θ. The density is nmn−1/θn, so E[M]=∫0θnmnθndm=nn+1θ.

    (3) E[θ^]=θ by (2). E[M2]=nn+2θ2, so

    Var(θ^)=(n+1)2n2(nn+2−n2(n+1)2)θ2=(n+1)2−n(n+2)n(n+2)θ2=θ2n(n+2).

    Var(2X¯)=4⋅θ2/12n=θ23n. Since n(n+2)≥3n, with equality only at n=1, θ^ is better for n≥2, and much better for large n: its error shrinks like 1/n rather than 1/n.

    (4) For 0≤t≤n, P(n(θ−M)/θ>t)=P(M<θ(1−t/n))=(1−t/n)n→e−t, which is the tail of the exponential distribution with mean 1.

    Paper A, Problem 5Stabbing intervals

    You are given n closed intervals [ai,bi] on the real line. A set of points stabs them if every interval contains at least one of the points. (1) Give a greedy algorithm that finds a stabbing set of minimum size, and prove that it is optimal. (2) Show that it can be implemented in O(nlog⁡n) time. (3) Prove that the minimum size of a stabbing set equals the maximum number of pairwise disjoint intervals. (4) Each interval now has a weight wi>0. Give an O(nlog⁡n) algorithm for the maximum total weight of a set of pairwise disjoint intervals, and justify it.

    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 p (initially −∞). If the current interval [a,b] has a>p, choose a new point at b and set p=b.

    Every interval is stabbed: when it is reached, either a new point is placed at its right end, or a≤p, and since intervals come in order of right endpoint, p≤b, so p∈[a,b]. Let J1,J2,…,Jk be the intervals that triggered the k new points. They are pairwise disjoint: Jt+1 had a(Jt+1)>p=b(Jt). Any stabbing set needs a different point for each of k disjoint intervals, so it has at least k points. The greedy set has exactly k, so it is optimal.

    (2) Sorting takes O(nlog⁡n); the scan is O(n), since each interval needs one comparison with p.

    (3) If m intervals are pairwise disjoint, every stabbing set has at least m points, so min ≥ max. The greedy algorithm produces k points together with k pairwise disjoint intervals, so min =k≤ max.

    (4) Sort by right endpoint, b1≤⋯≤bn, and let q(j) be the largest i<j with bi<aj (or 0), found by binary search in O(log⁡n). Let F(j) be the best weight using intervals among the first j. Then F(0)=0 and F(j)=max(F(j−1),wj+F(q(j))). Correctness: an optimal solution for the first j intervals either omits interval j (giving F(j−1)) or uses it. If it uses it, every other interval in it ends before aj, since one ending at or after aj and no later than bj would meet [aj,bj]; those are exactly the first q(j) intervals, so the rest is at best F(q(j)). Total O(nlog⁡n).

    Paper B

    Linear algebra, optimization, differential equations, probability, algorithms.

    Paper B, Problem 1Schur complements

    Let A be a k×k positive definite matrix, B a real k×m matrix and C a real symmetric m×m matrix, and let M=(ABB⊤C). (1) Show that M⪰O if and only if S=C−B⊤A−1B⪰O. (2) Show that for x∈Rk and t∈R, (Axx⊤t)⪰O if and only if t≥x⊤A−1x. (3) Show that (x,A)↦x⊤A−1x is convex on Rk×{A≻O}. (4) Show that if A⪰B≻O (now B square), then B−1⪰A−1.

    Hint

    (1) Find an invertible block upper-triangular P with P⊤MP block diagonal. (4) Apply (1) to (B−1IIA), once with each diagonal block in the role of A.

    Solution

    (1) Let P=(I−A−1BOI), which is invertible. A direct computation gives P⊤MP=(AOOS). Congruence by an invertible matrix preserves positive semidefiniteness (v⊤P⊤MPv=(Pv)⊤M(Pv)), and A≻O, so M⪰O⟺S⪰O.

    (2) The case m=1, B=x, C=t: S=t−x⊤A−1x.

    (3) By (2), the epigraph {(x,A,t):A≻O, t≥x⊤A−1x} equals {(x,A,t):A≻O, (Axx⊤t)⪰O}. The matrix depends linearly on (x,A,t), and the PSD cone and the open cone {A≻O} are convex, so the epigraph is convex, and the function is convex.

    (4) Let N=(B−1IIA). With B−1≻O as the first block, (1) gives N⪰O⟺A−I(B−1)−1I=A−B⪰O, which holds. Swapping the two block rows and columns (a permutation congruence) gives (AIIB−1)⪰O, and now with A≻O as the first block, (1) gives B−1−A−1⪰O. (A≻O because A⪰B≻O.)

    Paper B, Problem 2Projection onto the simplex

    Let Δ={x∈Rn:xi≥0, ∑ixi=1}, and for y∈Rn let P(y) minimize 12‖x−y‖2 over x∈Δ. (1) Show that P(y) exists, is unique, and is the only p∈Δ with ⟨y−p,z−p⟩≤0 for all z∈Δ. (2) Show there is a unique τ∈R with P(y)i=max(yi−τ,0) for all i, and give an O(nlog⁡n) algorithm for τ. (3) Show that ‖P(y)−P(y′)‖≤‖y−y′‖. (4) Let f be convex and differentiable with L-Lipschitz gradient, x0∈Δ, and xk+1=P(xk−1L∇f(xk)). Show that f(xk+1)≤f(xk)−L2‖xk+1−xk‖2.

    Hint

    (2) Write the KKT conditions with a multiplier τ for ∑xi=1. To find τ, sort y in decreasing order u1≥⋯≥un and guess how many coordinates of P(y) are positive. (4) Use (1) with z=xk, then the descent lemma f(x+d)≤f(x)+⟨∇f(x),d⟩+L2‖d‖2.

    Solution

    (1) Δ is compact and the objective continuous, so a minimizer exists; the objective is strictly convex and Δ convex, so it is unique. If p is the minimizer and z∈Δ, then φ(t)=12‖p+t(z−p)−y‖2 is minimized over [0,1] at t=0, so φ′(0)=⟨p−y,z−p⟩≥0. Conversely, if p∈Δ satisfies the inequality, then ‖z−y‖2=‖z−p‖2+‖p−y‖2+2⟨z−p,p−y⟩≥‖p−y‖2 for every z∈Δ.

    (2) The constraints are linear, so the KKT conditions are necessary and sufficient: xi−yi−μi+τ=0, μi≥0, μixi=0, x∈Δ. If xi>0 then μi=0 and xi=yi−τ; if xi=0 then yi−τ=−μi≤0. Either way xi=max(yi−τ,0). The function g(τ)=∑imax(yi−τ,0) is continuous and non-increasing, strictly decreasing wherever it is positive, tends to ∞ as τ→−∞, and is 0 for τ≥maxiyi. So exactly one τ∗ has g(τ∗)=1.

    Algorithm: sort u1≥⋯≥un, compute prefix sums, and let τj=1j(∑i≤jui−1). Return τk for the largest k with uk>τk. Why: uj>τj⟺∑i≤j(ui−uj)<1⟺g(uj)<1⟺uj>τ∗. So the j with uj>τj are exactly 1,…,k, where k is the number of positive coordinates of P(y), and then g(τ∗)=∑i≤kui−kτ∗=1 gives τ∗=τk. Sorting is O(nlog⁡n), the rest O(n).

    (3) Let p=P(y), p′=P(y′). By (1), ⟨y−p,p′−p⟩≤0 and ⟨y′−p′,p−p′⟩≤0. Adding: ‖p−p′‖2≤⟨y−y′,p−p′⟩≤‖y−y′‖‖p−p′‖.

    (4) Let d=xk+1−xk. By (1) with y=xk−1L∇f(xk) and z=xk: ⟨xk−1L∇f(xk)−xk+1,xk−xk+1⟩≤0, i.e. ⟨∇f(xk),d⟩≤−L‖d‖2. The descent lemma then gives f(xk+1)≤f(xk)−L‖d‖2+L2‖d‖2=f(xk)−L2‖d‖2.

    Paper B, Problem 3Gradient flow of a strongly convex function

    Let f:Rd→R be continuously differentiable with locally Lipschitz gradient and μ-strongly convex for some μ>0: f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2‖y−x‖2 for all x,y. Let x∗ be its minimizer and f∗=f(x∗), and let x(t) solve x˙=−∇f(x). (1) Show that ddtf(x(t))=−‖∇f(x(t))‖2, and that the solution exists for all t≥0. (2) Show that ‖∇f(x)‖2≥2μ(f(x)−f∗) for every x. (3) Show that f(x(t))−f∗≤e−2μt(f(x(0))−f∗). (4) Show that ‖x(t)−x∗‖≤e−μt‖x(0)−x∗‖.

    Hint

    (2) Minimize both sides of the strong convexity inequality over y. (4) Differentiate 12‖x−x∗‖2, and add the strong convexity inequality to itself with x and y swapped.

    Solution

    (1) By the chain rule, ddtf(x)=⟨∇f(x),x˙⟩=−‖∇f(x)‖2. So f(x(t))≤f(x(0)). Strong convexity at x∗ (where ∇f=0) gives f(y)≥f∗+μ2‖y−x∗‖2, so the sublevel set {f≤f(x(0))} is bounded. The solution stays in it, cannot blow up, and so exists for all t≥0.

    (2) The right-hand side of the inequality is minimized over y at y=x−∇f(x)/μ, with value f(x)−12μ‖∇f(x)‖2. The left side is at least f∗ for every y, so f∗≥f(x)−12μ‖∇f(x)‖2.

    (3) Let g(t)=f(x(t))−f∗. By (1) and (2), g˙≤−2μg, so ddt(e2μtg)≤0 and g(t)≤e−2μtg(0).

    (4) Adding the strong convexity inequality to the same inequality with x,y swapped gives ⟨∇f(x)−∇f(y),x−y⟩≥μ‖x−y‖2. With y=x∗ and ∇f(x∗)=0: ddt12‖x−x∗‖2=−⟨∇f(x),x−x∗⟩≤−μ‖x−x∗‖2. So ‖x(t)−x∗‖2≤e−2μt‖x(0)−x∗‖2. For f=μ2‖x‖2, x(t)=e−μtx(0), so both rates are sharp.

    Paper B, Problem 4The coupon collector

    Each draw gives one of n coupon types, uniformly at random and independently of the other draws. Let T be the number of draws until every type has appeared, and Hn=∑k=1n1k. (1) Show that E[T]=nHn. (2) Show that Var(T)≤π26n2. (3) Show that P(|T−nHn|≥cn)≤π26c2 for c>0. (4) Let c>0 and let m≥nln⁡n+cn be an integer. Show that P(T>m)≤e−c.

    Hint

    (1) Split T into the waiting times between consecutive new types. (4) T>m means some particular type is missing from the first m draws: use a union bound and 1−x≤e−x.

    Solution

    (1) Let Gi be the number of draws after the (i−1)th new type until the ith. Each of those draws is new with probability pi=n−i+1n, independently, so Gi is geometric with mean 1/pi, and T=∑i=1nGi. Then E[T]=∑inn−i+1=nHn.

    (2) The Gi are independent, and Var(Gi)=1−pipi2≤1pi2. So Var(T)≤∑k=1nn2k2≤π26n2.

    (3) Chebyshev's inequality with (1) and (2).

    (4) T>m exactly when some type is absent from the first m draws. A given type is absent with probability (1−1n)m≤e−m/n. By the union bound, P(T>m)≤ne−m/n≤ne−ln⁡n−c=e−c. Compare (3): Chebyshev only gives a 1/c2 tail, while the union bound gives an exponential one on the upper side.

    Paper B, Problem 5Two-colouring a graph

    Let G=(V,E) be an undirected graph with n vertices and m edges, given by adjacency lists. G is bipartite if its vertices can be coloured with two colours so that every edge joins different colours. (1) Show that a graph containing a cycle of odd length is not bipartite. (2) Give an O(n+m) algorithm that decides whether G is bipartite and, if it is, outputs a colouring. (3) Prove that if your algorithm reports "not bipartite", then G contains an odd cycle, so (1) and (3) together show that G is bipartite exactly when it has no odd cycle. (4) If G is bipartite with c connected components, how many valid two-colourings does it have? Prove it.

    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 v0v1⋯vk−1v0 in a valid colouring, the colours alternate, so vi has the colour of v0 exactly when i is even. The edge vk−1v0 then needs k−1 to be even, i.e. k odd is impossible.

    (2) For each vertex not yet coloured, run BFS from it, giving each vertex the colour distmod2 (distance from the start of its BFS). Afterwards check every edge; if some edge has both ends the same colour, report "not bipartite", otherwise output the colouring. Each vertex and edge is handled a constant number of times: O(n+m).

    (3) If the colouring is valid, G is bipartite. Otherwise some edge uv has dist(u)≡dist(v)(mod2); both are in the same BFS tree, and for an edge, BFS distances differ by at most 1, so dist(u)=dist(v)=d. Let w be the last common vertex of the tree paths from the root to u and to v, at distance d′. The tree path w→u, the edge uv and the tree path v→w form a cycle of length 2(d−d′)+1, which is odd.

    (4) 2c. In a valid colouring, the colour of one vertex in a component determines all others in it: along any path the colours alternate. So each component has at most two colourings, and if it is bipartite, exactly two (swap the colours). Choices in different components are independent.

    Paper C

    Linear algebra, analysis, differential equations, probability, algorithms.

    Paper C, Problem 1The Schur product theorem and kernels

    For n×n matrices, A∘B is the entrywise product, (A∘B)ij=AijBij. (1) Show that if A=aa⊤ and B=bb⊤ for vectors a,b, then A∘B=(a∘b)(a∘b)⊤. (2) Show that A,B⪰O implies A∘B⪰O. (3) Show that if G⪰O, the matrix E with Eij=eGij is positive semidefinite. (4) For points x1,…,xn∈Rd, show that Kij=exp⁡(−12‖xi−xj‖2) defines a positive semidefinite matrix.

    Hint

    (2) Write A and B as sums of rank-one PSD matrices. (3) Expand the exponential as a power series, entry by entry. (4) Expand ‖xi−xj‖2 and look for a Gram matrix.

    Solution

    (1) (aa⊤∘bb⊤)ij=aiajbibj=(aibi)(ajbj).

    (2) By the spectral theorem, A=∑iαiuiui⊤ and B=∑jβjvjvj⊤ with αi,βj≥0. The product ∘ is bilinear, so by (1), A∘B=∑i,jαiβj(ui∘vj)(ui∘vj)⊤, a non-negative combination of PSD matrices.

    (3) By (2) and induction, every entrywise power G∘k is PSD, and G∘0=11⊤ is PSD. So each partial sum ∑k≤NG∘k/k! is PSD, and it converges entrywise to E. The PSD matrices form a closed set (v⊤Ev is a limit of non-negative numbers), so E⪰O.

    (4) −12‖xi−xj‖2=−12‖xi‖2+⟨xi,xj⟩−12‖xj‖2, so K=DED, where D=diag(e−‖xi‖2/2) and E comes from the Gram matrix Gij=⟨xi,xj⟩⪰O as in (3). Then v⊤Kv=(Dv)⊤E(Dv)≥0. This is why the Gaussian kernel is a valid kernel in kernel methods.

    Paper C, Problem 2Fourier series and Parseval

    Use the conventions ak=1π∫−ππf(x)cos⁡kxdx, bk=1π∫−ππf(x)sin⁡kxdx, and Parseval's identity 1π∫−ππf2=a022+∑k≥1(ak2+bk2) for square-integrable f. (1) Find the Fourier coefficients of f(x)=x on (−π,π). (2) Deduce that ∑k≥11k2=π26. (3) Let SN be the Nth partial sum of the series in (1). Show that sup−π<x<π|SN(x)−x|≥π for every N. (4) Find the Fourier coefficients of x2 on (−π,π) and deduce that ∑k≥11k4=π490.

    Hint

    (3) SN is a finite sum of sines, so it is continuous on [−π,π]. What is SN(π)?

    Solution

    (1) f is odd, so ak=0. Integrating by parts, bk=2π∫0πxsin⁡kxdx=2π[−xcos⁡kxk]0π+2πk∫0πcos⁡kxdx=2(−1)k+1k.

    (2) 1π∫−ππx2dx=2π23=∑k4k2.

    (3) SN(x)=∑k≤Nbksin⁡kx is continuous with SN(π)=0. As x→π−, |SN(x)−x|→π, so the supremum over (−π,π) is at least π. The convergence is not uniform: the periodic extension of x jumps at ±π, and a uniform limit of continuous functions would be continuous.

    (4) x2 is even, so bk=0; a0=1π∫x2=2π23, and integrating by parts twice, ak=4(−1)kk2. Parseval: 1π∫−ππx4dx=2π45=a022+∑k16k4=2π49+16∑k1k4. So ∑k1k4=116(25−29)π4=π490.

    Paper C, Problem 3The Lyapunov equation

    A real n×n matrix A is stable if all its eigenvalues have negative real part. You may use that then there are C,α>0 with ‖eAt‖≤Ce−αt for t≥0. (1) Suppose P≻O satisfies A⊤P+PA=−I. Show that every solution of x˙=Ax satisfies V(t)≤e−t/λmax(P)V(0), where V=x⊤Px, and hence x(t)→0. (2) Suppose A is stable. Show that P=∫0∞eA⊤teAtdt is well defined, positive definite, and satisfies A⊤P+PA=−I. (3) Show that the solution in (2) is the only solution of A⊤X+XA=−I. (4) Find P for A=(−110−2).

    Hint

    (2) The integrand is ddt of something simple, after multiplying by A⊤ on the left and A on the right. (3) If A⊤X+XA=O, differentiate eA⊤tXeAt.

    Solution

    (1) V˙=x⊤(A⊤P+PA)x=−‖x‖2. Since V≤λmax(P)‖x‖2, V˙≤−V/λmax(P), and Grönwall gives the bound. Then ‖x‖2≤V/λmin(P)→0.

    (2) ‖eA⊤teAt‖≤C2e−2αt, which is integrable. For x≠0, x⊤Px=∫0∞‖eAtx‖2dt>0, since the integrand is continuous and equals ‖x‖2>0 at t=0. Finally

    A⊤P+PA=∫0∞(A⊤eA⊤teAt+eA⊤teAtA)dt=∫0∞ddt(eA⊤teAt)dt=limT→∞eA⊤TeAT−I=−I.

    (3) If X and P both solve it, D=X−P satisfies A⊤D+DA=O, so ddt(eA⊤tDeAt)=eA⊤t(A⊤D+DA)eAt=O. Hence eA⊤tDeAt=D for all t, and the left side tends to O. So D=O.

    (4) Write P=(pqqr). Then A⊤P+PA=(−2pp−3qp−3q2q−4r)=−I gives p=12, q=16, r=13. So P=(1/21/61/61/3), which is positive definite (detP=536>0, p>0), as (2) promises.

    Paper C, Problem 4A Poisson count with a gamma prior

    A rate λ>0 has the gamma prior with density βαΓ(α)λα−1e−βλ (α,β>0), and given λ, X is Poisson with mean λ. (1) Find the posterior distribution of λ given X=x. (2) Find the marginal probability P(X=k) for k=0,1,2,…. (3) Show that Var(X)=αβ+αβ2, so that Var(X)>E[X]. (4) Under squared-error loss, the Bayes estimate of λ is the posterior mean. Show that it is a weighted average of the prior mean and x, and find the weights.

    Hint

    (1) Multiply prior by likelihood and recognise the shape. (3) Use Var(X)=E[Var(X∣λ)]+Var(E[X∣λ]).

    Solution

    (1) The posterior density is proportional to e−λλx⋅λα−1e−βλ=λα+x−1e−(β+1)λ: gamma with parameters α+x and β+1.

    (2) P(X=k)=∫0∞e−λλkk!βαΓ(α)λα−1e−βλdλ=Γ(α+k)k!Γ(α)(ββ+1)α(1β+1)k, a negative binomial distribution.

    (3) The gamma prior has mean α/β and variance α/β2. Given λ, X has mean and variance λ. So Var(X)=E[λ]+Var(λ)=αβ+αβ2>αβ=E[X]. Uncertainty about the rate adds variance, which is why the negative binomial is used for over-dispersed counts.

    (4) The posterior mean is α+xβ+1=ββ+1⋅αβ+1β+1⋅x. The weight on the data, 1β+1, is small when the prior is concentrated (large β).

    Paper C, Problem 5Longest increasing subsequences

    Let a1,…,an be distinct real numbers and L the length of their longest increasing subsequence. (1) Give an O(n2) dynamic program for L. (2) Give an O(nlog⁡n) algorithm, and prove it correct. (3) Prove that if n=k2+1, the sequence has an increasing or a decreasing subsequence of length k+1. (4) Prove that the minimum number of decreasing subsequences into which the sequence can be partitioned is exactly L.

    Hint

    (2) Keep, for each length j, the smallest possible last element of an increasing subsequence of length j seen so far. (3) and (4) Label each ai with ℓi, the length of the longest increasing subsequence ending at ai.

    Solution

    (1) ℓi=1+max{ℓj:j<i, aj<ai} (with max∅=0), and L=maxiℓi. Each ℓi takes O(i) time.

    (2) Maintain t1,t2,…,tr, where tj is the smallest last element of an increasing subsequence of length j among the elements read so far. The tj are strictly increasing: dropping the last element of a length-j subsequence ending at tj leaves a length-(j−1) one ending below tj. To read a, find by binary search the first j with tj>a (or j=r+1), and set tj=a. This is right: tj−1<a (or j=1), so a extends a subsequence of length j−1 to length j, ending at a<tj. For i<j, a>ti cannot improve ti. For i>j, a length-i subsequence ending at a would need a length-(i−1) one ending below a, but those end at ≥ti−1≥tj>a. At the end, L=r. Each step is O(log⁡n).

    (3) Let di be the length of the longest decreasing subsequence ending at ai. For i<j: if ai<aj then ℓj>ℓi, otherwise dj>di. So the pairs (ℓi,di) are distinct. If all were at most k, there would be at most k2<n pairs.

    (4) An increasing subsequence meets each decreasing subsequence in at most one element, so at least L parts are needed. Conversely, put ai in part ℓi∈{1,…,L}. Within one part the elements decrease: if i<j and ai<aj, then ℓj≥ℓi+1, so they are in different parts. (This is the simplest case of Dilworth's theorem.)

    InteractiveAxler, Ch. 7: Operators on Inner Product Spaces

    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

    Adjoint, self-adjoint, normal (Axler 7.2, 7.10, 7.18). T∗ is defined by ⟨Tv,w⟩=⟨v,T∗w⟩. T is self-adjoint if T=T∗ (a symmetric matrix in an orthonormal basis), normal if TT∗=T∗T.
    Spectral theorems (Axler 7.29, 7.31). Over R, V has an orthonormal basis of eigenvectors of T iff T is self-adjoint. Over C, iff T is normal.
    Singular value decomposition (Axler 7.70). For any T∈L(V,W) there are orthonormal e1,…,em in V and f1,…,fm in W and s1≥⋯≥sm>0 with Tv=∑sk⟨v,ek⟩fk. The sk are the square roots of the eigenvalues of T∗T.

    Geometrically (Axler 7.99): T sends the unit ball to an ellipsoid whose semi-axes are skfk, and the ek are the directions that land on those axes.

    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 T 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

    Preset
    The unit circle and the right singular vectors e₁, e₂.
    Its image: an ellipse with semi-axes s₁f₁, s₂f₂. Drag Te₁ and Te₂ (the matrix columns).

    Worked example

    Find the singular values of the shear T=(1101).

    1. Compute T∗T.

      T∗T=(1011)(1101)=(1112).

    2. Its eigenvalues?

      Trace 3, determinant 1: μ=3±52.

    3. Singular values, and a sanity check.

      s=μ=5±12≈1.618, 0.618: the golden ratio and its reciprocal. Their product is |detT|=1, the area scale. The eigenvalues of T are both 1, very different from the singular values: T is not normal.

    Check your understanding

    For a self-adjoint operator, the singular values are

    1. the absolute values of its eigenvalues.
    2. its eigenvalues.Singular values are never negative.
    T∗T=T2 has eigenvalues λ2. Pick "symmetric" in the figure with a negative eigenvalue: the ellipse doesn't care about the sign; fk=±ek.

    Which matrices are normal?

    1. Rotations.
    2. The shear (1101).TT∗≠T∗T here.
    Rotations are unitary: T∗T=I=TT∗. Over C they are diagonalizable in an orthonormal basis with eigenvalues e±iθ, though over R they have no eigenvectors at all.

    The best rank-1 approximation of T in operator norm is

    1. v↦s1⟨v,e1⟩f1.
    2. the rank-1 piece with the smallest singular value.Keep the biggest, drop the rest.
    Truncating the SVD after k terms gives the best rank-k approximation, with error sk+1 (Eckart–Young). This is the idea behind principal components and image compression.

    Practice

    Eigenvalues of self-adjoint operators are realAxler 7.12

    Prove it, and prove eigenvectors for distinct eigenvalues are orthogonal.

    Solution

    λ‖v‖2=⟨Tv,v⟩=⟨v,Tv⟩=λ¯‖v‖2. If Tv=λv, Tw=μw with λ≠μ real: λ⟨v,w⟩=⟨Tv,w⟩=⟨v,Tw⟩=μ⟨v,w⟩, so ⟨v,w⟩=0.

    Operator normAxler 7.85

    Show ‖T‖=max‖v‖=1‖Tv‖=s1.

    Solution

    With v=∑akek (extended to an orthonormal basis), ‖Tv‖2=∑sk2|ak|2≤s12∑|ak|2, with equality at v=e1.

    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 T∈L(V) and a subspace U, prove that U is invariant under T if and only if U⟂ is invariant under T∗.

    Hint

    Use ⟨Tu,w⟩=⟨u,T∗w⟩, and for the converse apply the first half to T∗.

    Solution

    Suppose TU⊆U. For w∈U⟂ and u∈U: ⟨u,T∗w⟩=⟨Tu,w⟩=0, since Tu∈U. So T∗w∈U⟂.

    Conversely, if U⟂ is invariant under T∗, the first half applied to T∗ and U⟂ says (U⟂)⟂=U is invariant under T∗∗=T (Axler 6.52, 7.5).

    Exercise 7E.1Zero singular values

    Show T∈L(V,W) is 0 if and only if all its singular values are 0.

    Hint

    The singular values are the square roots of the eigenvalues of T∗T, and ‖Tv‖2=⟨T∗Tv,v⟩.

    Solution

    If T=0, then T∗T=0, whose eigenvalues are all 0. Conversely, if all singular values are 0, the self-adjoint operator T∗T has only the eigenvalue 0. By the spectral theorem it is diagonal with zeros in an orthonormal basis, so T∗T=0. Then ‖Tv‖2=⟨T∗Tv,v⟩=0 for every v, so T=0.

    Exercise 7E.3Eigenvalues 0, 0 but singular values 5, 0

    Give T∈L(C2) whose only eigenvalue is 0 and whose singular values are 5 and 0.

    Hint

    A nilpotent map with a large entry.

    Solution

    T=(0500), i.e. T(z1,z2)=(5z2,0). It is upper triangular with zero diagonal, so 0 is its only eigenvalue. T∗T=(00025), so the singular values are 5 and 0. Eigenvalues and singular values agree for normal operators, but this T is far from normal.

    Interactive2020 P1, 2024 P1, 2025 P1, 2026 P1; Horn and Johnson, Ch. 2, 4, 7

    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

    Spectral theorem (H&J 4.1.5). A real symmetric B can be written B=QΛQ⊤ with Q orthogonal and Λ=diag(λ1,…,λn) real. B⪰O (positive semidefinite, 半正定値) means x⊤Bx≥0 for all x, equivalently all λi≥0. Then B1/2=QΛ1/2Q⊤ is the unique PSD square root (H&J 7.2.6).

    Change basis first. (Sylvester's theorem, H&J 2.4.4.1, is the general form: AX−XB=C is uniquely solvable for every C exactly when A and B share no eigenvalue.) For an equation like BC+CB=A, put C~=Q⊤CQ and A~=Q⊤AQ. The equation becomes ΛC~+C~Λ=A~, which is entrywise: (λi+λj)C~ij=A~ij. Commuting with B becomes (λi−λj)C~ij=0.

    Loewner order (H&J 7.7.1). X⪰Y means X−Y⪰O. It is a partial order: two symmetric matrices are often incomparable. Congruence preserves it: X⪰Y⇒S⊤XS⪰S⊤YS for any S (H&J 7.7.2), which is the tool for reducing to B=I.
    Trace facts for PSD matrices (H&J 7.2.P26, 7.5.4). If A,B⪰O then tr(AB)=tr(A1/2BA1/2)≥0, and tr(AB)=‖A1/2B1/2‖F2, so tr(AB)=0 if and only if AB=O. Conversely, A⪰O if and only if tr(AC)≥0 for every PSD C (take C=vv⊤): the PSD cone is self-dual. Horn and Johnson credit this to Moutard (1894).
    What the order survives (H&J 7.7.4, 7.7.P3). If A⪰B≻O then B−1⪰A−1 and A1/2⪰B1/2. It does not follow that A2⪰B2. (Functions that preserve the order are called operator monotone; t1/2, log⁡t and −1/t are, t2 is not.)

    Projection onto the PSD cone. With the inner product ⟨A,B⟩=tr(AB), the nearest PSD matrix to a symmetric A=QΛQ⊤ clips the negative eigenvalues: ϕ(A)=Qmax(Λ,0)Q⊤. Like every projection onto a closed convex set, it is characterized by the variational inequality ⟨A−ϕ(A),X−ϕ(A)⟩≤0 for all X in the set. The same inequality reappears for isotonic regression in the algorithms topic.

    Orthogonal Procrustes (H&J 7.4.5). Over orthogonal P, ‖PX−Y‖F2=‖X‖F2+‖Y‖F2−2tr(PXY⊤). Minimizing it means maximizing the trace; if XY⊤=UΣV⊤, the maximizer is P=VU⊤.

    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

    The curve x⊤Mx=1 of a positive definite M is an ellipse with semi-axes 1/λi along its eigenvectors. A larger matrix gives a smaller ellipse, so P⪰Q exactly when the ellipse of P sits inside the ellipse of Q. left side right side. Drag the dots to change A and B.
    Test the claim
    Start from

    Worked example

    2025 P1(4): find 2×2 symmetric A⪰B⪰O with A2⪰̸B2.

    1. Why must A and B fail to commute?

      If AB=BA they diagonalize in a common basis, and ai≥bi≥0 gives ai2≥bi2. So the counterexample needs tilted axes, as in the second preset above.

    2. Take B=diag(1,0) and A=B+(1111). Check A⪰B⪰O.

      A−B=(1111)=vv⊤ with v=(1,1)⊤, which is PSD. B is PSD. So A=(2111)⪰B⪰O.

    3. Compute A2−B2 and decide.

      A2=(5332), B2=B, so A2−B2=(4332) with determinant 8−9=−1<0. One eigenvalue is negative, so A2⪰̸B2. Writing out the matrices and the determinant is a complete answer for a "false" part.

    Check your understanding

    If A⪰B⪰O, which of these must hold?

    1. A2⪰B2The worked example above is a counterexample.
    2. A1/2⪰B1/2
    3. AB⪰OAB need not even be symmetric when they don't commute.
    The square root is operator monotone. Proof: let S=A1/2, R=B1/2, and suppose (S−R)v=−μv with μ>0, ‖v‖=1. Since S2−R2=(S−R)S+R(S−R), we get v⊤(A−B)v=−μv⊤(S+R)v≤0. But A⪰B, so v⊤(S+R)v=0, forcing Sv=Rv=0 and (S−R)v=0, a contradiction.

    X,Y⪰O and tr(XY)=0. What follows?

    1. X=O or Y=OX=diag(1,0), Y=diag(0,1).
    2. XY=O
    3. X+Y is singularThe same example gives X+Y=I.
    tr(XY)=‖X1/2Y1/2‖F2=0 forces X1/2Y1/2=O, hence XY=O. The ranges are orthogonal: that is the complementarity behind 2026 P1(4) and semidefinite programming.

    What is the nearest PSD matrix to A=diag(3,−2) in the Frobenius norm?

    1. diag(3,0)
    2. diag(3,2)That flips the sign. It is at distance 4, while clipping gives distance 2.
    3. diag(1,0)Clipping only touches negative eigenvalues.
    Clip negative eigenvalues to zero in the eigenbasis. 2026 P1(2) asks you to prove this is the unique minimizer.
    Practice2020 P1, 2024 P1, 2025 P1, 2026 P1; Horn and Johnson, Ch. 2, 4, 7

    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

    A is a real n×n matrix and B is symmetric positive definite. (1) Show there is exactly one real C with BC+CB=A; call it CA,B. (2) Show BCA,B=CA,BB if and only if AB=BA.

    Hint

    (1) Change to the eigenbasis of B. (2) For one direction, show BCB−1 also solves the equation and use uniqueness.

    Solution

    (1) Write B=QΛQ⊤ with all λi>0. With C~=Q⊤CQ and A~=Q⊤AQ, the equation is equivalent to (λi+λj)C~ij=A~ij for all i,j. Since λi+λj>0, the unique solution is C~ij=A~ij/(λi+λj), and C=QC~Q⊤ is real. (Equivalently, the linear map C↦BC+CB has eigenvalues λi+λj>0, so it is invertible.)

    (2) If BC=CB then A=2BC, and AB=2BCB=2B(BC)=BA. Conversely, if AB=BA, let C′=BCB−1. Then BC′+C′B=B(BC+CB)B−1=BAB−1=A, so C′=C by uniqueness, which says BC=CB.

    2024 Problem 1Orthogonal Procrustes

    Let d<m, X,Y∈Rd×m, and let OPT(X,Y) be the set of minimizers of ‖PX−Y‖F2 over P∈Rd×d with P⊤P=I. (1) Given A,B∈Rd×m with columns aj,bj and weights wj>0, find X,Y so that OPT(X,Y) is the set of minimizers of ∑jwj‖Paj−bj‖22. (2) Show OPT(X,Y) is the set of maximizers of tr(PXY⊤) over orthogonal P. (3) If XY⊤=UΣV⊤ is an SVD, give an element of OPT(X,Y).

    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; ‖PX‖F=‖X‖F when P is orthogonal. (3) Write tr(PUΣV⊤)=tr(ZΣ) with Z=V⊤PU orthogonal.

    Solution

    (1) X=AW1/2, Y=BW1/2 with W=diag(w1,…,wm). Column j of PX−Y is wj(Paj−bj), so ‖PX−Y‖F2=∑jwj‖Paj−bj‖22 for every P.

    (2) ‖PX−Y‖F2=tr(X⊤P⊤PX)−2tr(Y⊤PX)+‖Y‖F2=‖X‖F2+‖Y‖F2−2tr(PXY⊤), using P⊤P=I and tr(Y⊤PX)=tr(PXY⊤). The first two terms don't depend on P, so minimizing the left side is the same as maximizing tr(PXY⊤).

    (3) tr(PUΣV⊤)=tr(V⊤PUΣ)=∑iσiZii with Z=V⊤PU orthogonal. Entries of an orthogonal matrix satisfy |Zii|≤1, so the trace is at most ∑iσi, with equality at Z=I, i.e. P=VU⊤. This P is in OPT(X,Y). Horn and Johnson (7.4.5) state the same answer through the polar decomposition: if YX⊤=HU0 with H⪰O, U0 orthogonal, then P=U0.

    2025 Problem 1True or false for the Loewner order

    For real symmetric d×d matrices A,B (d≥2), prove or give a counterexample: (1) A,B⪰O⇒tr(AB)≥0. (2) A,B⪰O and tr(AB)=0⇒A=O or B=O. (3) tr(AC)≥0 for every PSD C⇒A⪰O. (4) A⪰B⪰O⇒A2⪰B2. (5) A⪰B≻O⇒B−1⪰A−1.

    Hint

    (5) Reduce to the case B=I by congruence with B−1/2.

    Solution

    (1) True. tr(AB)=tr(A1/2BA1/2), and A1/2BA1/2⪰O since x⊤A1/2BA1/2x=(A1/2x)⊤B(A1/2x)≥0. Its trace is a sum of nonnegative eigenvalues.

    (2) False. A=diag(1,0,…,0), B=diag(0,1,0,…,0).

    (3) True. For any v, C=vv⊤⪰O, and tr(Avv⊤)=v⊤Av≥0.

    (4) False. The worked example above, padded with zeros for d>2.

    (5) True. A⪰B gives M:=B−1/2AB−1/2⪰I (congruence preserves ⪰), so every eigenvalue of M is at least 1 and every eigenvalue of M−1=B1/2A−1B1/2 is at most 1, i.e. B1/2A−1B1/2⪯I. Congruence with B−1/2 gives A−1⪯B−1.

    2026 Problem 1Projection onto the PSD cone

    Sn is the space of real symmetric matrices with ⟨A,B⟩=tr(AB), and S+n the PSD ones. (1) Show S+n is convex. (2) Show ‖X−A‖2 has a unique minimizer ϕ(A) over X∈S+n and write it using the eigen-decomposition of A. (3) Show ⟨A−ϕ(A),X−ϕ(A)⟩≤0 for all X∈S+n. (4) For X,Y∈S+n, show ⟨X,Y⟩=0 if and only if X=ϕ(X−Y).

    Hint

    (2) In the eigenbasis of A, the squared distance is at least the sum of squared diagonal differences. (4) First prove the converse of (3): a PSD Z satisfying the inequality must be ϕ(A).

    Solution

    (1) x⊤(αX+(1−α)Y)x=αx⊤Xx+(1−α)x⊤Yx≥0.

    (2) Write A=QΛQ⊤. For PSD X, X~=Q⊤XQ is PSD (so X~ii≥0) and ‖X−A‖2=‖X~−Λ‖2=∑i(X~ii−λi)2+∑i≠jX~ij2≥∑i(X~ii−λi)2≥∑i:λi<0λi2. Equality holds throughout exactly when X~ is diagonal with X~ii=max(λi,0). So the minimizer exists and is unique: ϕ(A)=∑imax(λi,0)qiqi⊤, where qi are orthonormal eigenvectors.

    (3) Let N=∑λi<0(−λi)qiqi⊤⪰O. Then A−ϕ(A)=−N and Nϕ(A)=O (they live on orthogonal eigenvectors), so ⟨A−ϕ(A),X−ϕ(A)⟩=−⟨N,X⟩+⟨N,ϕ(A)⟩=−tr(NX)≤0 by the trace fact. (A general proof: for t∈(0,1], ϕ+t(X−ϕ) is PSD by (1), so ‖ϕ+t(X−ϕ)−A‖2≥‖ϕ−A‖2; expand, divide by t, let t→0.)

    (4) First, if Z is PSD and ⟨A−Z,W−Z⟩≤0 for all PSD W, then ‖W−A‖2=‖W−Z‖2+‖Z−A‖2−2⟨A−Z,W−Z⟩≥‖Z−A‖2, so Z=ϕ(A) by uniqueness. Now take A=X−Y, Z=X: the inequality reads ⟨−Y,W−X⟩=⟨X,Y⟩−⟨Y,W⟩≤0 for all PSD W.

    (i)⇒(ii): if ⟨X,Y⟩=0, this is −tr(YW)≤0, true by the trace fact, so X=ϕ(X−Y). (ii)⇒(i): if X=ϕ(X−Y), (3) gives the inequality for all PSD W. With W=O: ⟨X,Y⟩≤0. The trace fact gives ⟨X,Y⟩≥0. So ⟨X,Y⟩=0.

    From Horn and Johnson, Matrix Analysis (2nd ed., Cambridge, 2013)

    Numbers match the book, which works over C with Hermitian matrices; read "real symmetric" and ⊤ if you prefer. Each problem is restated in our own words; the hints and solutions are written for this page.

    Problem 2.4.P13Sylvester's equation by eigenvalues (the engine of 2020 P1)

    Let A∈Mn and B∈Mm have no eigenvalue in common. Show that X↦AX−XB is invertible on n×m matrices, by showing that T1(X)=AX and T2(X)=XB commute and that the eigenvalues of T1−T2 are differences of eigenvalues of A and B.

    Hint

    T1 acts on each column of X by A; T2 acts on each row by B⊤. Commuting linear maps can be triangularized in one basis (H&J 2.3.3).

    Solution

    T1T2(X)=AXB=T2T1(X). Acting column by column, T1 is Im⊗A, with the eigenvalues λi of A; acting row by row, T2 is B⊤⊗In, with the eigenvalues μj of B. Triangularize T1 and T2 simultaneously: the diagonal of T1−T2 then consists of differences λi−μj, none of which is 0. So T1−T2 is invertible.

    For 2020 P1, BC+CB=A is BC−C(−B)=A: the relevant differences are λi−(−λj)=λi+λj>0. The eigenbasis computation in that solution is this argument made explicit.

    Problem 7.2.P26(a)A two-sided bound on tr AB

    For PSD A,B, show 0≤trAB≤λmax(A)trB (the book writes λmax(A) as the spectral norm |||A|||2).

    Hint

    Move the square root of B to both sides and use A⪯λmax(A)I.

    Solution

    trAB=tr(B1/2AB1/2). Since O⪯A⪯λmax(A)I, congruence gives O⪯B1/2AB1/2⪯λmax(A)B, and the trace is monotone for ⪯ (the difference has non-negative eigenvalues). Taking traces gives both inequalities. The lower one is 2025 P1(1).

    Problem 7.7.P6A bigger matrix has a bigger range

    If A⪰B⪰O, show rangeB⊆rangeA.

    Hint

    Compare null spaces, then take orthogonal complements.

    Solution

    If Ax=0, then 0=x⊤Ax≥x⊤Bx=‖B1/2x‖2≥0, so B1/2x=0 and Bx=0. Hence nullA⊆nullB. For symmetric matrices range=(null)⟂, so rangeB⊆rangeA. In the ellipse picture: wherever A is degenerate, its "ellipse" runs off to infinity, and since it must fit inside B's, B is degenerate in that direction too.

    Problem 7.7.P21(a, b)How much must A be scaled to dominate B?

    Let A≻O and B⪰O. Show that cA⪰B for some c>0, and that the smallest such c is the spectral radius ρ(A−1B).

    Hint

    Congruence by A−1/2.

    Solution

    cA⪰B⟺cI⪰A−1/2BA−1/2⟺c≥λmax(A−1/2BA−1/2). The matrix A−1/2BA−1/2 is PSD and similar to A−1B, so its largest eigenvalue is ρ(A−1B). This generalized eigenvalue is a quick test for A⪰B: it holds exactly when ρ(A−1B)≤1 (H&J 7.7.3).

    Problem 7.7.P44Inverses reverse the order, from the definition

    If A⪰B≻O, prove B−1⪰A−1 directly: show x⊤B−1x≥x⊤A−1x for every x, starting from (y−B−1x)⊤B(y−B−1x)≥0.

    Hint

    Expand the square, use A⪰B on the y⊤By term, then choose y=A−1x.

    Solution

    Expanding, y⊤By−2y⊤x+x⊤B−1x≥0, i.e. x⊤B−1x≥2y⊤x−y⊤By≥2y⊤x−y⊤Ay, the last step because y⊤Ay≥y⊤By. With y=A−1x the right side is 2x⊤A−1x−x⊤A−1x=x⊤A−1x. This is a second proof of 2025 P1(5), and it needs no square roots at all: a good one to have if you blank on the congruence argument.

    Problem 7.7.P45One block matrix, two Schur complements

    For A,B≻O, let H=(B−1IIA). Compute the Schur complements of B−1 and of A in H, and explain why A⪰B⟺H⪰O⟺B−1⪰A−1.

    Hint

    If P≻O, then (PQQ⊤R)⪰O if and only if R−Q⊤P−1Q⪰O.

    Solution

    H/B−1=A−IBI=A−B and H/A=B−1−IA−1I=B−1−A−1. The hint follows from the congruence (I0−Q⊤P−1I)(PQQ⊤R)(I−P−1Q0I)=(P00R−Q⊤P−1Q). Applying it with either diagonal block as the pivot gives A−B⪰O⟺H⪰O⟺B−1−A−1⪰O. A third proof of 2025 P1(5), and the standard way this fact is used in semidefinite programming.

    Simulation2020 P4, 2023 P2, 2025 P2, 2026 P3; Strogatz §§2.5, 6.3–6.5, 7.2

    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

    Equilibria (Strogatz §6.3). For x˙=F(x), the constant solutions are exactly the zeros of F. With uniqueness of solutions assumed, "x(t)=x(0) for all t" is the same as F(x(0))=0. Near an equilibrium, the eigenvalues of the Jacobian classify it (node, saddle, spiral), except in borderline cases such as centers.
    Lyapunov functions (Strogatz §7.2, which spells it Liapunov). If L is minimized at an equilibrium x∗ and ddtL(x(t))=∇L⋅F<0 away from x∗, solutions are drawn toward x∗. For Lotka–Volterra systems x˙i=xi(vi+(Ax)i), Volterra's choice L=∑ci(xi−xi∗log⁡xi)+const gives L˙=12z⊤(CA+A⊤C)z with z=x−x∗.
    Conserved quantities from dy/dx (Strogatz §6.5). In the plane, dividing the equations gives dy/dx=y˙/x˙. If that separates or is exact, integrating gives H(x,y)=const along solutions, and the trajectories are level sets of H. If an isolated equilibrium is a local minimum of H, nearby orbits are closed (Strogatz Theorem 6.5.1).
    Comparison and blow-up (Strogatz §2.5). If x˙≥x2 and x(0)=1, then ddt(−1/x)≥1, so x(t)≥1/(1−t): the solution leaves every bounded set before t=1.
    Linear equations on a circle or interval. Constant-coefficient linear equations are diagonalized by Fourier modes. On Z/NZ, e2πimn/N is an eigenvector of the second difference with eigenvalue −4sin2⁡(πm/N). On (0,L) with zero-flux (Neumann) ends, cos⁡(kπx/L) is an eigenfunction of ∂x2 with eigenvalue −(kπ/L)2. Every nonzero mode decays; the mean (mode 0) survives.

    Gradient flows. The Allen–Cahn equation ut=u−u3+uxx is the steepest descent of the energy H(u)=∫(14u4−12u2+12ux2)dx: a double well that prefers u=±1, plus a penalty on gradients. That structure is why H never increases (2025 P2(1)), and it is the picture to draw in (4). For more on gradient flows, see the Gradient Flows page.

    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 x˙=x2, 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

    x˙=−2xy, y˙=2xy−y (2026 P3). Read x as the susceptible and y as the infected fraction. trajectory equilibria y=0 x=12. Faint curves are level sets of H=x+y−12log⁡x. Drag the dot.
    Starting point
    Jump to

    Explore: phase separation

    Equation
    Initial data
    Space–time picture: x across, time down. u≈+1 u≈−1; pale means mixed (u≈0).
    The profile u(t,⋅) now, between −1 and 1.

    Worked example

    2026 P3(3): start with x(0),y(0)>0, x(0)+y(0)=1. Can limt→∞x(t) lie in [12,1)?

    1. Find a conserved quantity.

      dydx=2xy−y−2xy=−1+12x, so y=−x+12log⁡x+const. Check: H=x+y−12log⁡x has H˙=−2xy+(2xy−y)−12⋅−2xyx=0.

    2. Show the limits x∞, y∞ exist, with y∞=0 and x∞>0.

      From (2), x,y>0, so x strictly decreases and is bounded below: x∞ exists. x+y decreases (ddt(x+y)=−y) and is bounded below, so it has a limit and ∫0∞ydt=1−lim(x+y)<∞; with y converging (as the difference of convergent functions), y∞=0. Finally log⁡x(t)=log⁡x(0)−2∫0ty, which stays bounded, so x∞>0.

    3. Use H to locate x∞.

      Let g(x)=x−12log⁡x, which decreases on (0,12] and increases on [12,∞). Conservation gives g(x∞)=H(x(0),y(0))=g(x(0))+y(0)>g(x(0)). If x∞≥12, then 12≤x∞<x(0) and g increasing there gives g(x∞)<g(x(0)), a contradiction. So x∞<12 always, and no such solution exists.

      In epidemic terms, x=12 is the herd-immunity threshold (R0=2); the outbreak always overshoots it. Drag the starting point above to watch this.

    Check your understanding

    Along solutions of x˙=−2xy, y˙=2xy−y with x>0, which quantity is constant?

    1. x+yddt(x+y)=−y, which is why x+y≤1 in (2).
    2. x+y−12log⁡x
    3. xyddt(xy)=xy(2x−2y−1), not zero in general.
    Integrate dy/dx=−1+1/(2x). The level sets of this H are the trajectories in the figure.

    Linearize ut=u−u3+uxx at u=0 on (0,L) with zero-flux ends. When does the mode cos⁡(kπx/L) grow?

    1. When (kπ/L)2<1
    2. Always: the reaction term pushes away from 0Diffusion damps short waves at rate (kπ/L)2, which can beat the reaction's rate 1.
    3. Never: diffusion smooths everythingMode 0 (and other long waves) grow at rate 1−(kπ/L)2>0.
    The linearization is ut=u+uxx, with growth rate 1−(kπ/L)2. Long waves grow and short ones die, which is why small noise first turns into a few broad bumps. If L<π, only the mean grows.

    If x˙≥x2 and x(0)=1, what can you conclude?

    1. x blows up at some T≤1.
    2. x grows at least exponentially, but exists for all time.Compare with u˙=u2, whose solution 1/(1−t) blows up at 1.
    3. Nothing without an upper bound on x˙.A lower bound is exactly what forces blow-up.
    ddt(1/x)=−x˙/x2≤−1, so 1/x(t)≤1−t. This is the last step of 2026 P3(4).
    Practice2020 P4, 2023 P2, 2025 P2, 2026 P3; Strogatz §§2.5, 6.3–6.5, 7.2

    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

    ∂tx(n,t)=x(n−1,t)+x(n+1,t)−2x(n,t) for integers n, with x(n+N,t)=x(n,t), N≥3. Let e(m,n)=e2πimn/N. (1) If x(n,t)=e(m,n)fm(t) is a solution with fm(0)=cm, find fm. (2) Solve with x(n,0)=gn, n=0,…,N−1. (3) Find limt→∞x(n,t).

    Hint

    e(m,n±1)=e(m,n)e±2πim/N. For (2), expand g in the discrete Fourier basis.

    Solution

    (1) Substituting, fm′=(e−2πim/N+e2πim/N−2)fm=−4sin2⁡(πm/N)fm, so fm(t)=cme−4sin2⁡(πm/N)t. Periodicity holds because e(m,n+N)=e(m,n).

    (2) By orthogonality ∑n=0N−1e(m,n)e(m′,n)―=Nδmm′, gn=∑m=0N−1cme(m,n) with cm=1N∑n=0N−1gne−2πimn/N. By linearity, x(n,t)=∑m=0N−1cme2πimn/Ne−4sin2⁡(πm/N)t. (It satisfies (*), (**), and the initial condition; uniqueness for this linear ODE system makes it the solution.)

    (3) For 1≤m≤N−1, sin2⁡(πm/N)>0, so those terms vanish. The limit is c0=1N∑ngn, the average of the initial values, for every n.

    2023 Problem 2Stability of a Lotka–Volterra system

    A is a real nonsingular n×n matrix, Fi(x)=xi(vi+∑jaijxj) on the positive orthant, and x∗ is a positive equilibrium. Consider x˙=F(x). (1) For c>0 and L(x)=∑ici[xi∗log⁡(xi∗/xi)−xi∗+xi], show L˙(x′)<0 for every positive x′≠x∗ if and only if CA+A⊤C is negative definite (C=diag(c)). (2) With Hw(z)=12∑wizi2 and z=x−x∗, find G(z) with z˙=G(z)∇Hw(z), in terms of A, W, X∗, Z. (3) If such a c exists, find w>0 so that ddtHw(z(t))<0 whenever z(t) is in a punctured neighbourhood of 0.

    Hint

    Use vi=−∑jaijxj∗ to rewrite Fi=xi(Az)i. In (3), choose W so that WX∗=C.

    Solution

    (1) ∂L/∂xi=ci(1−xi∗/xi)=cizi/xi and Fi=xi(Az)i, so L˙=∑icizi(Az)i=z⊤CAz=12z⊤(CA+A⊤C)z. As x′ ranges over positive vectors other than x∗, z ranges over a set containing a punctured ball around 0. A quadratic form is negative on a punctured ball if and only if it is negative definite (scale any nonzero vector into the ball); and negative definiteness gives L˙<0 for every z≠0.

    (2) z˙i=x˙i=(xi∗+zi)(Az)i, and ∇Hw=Wz, so z=W−1∇Hw. Hence G(z)=(X∗+Z)AW−1.

    (3) Take wi=ci/xi∗, so W=C(X∗)−1. Then ddtHw=∇Hw⊤G∇Hw=z⊤W(X∗+Z)Az=z⊤CAz+z⊤C(X∗)−1ZAz. The first term is ≤−μ‖z‖2 with μ>0 (half the smallest eigenvalue of −(CA+A⊤C)); the second is O(‖z‖3). So the derivative is negative for small z≠0.

    2025 Problem 2Allen–Cahn and phase separation

    (A): ut=u−u3+uxx on 0<x<L, ux(t,0)=ux(t,L)=0, u(0,x)=f(x) with sup|f|<1. (1) Show H(u)=∫0L(14u4−12u2+12ux2)dx is non-increasing in t. (2) For (B) ut=uxx with the same boundary and initial conditions, write u=∑kbkecktcos⁡(kπx/L); find bk,ck and the limit as t→∞. (3) Solve (C) v′=v−v3, v(0)=a, |a|<1, and find the limit. (4) (i) Explain how (B), (C) and the monotonicity of H bear on modelling phase separation. (ii) Sketch the evolution for |f|≪1.

    Hint

    (1) Differentiate under the integral and integrate uxuxt by parts. (3) Separate variables; partial fractions in 1/(v−v3), or solve for v2.

    Solution

    (1) dHdt=∫0L((u3−u)ut+uxuxt)dx=∫0L(u3−u−uxx)utdx+[uxut]0L=−∫0Lut2dx≤0, since the boundary term vanishes by the Neumann condition.

    (2) Each term must solve (B): ck=−(kπ/L)2. Matching t=0 with the cosine series: b0=1L∫0Lf, bk=2L∫0Lf(x)cos⁡(kπx/L)dx for k≥1. As t→∞, u→b0, the mean of f.

    (3) ddt(v−2)=−2v′/v3=2−2v−2 (for a≠0), so v−2−1=(a−2−1)e−2t, giving v(t)=aet1−a2+a2e2t (also valid for a=0). The limit is 1 if a>0, −1 if a<0, 0 if a=0.

    (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 ±1 (0 is unstable), producing noise-scale fragments. In (A) they compete: H is a double-well energy minimized by u=±1 plus a gradient cost, and the dynamics only lowers it, so the system settles into large regions of pure phase separated by thin smooth interfaces whose number is penalized by the gradient term. (ii) For |f|≪1: an early linear stage where long-wave modes with (kπ/L)2<1 grow like e(1−(kπ/L)2)t and short ones decay; then saturation into plateaus at ±1 joined by tanh-shaped interfaces of width about 2; then very slow coarsening as nearby interfaces annihilate (exponentially slow in one dimension). The space–time figure above is that sketch.

    2026 Problem 3An epidemic-type system

    x˙=−2xy, y˙=2xy−y, solutions unique and smooth. (1) Find every initial point for which the solution is constant. (2) If x(0),y(0)>0 and x(0)+y(0)=1, show x,y≥0 and x+y≤1 for t≥0. (3) Under (2), can 12≤limx(t)<1? (4) From (1,−1), show x(t)→∞ as t↑T for some finite T>0.

    Hint

    (2) Write x(t)=x(0)exp⁡(−2∫0ty). (4) On the conserved level through (1,−1), express y in terms of x and compare with x˙≥x2.

    Solution

    (1) −2xy=0 and y(2x−1)=0. If y≠0 the first forces x=0, and then the second gives −y=0, a contradiction. So y=0, and any x works: the constant solutions start at (c,0), c∈R.

    (2) x(t)=x(0)e−2∫0ty>0 and y(t)=y(0)e∫0t(2x−1)>0. Then ddt(x+y)=−y≤0, so x+y≤1.

    (3) No; see the worked example: limx(t)<12 always.

    (4) y(t)=−e∫0t(2x−1)<0 for all t, so x˙=−2xy>0 while x>0: x increases from 1. H=x+y−12log⁡x equals 0 at (1,−1), so y=12log⁡x−x and x˙=x(2x−log⁡x). Since log⁡x≤x−1, 2x−log⁡x≥x+1>x, so x˙>x2 with x(0)=1, and x(t)≥1/(1−t). Hence the solution cannot exist on [0,1) with x finite: there is T≤1 with x(t)→∞ as t↑T. In fact T=∫1∞dxx(2x−log⁡x)≈0.5735.

    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 x≥0 and sick y≥0 evolve by x˙=−kxy, y˙=kxy−ℓy with k,ℓ>0. (a) Find and classify the fixed points. (b) Sketch nullclines and the vector field. (c) Find a conserved quantity. (d) What happens as t→∞? (e) An epidemic occurs if y increases at first. When does that happen?

    Hint

    (c) Form dy/dx and separate variables. With k=2, ℓ=1 this is the exam's system.

    Solution

    (a) kxy=0 and y(kx−ℓ)=0 force y=0: every point (x∗,0) is fixed, a whole line of them. The Jacobian there is (0−kx∗0kx∗−ℓ), with eigenvalues 0 (along the line) and kx∗−ℓ. Points with x∗<ℓ/k attract nearby trajectories; points with x∗>ℓ/k repel them. Being non-isolated, none is a node or saddle in the usual sense.

    (b) x˙=0 on the axes; y˙=0 on y=0 and on the vertical line x=ℓ/k. In the open quadrant x always decreases, and y rises to the right of x=ℓ/k and falls to the left.

    (c) dy/dx=−1+ℓ/(kx), so E=kx+ky−ℓlog⁡x is conserved.

    (d) Every trajectory in the open quadrant ends on the line of fixed points at some x∞<ℓ/k, with y→0: the argument of the worked example, with ℓ/k in place of 12.

    (e) y˙(0)=y0(kx0−ℓ)>0 exactly when x0>ℓ/k: the epidemic threshold. In the exam's units, ℓ/k=12, which is why the gold line in the figure sits at x=12, and why 2026 P3(3) asks about [12,1).

    Exercise 2.5.2Blow-up without an exact solution

    Show that every solution of x˙=1+x10 escapes to +∞ in finite time.

    Hint

    Don't solve it. Compare with x˙=1+x2, whose solutions are shifted tangents.

    Solution

    Since x˙≥1, x reaches the value 1 by time t1=max(0,1−x0). From then on x≥1, so x10≥x2 and x˙≥1+x2, i.e. ddtarctan⁡x≥1. Hence arctan⁡x(t)≥π4+(t−t1), which reaches π2 by t=t1+π4: x must blow up before then. This is the same comparison as 2026 P3(4), where x˙=x(2x−log⁡x)≥x2.

    Exercise 6.4.1Two competing species

    For x˙=x(3−x−y), y˙=y(2−x−y) with x,y≥0, find and classify the fixed points and describe the long-run behaviour.

    Hint

    Look at ddtlog⁡(x/y).

    Solution

    Fixed points: (0,0), (3,0), (0,2); an interior one would need x+y=3 and x+y=2 at once. The Jacobian is (3−2x−y−x−y2−x−2y). At (0,0): eigenvalues 3, 2, an unstable node. At (3,0): (−3−30−1), eigenvalues −3,−1, a stable node. At (0,2): (10−2−2), eigenvalues 1,−2, a saddle.

    Globally, for x,y>0, ddtlog⁡(x/y)=(3−x−y)−(2−x−y)=1, so y/x→0 exponentially: y is driven out and every trajectory with x(0)>0 tends to (3,0). (Competitive exclusion; 2023 P2 is the general Lotka–Volterra system, where Volterra's function L plays the role this ratio plays here.)

    Exercise 7.2.10A Lyapunov function rules out cycles

    Show that x˙=y−x3, y˙=−x−y3 has no closed orbits, by finding V=ax2+by2 that decreases along trajectories.

    Solution

    V˙=2ax(y−x3)+2by(−x−y3)=2(a−b)xy−2ax4−2by4. With a=b=1 the cross term cancels and V˙=−2(x4+y4)<0 away from the origin. On a closed orbit V would return to its starting value after one period, but it strictly decreases: impossible. In fact the origin is globally asymptotically stable. Note that linearization alone says nothing here: the Jacobian at the origin has eigenvalues ±i.

    Exercise 7.2.11When is a quadratic form a valid Lyapunov candidate?

    Show that V=ax2+2bxy+cy2 is positive definite if and only if a>0 and ac−b2>0.

    Solution

    If a≤0, V(1,0)=a≤0. If a>0, complete the square: V=a(x+bay)2+ac−b2ay2, positive for all (x,y)≠0 exactly when ac−b2>0. This is the 2×2 case of the leading-minor test for (abbc)≻O, the matrix fact behind 2023 P2(1) (see the symmetric matrices topic).

    Interactive2024 P2; also 2024 P1, 2026 P1; Boyd and Vandenberghe Ch. 2, 3, 5, 8

    Optimization and acceleration

    Convergence proofs for first-order methods follow one template: write down an energy that mixes the gap f(x)−f∗ with a distance to the optimum, show it never increases, and read off the rate from the weight on the gap. 2024 P2 does exactly this, first in continuous time and then for a discretization.

    The idea

    Convexity, first order (BV (3.2), §3.1.3). A differentiable f is convex if and only if f(y)≥f(x)+∇f(x)⊤(y−x) for all x,y. With y=x∗: f(x)−f∗≤∇f(x)⊤(x−x∗). This single inequality closes most rate proofs.
    Rates. For convex f with L-Lipschitz gradient, gradient descent with step 1/L has f(xk)−f∗≤L‖x0−x∗‖2/(2k). Nesterov's accelerated method, yk=xk+k−1k+2(xk−xk−1), xk+1=yk−1L∇f(yk), achieves O(1/k2), which is optimal for first-order methods in this class.

    The continuous-time picture. Letting the step size shrink, Nesterov's method tracks x¨+3tx˙+∇f(x)=0 (Su, Boyd and Candès). 2024 P2 writes a shifted version as a first-order system in (x,v) with x˙=2t+1(v−x) and v˙=−t+12∇f(x), and the energy E(t)=(t+1)2(f(x)−f∗)+2‖v−x∗‖2. The growing weight (t+1)2 on the gap is the rate.

    Discrete energies. For sequences, δ+y(k)=(y(k+1)−y(k))/h obeys a product rule δ+(a(k)b(k))=(δ+a(k))b(k+1)+a(k)δ+b(k) and δ+‖y(k)‖2=2y(k+1)⊤δ+y(k)−h‖δ+y(k)‖2. The extra −h‖⋅‖2 is a gift: it has the right sign.
    Proximal gradient. For f+g with f smooth and g convex but maybe not smooth, iterate xk+1=proxγg(xk−γ∇f(xk)), where proxγg(y)=arg⁡minu(g(u)+12γ‖u−y‖2). For g=λ‖⋅‖1 the prox is soft-thresholding; for g the indicator of a convex set it is the projection (for the PSD cone, the ϕ of 2026 P1, which Boyd and Vandenberghe state in §8.1.1, p. 399).
    Linear programming duality (BV §5.2.1, Exercise 5.23). For max{c⊤x:Ax≤b, x≥0} the dual is min{b⊤y:A⊤y≥c, y≥0}. Weak duality c⊤x≤b⊤y is one line; strong duality says the optima are equal when either is finite, and complementary slackness y⊤(b−Ax)=0=x⊤(A⊤y−c) characterizes optimal pairs. The max-flow min-cut theorem and the minimum-cost flow optimality conditions are special cases.

    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 1/k to 1/k2, 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

    gradient descent (dashed, a dot every 10 steps) Nesterov, both with step 1/L. Drag the start.
    f(xk)−f∗ against k on log–log axes. Dashed guides have slopes −1 and −2.

    Worked example

    2024 P2(1): show E˙≤0 for E(t)=(t+1)2(f(x)−f∗)+2‖v−x∗‖2, then deduce f(x(t))−f∗≤C/t2.

    1. Differentiate each term of E.

      E˙=2(t+1)(f−f∗)+(t+1)2∇f⊤x˙+4(v−x∗)⊤v˙.

    2. Substitute the dynamics.

      (t+1)2∇f⊤x˙=2(t+1)∇f⊤(v−x) and 4(v−x∗)⊤v˙=−2(t+1)∇f⊤(v−x∗). The v terms cancel: E˙=2(t+1)[f(x)−f∗−∇f(x)⊤(x−x∗)].

    3. Finish with convexity.

      The bracket is ≤0 by f∗≥f(x)+∇f(x)⊤(x∗−x). So E(t)≤E(0), and f(x(t))−f∗≤E(0)/(t+1)2≤E(0)/t2: take C=E(0)=f(x(0))−f∗+2‖v(0)−x∗‖2.

    Check your understanding

    In the proof above, which property of f was used?

    1. Convexity, in the form f(x∗)≥f(x)+∇f(x)⊤(x∗−x)
    2. Strong convexityNot assumed; with it you would get a linear rate.
    3. A Lipschitz gradientNeeded for discrete step-size choices in general, but not in the continuous-time argument.
    The energy method needs only that one inequality. In the discrete part (2), convexity is used twice: once between x(k) and x(k+1), once between x(k+1) and x∗.

    What is the guaranteed rate of plain gradient descent (step 1/L) on an L-smooth convex function?

    1. O(1/k)
    2. O(1/k2)That is the accelerated rate.
    3. Linear, O(ρk)Only with strong convexity, and then the rate depends on the condition number: compare large and small κ in the figure.
    Without strong convexity the gap decays like 1/k for gradient descent and 1/k2 for Nesterov, and no first-order method can beat 1/k2 in general.

    What is proxγλ|⋅|(y) for y∈R?

    1. sign(y)max(|y|−γλ,0)
    2. y/(1+γλ)That is the prox of λ2y2.
    3. max(y,0)That is projection onto [0,∞), the prox of its indicator.
    Minimize λ|u|+12γ(u−y)2: the optimality condition 0∈λ∂|u|+(u−y)/γ gives soft-thresholding. Proximal gradient with this prox is ISTA for the lasso.
    Practice2024 P2; also 2024 P1, 2026 P1; Boyd and Vandenberghe Ch. 2, 3, 5, 8

    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

    f is smooth and convex on Rd with a minimizer x∗. (1) For the system above, show E˙≤0 and f(x(t))−f∗≤C/t2. (2) Discretize as δ+x(k)=2hk+h+2(hk+1)2(v(k+1)−x(k+1)), δ+v(k)=−2hk+h+24∇f(x(k+1)), with E(k)=(hk+1)2(f(x(k))−f∗)+2‖v(k)−x∗‖2. Show δ+‖v(k)−x∗‖2=2(v(k+1)−x∗)⊤δ+v(k)−h‖δ+v(k)‖2 and δ+E(k)≤0. (3) Show f(x(k))−f∗≤C′/k2.

    Hint

    Write sk=2hk+h+2 and Ak=(hk+1)2. Then δ+Ak=sk: the coefficient in the scheme is the discrete derivative of the weight. Use the product rule with a=A, b=f(x(k))−f∗.

    Solution

    (1) The worked example.

    (2) With a=v(k+1)−x∗, b=v(k)−x∗: ‖a‖2−‖b‖2=2a⊤(a−b)−‖a−b‖2. Divide by h and use a−b=hδ+v(k).

    Now (h(k+1)+1)2−(hk+1)2=h(2hk+h+2), so δ+Ak=sk. Write Dk=f(x(k))−f∗ and g=∇f(x(k+1)). The product rule gives δ+E(k)=skDk+1+Akδ+Dk+4(v(k+1)−x∗)⊤δ+v(k)−2h‖δ+v(k)‖2.

    • Convexity between x(k) and x(k+1): f(x(k))≥f(x(k+1))+g⊤(x(k)−x(k+1)), so δ+Dk≤g⊤δ+x(k)=skAkg⊤(v(k+1)−x(k+1)).
    • The v update: 4(v(k+1)−x∗)⊤δ+v(k)=−skg⊤(v(k+1)−x∗).

    Adding, the v(k+1) terms cancel: δ+E(k)≤sk[f(x(k+1))−f∗−g⊤(x(k+1)−x∗)]−2h‖δ+v(k)‖2≤0, by convexity between x(k+1) and x∗.

    (3) E(k)≤E(0), so f(x(k))−f∗≤E(0)/(hk+1)2≤E(0)/(h2k2). Take C′=E(0)/h2.

    Fresh practiceThe dual of a transportation LP

    Supplies ai≥0 at sources i, demands bj≥0 at sinks j with ∑ai=∑bj, and costs cij. Write the LP for the cheapest shipment xij≥0, its dual, and the complementary slackness conditions. Interpret the dual variables.

    Solution

    Primal: minimize ∑cijxij subject to ∑jxij=ai, ∑ixij=bj, x≥0. Dual: maximize ∑iaiui+∑jbjvj subject to ui+vj≤cij (free u,v, because the primal constraints are equalities). Complementary slackness: xij>0⇒ui+vj=cij. Read −ui as the price paid to pick up a unit at i and vj as the price it fetches at j: goods only travel on routes where the price difference exactly covers the cost. This is the 1D picture behind optimal transport and the minimum-cost flow optimality conditions.

    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 C⊆Rn be nonempty, closed and convex. Show that every x0 has exactly one nearest point of C in the Euclidean norm.

    Hint

    Existence: compactness. Uniqueness: the midpoint of two nearest points, and the parallelogram law.

    Solution

    Pick any c∈C. The nearest point, if any, lies in C∩{x:‖x−x0‖≤‖c−x0‖}, which is closed and bounded, hence compact, and ‖x−x0‖ is continuous: a minimizer exists. If x≠y both attain the minimum distance d, then m=x+y2∈C by convexity, and the parallelogram law gives ‖m−x0‖2=d2+d22−‖x−y‖24<d2, a contradiction. With matrices and ⟨A,B⟩=tr(AB) in place of Rn, this is the existence and uniqueness half of 2026 P1(2).

    Exercise 8.3 (a, b)Projections onto the orthant and the PSD cone

    (a) Show that the Euclidean projection of x0 onto R+n replaces each negative entry by 0. (b) Show that the Frobenius projection of a symmetric X0=∑iλivivi⊤ onto the PSD cone is ∑imax(λi,0)vivi⊤.

    Hint

    (a) The problem separates coordinate by coordinate. (b) The Frobenius norm doesn't change under X↦Q⊤XQ with Q orthogonal; reduce to (a) on the diagonal.

    Solution

    (a) ‖x−x0‖2=∑k(xk−x0k)2, and each term is minimized over xk≥0 at xk=max(x0k,0). (b) Exactly the argument of 2026 P1(2): in the eigenbasis of X0, off-diagonal entries only add to the distance and the diagonal is problem (a). Part (a) also explains the variational inequality there: x0−P(x0) is the negative part of x0, which is orthogonal to P(x0) and has non-positive inner product with every point of the orthant.

    Exercise 2.28The PSD cone in coordinates

    Describe S+n by inequalities on the entries for n=1,2,3, writing a general element as x1, (x1x2x2x3) and (x1x2x3x2x4x5x3x5x6).

    Hint

    A symmetric matrix is PSD if and only if all principal minors are non-negative (leading ones are not enough for semidefiniteness).

    Solution

    n=1: x1≥0. n=2: x1≥0, x3≥0, x1x3≥x22. n=3: x1,x4,x6≥0; x1x4≥x22, x1x6≥x32, x4x6≥x52; and det≥0. For n=2 the cone is a round cone in (x1,x2,x3)-space (x1x3≥x22 with x1+x3≥0), which is why the ellipse picture in the symmetric matrices topic works: each interior point of this cone is an ellipse. Only checking the leading minors x1≥0, x1x3−x22≥0 would wrongly admit diag(0,−1).

    Exercise 5.4The LP dual as the best bound from a single inequality

    For the LP min{c⊤x:Ax⪯b} and any w⪰0, every feasible x satisfies w⊤Ax≤w⊤b. (a) Find min{c⊤x:w⊤Ax≤w⊤b}. (b) Write the problem of choosing w to make this lower bound as large as possible. (c) Compare with the Lagrange dual.

    Solution

    (a) Minimizing a linear function over a half-space is −∞ unless c points out of it: unless c=−λA⊤w for some λ≥0. Then c⊤x=−λw⊤Ax≥−λw⊤b, with equality on the boundary, so the minimum is −λw⊤b. (b) Maximize −λw⊤b over w⪰0, λ≥0 with c=−λA⊤w. (c) Put z=λw: maximize −b⊤z subject to A⊤z+c=0, z⪰0. That is the Lagrange dual (BV (5.22)). Duality is "the best lower bound you can get by adding up constraints with non-negative weights".

    Exercise 5.5The dual of a general LP

    Find the dual function and dual problem of min{c⊤x:Gx⪯h, Ax=b}, with the implicit constraints made explicit.

    Solution

    L(x,λ,ν)=c⊤x+λ⊤(Gx−h)+ν⊤(Ax−b)=(c+G⊤λ+A⊤ν)⊤x−h⊤λ−b⊤ν. Minimizing over x: g(λ,ν)=−h⊤λ−b⊤ν if c+G⊤λ+A⊤ν=0, and −∞ otherwise. Dual: maximize −h⊤λ−b⊤ν subject to G⊤λ+A⊤ν+c=0, λ⪰0. Inequality constraints get sign-constrained multipliers; equalities get free ones, which is the pattern behind the transportation dual above.

    InteractiveRudin, Ch. 7: Sequences and Series of Functions

    Uniform convergence

    Pointwise limits of continuous functions can be discontinuous. Uniform convergence is the fix, and it is just convergence in the metric d(f,g)=sup|f−g|: the story of continuity, applied to a space whose points are functions.

    The idea

    Pointwise vs uniform (Rudin 7.1, 7.7). fn→f pointwise if fn(x)→f(x) for each x (the N may depend on x). Uniformly if for every ε one N works for all x: equivalently supx|fn(x)−f(x)|→0 (Rudin 7.9).
    Uniform limits keep continuity (Rudin 7.12). If continuous fn→f uniformly, f is continuous. Uniform limits also commute with integrals (Rudin 7.16), but not with derivatives without more hypotheses (Rudin 7.17).

    In the language of the story: C([a,b]) with the sup metric is a complete metric space (Rudin 7.15), and the Weierstrass theorem (Rudin 7.26) says polynomials are dense in it. Pointwise convergence, by contrast, is convergence in a topology that comes from no metric.

    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 xn on [0,1] 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

    Sequence fn
    The limit f in ink, with an ε-tube around it. fn is in blue where it stays in the tube and red where it leaves.

    Worked example

    Prove Rudin 7.12: a uniform limit of continuous functions is continuous.

    1. Fix p and ε. Which n do you use?

      One with sup|fn−f|<ε/3. This is where uniformity matters: the same n is good at p and at every nearby x.

    2. Now use continuity of that fn at p.

      Pick δ with |fn(x)−fn(p)|<ε/3 when |x−p|<δ. Then |f(x)−f(p)|≤|f(x)−fn(x)|+|fn(x)−fn(p)|+|fn(p)−f(p)|<ε. This "ε/3 argument" is the template for many proofs in analysis.

    Examples

    Example 7.1 (a discontinuous limit).

    xn on [0,1] converges pointwise to the function that is 0 on [0,1) and 1 at 1. The limit is discontinuous, so the convergence cannot be uniform: supx<1xn=1 for every n.

    Example 7.2 (uniform on bounded sets only).

    x/n→0 uniformly on every bounded interval but not on R, where sup|x/n|=∞. Many convergence statements are uniform only on compact sets.

    Example 7.3 (limits and integrals disagree).

    fn(x)=2n2xe−n2x2 tends to 0 at every x∈[0,1], but ∫01fn=1−e−n2→1. The bump escapes towards 0, which uniform convergence would forbid.

    Example 7.4 (the M-test).

    ∑n2−ncos⁡(3nx) converges uniformly by comparison with ∑2−n, so it is continuous; by Hardy's theorem it is differentiable nowhere. Uniform limits keep continuity but not differentiability.

    Check your understanding

    fn(x)=xn on [0,1] converges pointwise to f with f(1)=1 and f=0 elsewhere. Is the convergence uniform?

    1. Yes, since each fn is continuous.Continuity of the fn doesn't force uniform convergence.
    2. No: a uniform limit of continuous functions would be continuous.
    Rudin 7.12 in reverse: f is discontinuous at 1, so the convergence can't be uniform. Directly, sup[0,1)xn=1 for every n. On [0,0.9] it is uniform, with sup=0.9n.

    fn(x)=nxe−nx on [0,∞) tends to 0 pointwise. Then supxfn(x)

    1. tends to 0.Look at x=1/n.
    2. equals 1/e for every n.
    The maximum is at x=1/n with value e−1. The bump slides toward 0 and never shrinks: pointwise but not uniform convergence, even though the limit is continuous.

    Practice

    Exercise 7.1The Weierstrass M-test (Rudin 7.10)

    Show that ∑n≥1sin⁡(nx)n2 converges uniformly on R to a continuous function.

    Solution

    |sin⁡(nx)/n2|≤1/n2 and ∑1/n2<∞. The partial sums are uniformly Cauchy: supx|∑k=mn…|≤∑k=mn1/k2→0. So they converge uniformly, and the limit is continuous by Rudin 7.12.

    Exercise 7.2Limits and integrals: when can you swap them?

    For fn(x)=n2xe−nx on [0,1], compute lim∫01fn and ∫01limfn.

    Solution

    fn→0 pointwise, so the second is 0. But ∫01n2xe−nxdx=∫0nue−udu→1. The convergence is not uniform (supfn=n/e), so Rudin 7.16 doesn't apply, and the swap fails.

    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 N from the uniform Cauchy condition, then handle the finitely many earlier functions separately.

    Solution

    Let fn→f uniformly on E. Choose N with |fn(x)−fN(x)|<1 for all n≥N and all x (the uniform Cauchy condition, Rudin 7.8). fN is bounded by some B, so |fn|<B+1 for n≥N. The finitely many f1,…,fN−1 are bounded by B1,…,BN−1. Then max(B+1,B1,…,BN−1) bounds all fn.

    Rudin 7.2Sums and products

    If fn→f and gn→g uniformly on E, prove fn+gn→f+g uniformly. If in addition the fn and gn are bounded, prove fngn→fg uniformly.

    Hint

    For the product, add and subtract fng and use Rudin 7.1.

    Solution

    Sums: sup|(fn+gn)−(f+g)|≤sup|fn−f|+sup|gn−g|→0.

    Products: by Rudin 7.1 there is B with |fn|,|gn|≤B, and then |f|,|g|≤B too. Then |fngn−fg|≤|fn||gn−g|+|g||fn−f|≤Bsup|gn−g|+Bsup|fn−f|→0.

    Without boundedness it fails: on R, fn=gn=x+1/n converge uniformly to x, but fngn−x2=2x/n+1/n2 is unbounded for each n.

    Rudin 7.9Uniform convergence and moving points

    Let fn be continuous and fn→f uniformly on E. Prove fn(xn)→f(x) whenever xn→x in E. Is the converse true?

    Hint

    Split |fn(xn)−f(x)| through f(xn), using that f is continuous (Rudin 7.12).

    Solution

    |fn(xn)−f(x)|≤|fn(xn)−f(xn)|+|f(xn)−f(x)|≤sup|fn−f|+|f(xn)−f(x)|. The first term tends to 0 by uniformity, the second by continuity of f.

    The converse fails. Take fn(x)=x/n on E=R. If xn→x, then fn(xn)=xn/n→0=f(x), since xn is bounded. But supR|x/n|=∞, so the convergence is not uniform. (On a compact E the converse is true: this condition is called continuous convergence.)

    Interactive2023 P1, 2023 P3, 2024 P3, 2025 P3; Stein and Shakarchi Ch. 2–3

    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

    Residue theorem (Stein–Shakarchi Ch. 3, Theorem 2.1 and its corollaries). If g is holomorphic inside and on a simple closed positively oriented curve Γ except for isolated poles zk inside, then ∮Γgdz=2πi∑kReszkg. At a simple pole of p/q with q(zk)=0≠q′(zk), the residue is p(zk)/q′(zk); at a pole of order n, use the derivative formula of Ch. 3, Theorem 1.4. The Cauchy inequalities (Ch. 2, Corollary 4.3), |f(n)(z0)|≤n!‖f‖C/Rn, bound Taylor coefficients by ‖f‖R−n, which is the other route to the trapezoid bound below.

    Parametrize the circle. On |z|=1, z=eiθ and dθ=−idz/z, so ∫02πf(eiθ)dθ=∮−izf(z)dz. Since zN−1zN−1 has simple poles of residue 1N at the N-th roots of unity, the equally weighted sum 2πN∑kf(e2πik/N) is also a contour integral. Subtracting the two and pushing the contour out to radius R<r gives an error of order R−N: the trapezoid rule converges geometrically for periodic analytic integrands.

    Trigonometric polynomials. Bernstein's inequality: a trigonometric polynomial t of degree n has ‖t′‖∞≤n‖t‖∞. So if f is approximated within c/n3 by degree-n ones, consecutive differences are O(n−3), their derivatives O(n−2), and the derivatives converge. Fast approximation implies smoothness (the converse direction to Jackson's theorem).
    Limits and derivatives. If tn→f uniformly and tn′→s uniformly with s continuous, then f is differentiable with f′=s. Proof: pass to the limit in tn(θ)−tn(0)=∫0θtn′, then use the fundamental theorem of calculus.
    Quantile functions. If f>0 is a density on (a,b) with distribution function F, then Q=F−1 satisfies Q′(u)=1/f(Q(u)), the mean is ∫01Q(u)du, and the median is Q(12). So "mean minus median" is ∫01/2(Q(12+v)+Q(12−v)−2Q(12))dv, which is positive whenever Q is strictly convex, i.e. whenever f is strictly decreasing.
    Exchanging limits. 2023 P1(3) takes n→∞ and then m→∞. Each limit is a Riemann sum of a continuous function; say so explicitly rather than exchanging silently.

    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 2πi. 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 1/(z−a) in its expansion there. At a simple pole of p/q it equals p/q′ 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 u, 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 (0,1).
    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

    log10⁡|I(f)−IN(f)| against N. A straight line on this plot is geometric convergence. actual error prediction (for 1/(a−z) the two coincide)
    Integrand on the unit circle

    Worked example

    2023 P3(4): show the constant 2π in |I(f)−IN(f)|≤2π‖f‖rN−1 cannot be improved, i.e. lim supN(rNsupf|I(f)−IN(f)|/‖f‖)=2π.

    1. Which simple f does the N-point rule get completely wrong?

      f(z)=zN. Its integral over the circle is I=∫02πeiNθdθ=0, but at every node zN=1, so IN=2π. The error is 2π.

    2. Compute the ratio for this f.

      ‖f‖=sup|z|<r|z|N=rN, so rN|I−IN|/‖f‖=2π. Hence the sup is at least 2π for every N.

    3. Combine with the upper bound.

      From (3), the quantity is at most 2πrN/(rN−1)→2π. With the lower bound 2π, the limsup (in fact the limit) is 2π.

    Check your understanding

    The N-point trapezoid rule on the circle is exact for zk exactly when:

    1. k is not a nonzero multiple of N
    2. |k|≤Nk=N is the worst case: error 2π.
    3. alwaysThe nodes can't tell zN from the constant 1.
    1N∑j=1Nωjk is 1 if N∣k and 0 otherwise. This aliasing is the whole error: for f=∑akzk, IN−I=2π∑m≥1amN, and |amN|≤‖f‖r−mN by Cauchy's estimate, which is another proof of the bound.

    If ‖f−tn‖≤c/n3 for trigonometric polynomials tn of degree n, what can you conclude?

    1. f is continuously differentiable
    2. f is analyticAnalyticity needs geometric rates ρn, not polynomial ones.
    3. Nothing beyond continuityBernstein's inequality converts the approximation rate into control of derivatives.
    This is 2024 P3. The same argument gives C1 from any rate n−2−ε: after multiplying by n it is still summable.

    A density is strictly decreasing on (a,b). How do its mean and median compare?

    1. mean > median
    2. mean < medianThe long tail is on the right.
    3. It depends on the density2025 P3(3) proves the strict inequality in general.
    Q′=1/f(Q) increases, so Q is strictly convex and its average exceeds its middle value. The converse needs more: 2025 P3(1) has mean 34 above median 23 for a density that isn't decreasing, which is why part (4) asks about every sub-interval.
    Practice2023 P1, 2023 P3, 2024 P3, 2025 P3; Stein and Shakarchi Ch. 2–3

    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 A={ai}i=1m, B={bj}j=1n, let f(A,B)=ln⁡(1m∑i1Ki) with Ki=1n∑je−|ai−bj|. (1) Show f≥0 and find when f=0. (2) Show f(A,C)≤f(A,B)+f(B,C). (3) With Am(s)={s+i/m}, Bn={j/n}, find h with g(s)=limmlimnf(Am(s),Bn)=ln⁡∫s1+sdzh(z). (4) Find the s minimizing g.

    Hint

    (2) e−|a−c|≥e−|a−b|e−|b−c| gives, for every j, 1KiAC≤e|ai−bj|KjBC. Average this over j with weights proportional to e−|ai−bj|. (4) h is symmetric about 12.

    Solution

    (1) 0<Ki≤1, so each 1/Ki≥1 and f≥ln⁡1=0. Equality needs every Ki=1, i.e. ai=bj for all i,j: all entries of A and B are one common number. Conversely that gives f=0.

    (2) Write KiAB, KjBC, KiAC for the three averages. For each j, KiAC=1p∑le−|ai−cl|≥e−|ai−bj|KjBC, so 1/KiAC≤e|ai−bj|/KjBC. Average over j with weights qj=e−|ai−bj|/(nKiAB), which sum to 1: 1KiAC≤∑jqje|ai−bj|KjBC=1KiAB⋅1n∑j1KjBC. Averaging over i gives ef(A,C)≤ef(A,B)ef(B,C).

    (3) As n→∞, Ki is a Riemann sum for h(ai)=∫01e−|ai−y|dy. Then the outer average is a Riemann sum for ∫01duh(s+u) (h is continuous and positive). So h(z)=2−e−z−ez−1 for 0≤z≤1, h(z)=(1−e−1)ez for z<0, and h(z)=(1−e−1)e1−z for z>1.

    (4) G(s)=∫ss+1dz/h(z) has G′(s)=1/h(s+1)−1/h(s). Since h(z)=h(1−z) and h strictly increases on (−∞,12], G′<0 for s<0 and G′>0 for s>0 (the endpoint closer to 12 has the larger h). The minimizer is s=0: the sequences overlap exactly.

    2023 Problem 3The trapezoid rule for analytic functions

    For r>1, f holomorphic on Dr={|z|<r}, ‖f‖=supDr|f|, I(f)=∫02πf(eiθ)dθ and IN(f)=2πN∑k=1Nf(e2πik/N). (1) Show I(f)=∮|z|=1−izf(z)dz. (2) Find the poles of gN[f](z)=−izN−1zN−1f(z) in Dr and the residues. (3) If ‖f‖<∞, show |I(f)−IN(f)|≤2π‖f‖/(rN−1). (4) Show the constant 2π is optimal.

    Hint

    (3) Express both I and IN as integrals over |z|=R for 1<R<r, subtract, and simplify 1z−zN−1zN−1.

    Solution

    (1) With z=eiθ, dz=izdθ, so dθ=−idz/z.

    (2) The poles are the zeros of zN−1, the roots of unity ωk=e2πik/N, all simple and inside Dr. Resωk=−iωkN−1f(ωk)NωkN−1=−iNf(ωk) (the pole is removable if f(ωk)=0).

    (3) Fix 1<R<r. By the residue theorem, ∮|z|=RgN=2πi∑k(−iN)f(ωk)=IN. The integrand −if/z has only the pole at 0, so (1) also holds on |z|=R. Subtracting, I−IN=∮|z|=R(−i)f(z)(1z−zN−1zN−1)dz=∮|z|=Rif(z)z(zN−1)dz. On |z|=R, |zN−1|≥RN−1, so |I−IN|≤2πR⋅‖f‖R(RN−1). Let R↑r.

    (4) The worked example.

    2024 Problem 3Fast approximation implies differentiability

    Tn is the set of functions θ↦P(eiθ) with P a complex polynomial of degree n. f is continuous and 2π-periodic, and for each n some tn∈Tn has ‖f−tn‖≤c/n3. (1) Show ‖tn+1−tn‖≤2c/n3. (2) Using completeness of C[0,2π] and ‖t′‖≤n‖t‖ for t∈Tn, show tn′ converges uniformly to a continuous periodic s. (3) Show f is differentiable on R.

    Solution

    (1) ‖tn+1−tn‖≤‖tn+1−f‖+‖f−tn‖≤c(n+1)3+cn3≤2cn3.

    (2) tn+1−tn comes from a polynomial of degree at most n+1, so Bernstein's inequality (which holds for degree at most n+1) gives ‖tn+1′−tn′‖≤(n+1)2cn3≤4cn2. For m>n, ‖tm′−tn′‖≤∑k≥n4c/k2→0: the sequence is Cauchy in the sup norm, so it converges uniformly to some continuous s. Each tn′ is 2π-periodic, hence so is s.

    (3) tn(θ)−tn(0)=∫0θtn′. Let n→∞, using uniform convergence on both sides: f(θ)=f(0)+∫0θs. Since s is continuous, f is differentiable with f′=s, on [0,2π] and then on R by periodicity.

    2025 Problem 3Mean versus median

    Fa,b is the set of continuous densities on (a,b) with inff>0. (1) For g∈F0,5/3 equal to 32x+12 on (0,13], −32x+32 on (13,23], 12 on (23,53), find the mean and median. (2) With Q=F−1, show the mean is ∫01Q. (3) If f is strictly decreasing, show mean > median. (4) If f′ is continuous and for every a<c<d<b the normalized restriction fcd has mean > median, show f is strictly decreasing.

    Solution

    (1) The three pieces have mass 14,14,12, so the CDF at 23 is 12: median 23. ∫xg over the pieces is 5108+13108+63108=34: mean 34.

    (2) F is C1 with F′=f>0, a bijection (a,b)→(0,1). Substituting x=Q(u), du=f(x)dx: ∫abxf(x)dx=∫01Q(u)du.

    (3) Q′(u)=1/f(Q(u)). As u increases, Q(u) increases and f(Q(u)) strictly decreases, so Q′ strictly increases: Q is strictly convex. Mean − median =∫01(Q(u)−Q(12))du=∫01/2(Q(12+v)+Q(12−v)−2Q(12))dv>0.

    (4) Contrapositive. Suppose f is not strictly decreasing. If f′(x0)>0 somewhere, then by continuity f′>0 on some [c,d], fcd is strictly increasing, and the mirror of (3) (Q strictly concave) gives mean < median. Otherwise f′≤0 everywhere, so f is non-increasing, and not being strictly decreasing means f(x)=f(y) for some x<y: f is constant on [x,y], and for c,d in there fcd is uniform with mean = median. Either way the hypothesis fails.

    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 ∫02πdθa+bcos⁡θ=2πa2−b2 whenever a>|b|, a,b real.

    Hint

    Substitute z=eiθ, so cos⁡θ=12(z+z−1) and dθ=−idz/z, as in 2023 P3(1).

    Solution

    For b=0 it is immediate. Otherwise the integral becomes ∮|z|=1−2idzbz2+2az+b. The roots z±=−a±a2−b2b are real with z+z−=1, and |z+|<1<|z−|. The residue at z+ is −2ib(z+−z−)=−2i2a2−b2, so the integral is 2πi⋅−ia2−b2=2πa2−b2.

    Connection to the figure above: the integrand is analytic in the annulus |z+|<|z|<1/|z+|, so the N-point trapezoid rule for it converges like |z+|N. The closer a is to |b|, the closer the poles are to the circle and the slower the convergence.

    Exercise 3.7Differentiate the previous answer

    Show that ∫02πdθ(a+cos⁡θ)2=2πa(a2−1)3/2 for a>1.

    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 b=1, F(a)=∫02πdθa+cos⁡θ=2π(a2−1)−1/2 for a>1. Differentiating under the integral (the integrand is smooth in a and bounded uniformly for a in compact subsets of (1,∞)): −∫02πdθ(a+cos⁡θ)2=F′(a)=−2πa(a2−1)−3/2. Differentiating under the integral sign, with a sentence of justification, is exactly the step 2023 P4(2) needs.

    Exercise 3.1The poles of 1/sin πz

    Using sin⁡πz=eiπz−e−iπz2i, show that the zeros of sin⁡πz are exactly the integers, each of order 1, and find the residue of 1/sin⁡πz at z=n.

    Solution

    sin⁡πz=0⟺e2πiz=1⟺z∈Z. The derivative πcos⁡πn=π(−1)n≠0, so each zero is simple, and the residue is 1πcos⁡πn=(−1)nπ (the p/q′ rule). The same rule gave the residues of gN[f] at the roots of unity in 2023 P3(2).

    Exercise 3.11An integral that vanishes by the mean-value property

    Show that ∫02πlog⁡|1−aeiθ|dθ=0 when |a|<1.

    Hint

    log⁡|1−az| is the real part of a function holomorphic on a disc of radius more than 1.

    Solution

    For |z|<1/|a|, 1−az lies in the disc of radius 1 about 1, where the principal logarithm is holomorphic; so f(z)=log⁡(1−az) is holomorphic there and Ref=log⁡|1−az|. The mean-value property (Ch. 3, Corollary 7.3) at z0=0, r=1 gives 12π∫02πlog⁡|1−aeiθ|dθ=log⁡|1−0|=0. The same principle (the average of a holomorphic or harmonic function over a circle is its value at the centre) is why I(f)=2πf(0) for every f in 2023 P3.

    SimulationApplebaum, Ch. 5: Discrete random variables

    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

    Random variable. A function X from the sample space to R. For discrete X, its law is p(x)=P(X=x) and its cumulative distribution is F(x)=P(X≤x).
    Mean and variance. E(X)=∑xxp(x) and Var(X)=E((X−μ)2)=E(X2)−E(X)2. Expectation is linear, Var(aX+b)=a2Var(X), and for independent X,Y, Var(X+Y)=Var(X)+Var(Y).

    Three laws that come up again and again:

    • Binomial b(n,p): the number of successes in n independent trials, p(k)=(nk)pk(1−p)n−k; mean np, variance np(1−p).
    • Poisson π(λ): p(k)=e−λλk/k! for k=0,1,2,…; mean and variance both λ. It is the limit of b(n,λ/n) as n→∞: many trials, each rarely a success.
    • Geometric: the number of the trial on which the first success happens, p(r)=p(1−p)r−1 for r=1,2,…; mean 1/p, variance (1−p)/p2.
    Averages settle down. If X1,X2,… are i.i.d. with mean μ and variance σ2, the sample mean X¯n has mean μ and variance σ2/n. So its typical distance from μ shrinks like 1/n. (The law of large numbers itself is proved in Chapter 8.)

    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 x, the chance that the variable is at most x. 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

    Law
    the law p(k) relative frequency in your samples Poisson overlay
    running mean X¯n E(X) and the band E(X)±σ/n

    Worked example

    A batch contains 200 chips, each defective with probability 0.01 independently of the others. Let X be the number of defective chips.

    1. What is the law of X? Find P(X=0).

      X∼b(200,0.01), so P(X=0)=0.99200≈0.1340.

    2. Approximate the same probability with a Poisson law. Which λ?

      Match the means: λ=np=2. Then P(X=0)≈e−2≈0.1353, within about 1% of the exact value.

    3. Estimate P(X≥3) both ways.

      Use the complement. Exactly: 1−(0.1340+0.2707+0.2720)≈0.3233. Poisson: 1−e−2(1+2+2)=1−5e−2≈0.3233. They agree to four decimal places.

    4. Compare the variances. Why is the Poisson variance a little larger?

      The binomial variance is np(1−p)=1.98; the Poisson variance is λ=2. The factor 1−p is the only difference, and it tends to 1 as p→0 with np fixed. That is the regime in which the Poisson approximation is good.

    Check your understanding

    X∼b(10,0.3) and Y∼b(10,0.3) are independent. What is the law of X+Y?

    1. b(20,0.3)
    2. b(10,0.6)Adding the two counts adds the numbers of trials, not the success probabilities. X+Y can be as large as 20.
    3. It is not binomial.Think of X and Y as counting successes in two separate runs of independent trials.
    X+Y counts successes in 20 independent trials, each with success probability 0.3. Check: the mean is 3+3=6=20⋅0.3 and the variance is 2.1+2.1=4.2=20⋅0.3⋅0.7.

    In the simulator, the running mean wanders around E(X). If you quadruple the number of draws, by what factor does its typical distance from E(X) shrink?

    1. 4That would be true of the variance of X¯n, not its standard deviation.
    2. 2
    3. 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.
    Var(X¯n)=σ2/n, so the standard deviation is σ/n. Four times as many draws halves it. That is the band drawn around E(X) in the right-hand plot.

    X is uniform on {−1,0,1} and Y=X2. Which is true?

    1. They are independent, because they are uncorrelated.Uncorrelated only says E(XY)=E(X)E(Y). Compare P(Y=0∣X=0) with P(Y=0).
    2. They are uncorrelated but not independent.
    3. They are correlated, since Y is a function of X.Compute Cov(X,Y)=E(X3)−E(X)E(X2).
    E(XY)=E(X3)=0=E(X)E(Y), so the covariance is 0. But P(Y=0∣X=0)=1≠13=P(Y=0). Correlation only detects linear dependence.

    Practice

    Mean of the geometric lawDifferentiating a series

    Show that if p(r)=p(1−p)r−1 for r≥1, then E(X)=1/p.

    Hint

    Differentiate ∑r≥0xr=11−x for |x|<1.

    Solution

    Differentiating gives ∑r≥1rxr−1=1(1−x)2. With x=1−p, E(X)=p∑r≥1r(1−p)r−1=p⋅1p2=1p. On average a fair die takes 6 rolls to show its first six.

    Thinning a Poisson countTotal probability with random variables

    The number of emails arriving in an hour is N∼π(λ). Each email, independently, is spam with probability s. Show that the number of spam emails K is Poisson with mean λs.

    Hint

    Given N=n, K∼b(n,s). Sum over n≥k.

    Solution
    P(K=k)=∑n≥ke−λλnn!(nk)sk(1−s)n−k=e−λ(λs)kk!∑m≥0(λ(1−s))mm!=e−λs(λs)kk!,

    where m=n−k. So K∼π(λs).

    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

    X is uniform on {−2,−1,1,2} and Y=X2. Find the joint distribution and show X,Y are uncorrelated but not independent.

    Hint

    Compute E(XY)=E(X3) and compare a joint probability with the product of marginals.

    Solution

    The joint law puts mass 1/4 on each of (−2,4),(−1,1),(1,1),(2,4); Y is 1 or 4 with probability 1/2 each.

    EX=0 and E(XY)=EX3=14(−8−1+1+8)=0, so Cov(X,Y)=0.

    But P(X=1,Y=4)=0≠P(X=1)P(Y=4)=1/8, so they are not independent. Y is a function of X; correlation only detects linear dependence.

    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

    X∼Bin(15,0.3), P(X=k)=(15k)0.3k0.715−k. Rewrite (c) in terms of defectives.

    Solution

    (a) (153)(0.3)3(0.7)12≈0.170.

    (b) P(X≥5)=1−P(X≤4)≈1−0.515=0.485.

    (c) More than 11 good means at most 3 defective: P(X≤3)≈0.297.

    (d) P(X≤4)≈0.515.

    (e) P(2≤X≤6)=P(X≤6)−P(X≤1)≈0.869−0.035=0.834.

    Exercise 5.36Poisson plus Poisson

    If X∼π(λ) and Y∼π(μ) are independent, show X+Y∼π(λ+μ).

    Hint

    Convolve, and recognise the binomial theorem.

    Solution
    P(X+Y=n)=∑k=0ne−λλkk!⋅e−μμn−k(n−k)!=e−(λ+μ)n!∑k=0n(nk)λkμn−k=e−(λ+μ)(λ+μ)nn!.
    SimulationApplebaum, Ch. 8: Random variables with probability density functions

    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 n copies, and watch the histogram of the standardised sum turn into the normal curve.

    The idea

    Density. X has probability density function f if P(a≤X≤b)=∫abf(x)dx for all a≤b. Then E(X)=∫xf(x)dx and Var(X)=∫(x−μ)2f(x)dx. Examples: the uniform density on (a,b), and the exponential density λe−λx on [0,∞).
    Chebyshev and the weak law. P(|X−μ|≥c)≤σ2/c2. Applied to the mean X¯n of n i.i.d. copies, whose variance is σ2/n: P(|X¯n−μ|≥c)→0 as n→∞, for every c>0.
    Normal law. N(μ,σ2) has density 1σ2πe−(x−μ)2/2σ2. If X∼N(μ,σ2) then Z=(X−μ)/σ∼N(0,1), with distribution function Φ.
    Central limit theorem. If X1,X2,… are i.i.d. with mean μ and finite variance σ2>0, and Sn=X1+⋯+Xn, then for every z
    P(Sn−nμσn≤z)⟶Φ(z)(n→∞).
    Entropy of a density. H(X)=−∫flog⁡fdx. For U(a,b) it is log⁡(b−a), which is negative when b−a<1; for N(μ,σ2) it is 12log⁡(2πeσ2), the largest possible for a density with variance σ2.

    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 c away is at most the variance divided by c2.
    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

    Distribution of each term
    The law of one term Xi.
    histogram of (Sn−nμ)/σn standard normal density

    Worked example

    A fair die is rolled 100 times. Estimate the probability that the total is at least 380.

    1. Find the mean and variance of a single roll.

      μ=3.5, and E(X2)=916, so σ2=916−494=3512≈2.917.

    2. Find the mean and standard deviation of the total S.

      E(S)=350 and Var(S)=100⋅3512≈291.7, so the standard deviation is about 17.08.

    3. Standardise and use the normal approximation.

      S takes whole-number values, so "S≥380" is the same as "S≥379.5" (a continuity correction). Then

      P(S≥379.5)≈1−Φ(29.517.08)=1−Φ(1.727)≈0.042.

      The exact value, from convolving the die's law 100 times, is 0.0420.

    4. What does Chebyshev's inequality give? Why is it so much weaker?

      P(|S−350|≥30)≤291.7/900≈0.32, 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 S is a sum of many independent pieces.

    Check your understanding

    X1,…,Xn are i.i.d. Uniform(0, 1). For large n, what does the CLT say about Sn=X1+⋯+Xn?

    1. It is approximately N(n/2, n/12).
    2. It is approximately N(1/2, 1/12).Those are the mean and variance of one term. For a sum of independent terms, means add and variances add.
    3. It is approximately uniform on (0,n).Run the simulator with the uniform law and n=2: the sum is already a triangle, not flat.
    E(Sn)=n⋅12 and Var(Sn)=n⋅112, and the CLT says the shape is approximately normal. For n=12, S12−6 is a classical quick approximation to N(0,1).

    Can a probability density function take values bigger than 1?

    1. Yes
    2. No, because f(x) is a probability.f(x) is a probability per unit length. Only its integrals are probabilities.
    3. Only at finitely many points.The uniform density on (0,12) is 2 on the whole interval.
    The uniform density on (0,12) equals 2 there, and still ∫f=1. A density must be non-negative and integrate to 1; it can be as tall as it likes on a short interval.

    What is the entropy −∫flog⁡f of the uniform density on (0,12)?

    1. −1 bit
    2. It can't be negative, so 0.That is true for discrete entropy, where each pj≤1. A density can exceed 1, which makes −log⁡f negative.
    3. 1 bitCheck the sign: f=2 and −log⁡2=−1.
    −∫01/22log⁡2dx=−1. Continuous entropy is not a count of bits and can be negative. Differences of such entropies, such as mutual information, are still meaningful and non-negative.

    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 b(400,12), with mean 200 and standard deviation 100=10. With a continuity correction, P(189.5≤S≤210.5)≈Φ(1.05)−Φ(−1.05)≈0.706. (The exact binomial value is also 0.706 to three places.)

    From uniform to exponentialThe distribution-function method

    Let U be uniform on (0,1) and Y=−ln⁡U. Find the density of Y.

    Hint

    Compute P(Y>y) for y≥0 first.

    Solution

    For y≥0, P(Y>y)=P(U<e−y)=e−y. So FY(y)=1−e−y and fY(y)=e−y: Y is exponential with λ=1. This is how the simulator above generates exponential samples.

    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

    X has mean 2 and variance 1.6. Estimate P(X>5).

    Hint

    Without more information, Chebyshev is the tool.

    Solution

    P(X>5)≤P(|X−2|≥3)≤1.69≈0.18. This is an upper bound, not an approximation; one-sided Cantelli gives the sharper 1.61.6+9≈0.15.

    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 11.25 and 13.75 heads means 12 or 13. Use the normal approximation with mean 11.25 and standard deviation 25⋅0.45⋅0.55≈2.49.

    Solution

    With the continuity correction, P(11.5≤X≤13.5)≈Φ(0.905)−Φ(0.100)≈0.817−0.540=0.28. The exact binomial value is P(X=12)+P(X=13)≈0.275. (Without the continuity correction one gets Φ(1.0)−Φ(0)≈0.34, a noticeably worse estimate at n=25.)

    Exercise 8.37Entropy of the exponential distribution

    Find the entropy of X∼E(λ).

    Hint

    −log⁡f(x)=−log⁡λ+λxlog⁡e, and EX=1/λ.

    Solution

    H(X)=−∫0∞λe−λxlog⁡(λe−λx)dx=−log⁡λ+λE(X)log⁡e=log⁡eλ. In nats this is 1−ln⁡λ. It can be negative (when λ>e), as differential entropies can.

    Interactive2020 P2, 2023 P4, 2024 P4, 2025 P4

    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

    Densities of transformed variables. Find P(Y≤y) in terms of the original variable, then differentiate. For Y=1/X2 with X standard normal, P(Y≤y)=P(|X|≥y−1/2).
    Exponential and Poisson. X∼Exp(λ) is memoryless: X−c given X≥c is again Exp(λ). The minimum of independent Exp(λ1), Exp(λ2) is Exp(λ1+λ2); a sum of n i.i.d. Exp(λ) is Gamma(n,λ) with density λnxn−1e−λx/(n−1)!; and the number of arrivals by time a is Poisson(λa).
    Maximum likelihood. Write the likelihood of what you actually observe. Censored observations contribute probabilities, uncensored ones densities. To show a unique maximizer, reparametrize if it helps (θ=1/μ) and show the score is strictly monotone, from +∞ to a negative value.
    Transforms. The Laplace transform L(u)=E[e−uY], moment generating function M(λ)=E[eλY] and characteristic function φ(u)=E[eiuY] turn sums of independent variables into products. Convergence of characteristic functions to a continuous limit gives convergence in distribution (Lévy's continuity theorem).
    Coupling. For any two variables on one space, |P(S∈E)−P(T∈E)|≤P(S≠T). Constructing ξ and η from the same uniform U makes them equal as often as possible; summing over coordinates with a union bound gives Le Cam's inequality, |P(Bin(n,p)≤K)−P(Poisson(np)≤K)|≤np2.

    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 y, 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 eiuX: 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

    Bin(n,p) Poisson(np), probabilities of each k. The panel on the right compares the largest gap between their distribution functions with the bound np2.
    Keep μ = np fixed at 3 and grow n

    Worked example

    2024 P4(4): X1,X2,… i.i.d. Exp(λ), and N is the number of partial sums Sk=X1+⋯+Xk that are ≤a. Find the maximum likelihood estimate of λ from N, and its mean and variance.

    1. Find the distribution of N.

      N=k means Sk≤a<Sk+Xk+1. Conditioning on Sk=s (Gamma density) and using independence: P(N=k)=∫0aλksk−1e−λs(k−1)!e−λ(a−s)ds=e−λa(λa)kk!. So N∼Poisson(λa) (and P(N=0)=e−λa directly).

    2. Maximize the likelihood.

      ℓ(λ)=−λa+Nlog⁡λ+const, ℓ′(λ)=−a+N/λ. For N≥1 the unique maximizer is λ^=N/a. For N=0, ℓ decreases on λ>0 and the supremum is approached at λ→0; the formula N/a=0 is the natural boundary value, and worth a sentence in an answer.

    3. Mean and variance.

      Eλ^=EN/a=λ (unbiased) and Varλ^=λa/a2=λ/a.

    Check your understanding

    X1,X2 i.i.d. Exp(λ). What is the distribution of max(X1,X2)−min(X1,X2)?

    1. Exp(λ)
    2. Exp(2λ)That is the minimum.
    3. Gamma(2,λ)That is the sum.
    Once the first one fires, the other has a fresh Exp(λ) lifetime by memorylessness. (2024 P4(2).)

    Yk=1/Xk2 with Xk i.i.d. standard normal. What does (Y1+⋯+Yn)/n2 do as n→∞?

    1. It has the same distribution as Y1 for every n.
    2. It tends to 0 by the law of large numbers.E[Y]=∞, and the scaling is n2, not n.
    3. It becomes normal after centring.The variance is infinite; the central limit theorem doesn't apply.
    φY(u)=exp⁡(−|u|(1−isgnu)), so φY(u/n2)n=φY(u). This is the Lévy distribution, stable with index 12: sums are dominated by their largest term.

    Le Cam's inequality bounds |P(Bin(n,p)≤K)−P(Poisson(np)≤K)| by:

    1. np2=μ2/n
    2. np=μThat is what you get from P(ξj≠ηj)≤p. The coupling does better: about p2 per trial.
    3. 1/nThat is the Berry–Esseen rate for the normal approximation.
    Each Bernoulli–Poisson pair disagrees with probability p(1−e−p)≤p2, and there are n pairs. Use the figure: with μ fixed, doubling n halves the bound.
    Practice2020 P2, 2023 P4, 2024 P4, 2025 P4

    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

    X1,…,Xn i.i.d. exponential with mean μ. We observe Yi=a if Xi≤a and Yi=Xi otherwise. (1) Find g(μ)=E[Y1]. (2) If Y¯>a, show g(μ^)=Y¯ has a unique solution. (3) With M=#{i:Yi=a}, find h with P(M=m,Y¯≤b)=∫abh(m,y;μ)dy for 0≤m≤n−1, b>a. (4) For m<n, y>a, show h(m,y;μ) has a unique maximizer in μ.

    Hint

    (3) Given which m are censored, the others are a+Ei with Ei∼Exp by memorylessness, and nY¯=na+∑Ei. (4) Put θ=1/μ.

    Solution

    (1) g(μ)=aP(X≤a)+E[X;X>a]=a(1−e−a/μ)+(a+μ)e−a/μ=a+μe−a/μ.

    (2) g′(μ)=e−a/μ(1+a/μ)>0, g(μ)→a as μ→0+ and g→∞ as μ→∞. By continuity and strict monotonicity, each value in (a,∞) is taken exactly once.

    (3) Choose the censored set ((nm) ways, probability (1−e−a/μ)m). The other k=n−m≥1 exceed a (probability e−ka/μ) and, given that, are a+Ei with Ei i.i.d. mean μ. Then Y¯=a+S/n with S∼Gamma(k,1/μ). Changing variables, h(m,y;μ)=(nm)(1−e−a/μ)me−ka/μ⋅n(n(y−a))k−1e−n(y−a)/μμk(k−1)! for y>a.

    (4) With θ=1/μ, log⁡h=mlog⁡(1−e−aθ)−Tθ+klog⁡θ+const, where T=ka+n(y−a)=ny−ma>0. Then ddθlog⁡h=maeaθ−1+kθ−T. The first two terms strictly decrease from +∞ (as θ→0) to 0 (as θ→∞), so the derivative crosses zero exactly once, from positive to negative: a unique maximizer θ, hence a unique μ.

    2023 Problem 4The reciprocal of a squared normal

    X standard normal, Y=1/X2 with density f. (1) Find f. (2) For L(u)=∫0∞e−uyf(y)dy, show L′(u)=−L(u)/2u for u>0. (3) Find φ(u)=E[eiuY]. (4) For i.i.d. Yk∼f, show (Y1+⋯+Yn)/n2 converges in distribution and find the limit density.

    Hint

    (2) Write L(u)=2∫0∞12πe−x2/2−u/x2dx, differentiate, and substitute x=2u/t, which swaps x2/2 and u/x2.

    Solution

    (1) P(Y≤y)=2(1−Φ(y−1/2)), so f(y)=12πy−3/2e−1/(2y) for y>0.

    (2) Differentiating under the integral (dominated for u in compact subsets of (0,∞)), L′(u)=−2∫0∞12πx−2e−x2/2−u/x2dx. With x=2u/t, x−2dx becomes 12udt (orientation reversed, limits swapped) and the exponent is unchanged, so L′(u)=−12uL(u).

    (3) Solving with L(0+)=1: L(u)=e−2u. E[e−zY] is holomorphic for Rez>0 and continuous up to Rez=0; it agrees with e−2z (principal branch) on z>0, hence on the half-plane by the identity theorem (Stein–Shakarchi Ch. 2, Corollary 4.9), and at z=−iu: φ(u)=exp⁡(−−2iu)=exp⁡(−|u|(1−isgnu)).

    (4) The characteristic function of the scaled sum is φ(u/n2)n=exp⁡(−n|u|/n(1−isgnu))=φ(u). So for every n the scaled sum has density f; it converges (trivially) in distribution, and the limit density is f itself.

    2024 Problem 4Exponential clocks and a Poisson count

    X1,X2,… i.i.d. Exp(λ). (1) Density of X1−c given X1≥c. (2) Densities of Y=min(X1,X2) and Z−Y with Z=max. (3) Density of X1+⋯+Xn. (4) The MLE of λ from N (defined by SN≤a<SN+1), its mean and variance.

    Solution

    (1) P(X1−c>x∣X1≥c)=e−λ(x+c)/e−λc=e−λx: density λe−λx, x≥0.

    (2) P(Y>y)=e−2λy, so Y has density 2λe−2λy. For Z−Y: P(Z−Y>w)=2∫0∞λe−λxe−λ(x+w)dx=e−λw, density λe−λw (and Y, Z−Y are independent).

    (3) By induction on convolutions, λnxn−1e−λx/(n−1)! for x>0.

    (4) The worked example: λ^=N/a, mean λ, variance λ/a.

    2025 Problem 4Poisson approximation by coupling

    (1) Show the sum of independent Poisson(λ1) and Poisson(λ2) is Poisson(λ1+λ2). (2) For any ξj,ηj on one space, show |P(∑ξj≤K)−P(∑ηj≤K)|≤∑jP(ξj≠ηj). (3) With U uniform on (0,1), ξ=1[U>1−p] and η=min{ℓ:U≤qℓ} where qℓ=e−p∑i≤ℓpi/i!, show P(ξ≠η)≤p2. (4) Show |P(Y≤K)−e−μ∑i≤Kμi/i!|≤μ2/n for Y∼Bin(n,p), μ=np.

    Solution

    (1) P(X1+X2=k)=∑j=0ke−λ1λ1jj!e−λ2λ2k−j(k−j)!=e−(λ1+λ2)k!∑j(kj)λ1jλ2k−j=e−(λ1+λ2)(λ1+λ2)kk!.

    (2) Let E={∑ξj≤K}, F={∑ηj≤K}. |P(E)−P(F)|≤P(E△F)≤P(∑ξj≠∑ηj)≤P(⋃j{ξj≠ηj})≤∑jP(ξj≠ηj).

    (3) η is Poisson(p) (it is the inverse-CDF construction) and ξ is Bernoulli(p). Since 1−p≤e−p=q0: on U≤1−p both are 0; on 1−p<U≤q0, ξ=1≠0=η; on q0<U≤q1 both are 1; on U>q1, η≥2≠ξ. So P(ξ≠η)=(e−p−(1−p))+(1−e−p(1+p))=p(1−e−p)≤p⋅p.

    (4) Build n independent pairs (ξj,ηj) from independent uniforms. ∑ξj∼Bin(n,p) and, by (1), ∑ηj∼Poisson(np). By (2) and (3) the difference is at most np2=μ2/n.

    SimulationVershynin, Ch. 2: Concentration of Sums of Independent Random Variables

    Concentration of sums

    A sum of n independent terms with values in [0,1] exceeds its mean by s with probability at most e−2s2/n, for every n, not just in the limit. Hoeffding, Chernoff and Bernstein are three versions of this, and the differences between them matter exactly when some terms are rare.

    The idea

    Hoeffding. If ε1,…,εN are independent random signs and a∈RN, then P(∑aiεi≥t)≤exp(−t2/2‖a‖22). If instead Xi∈[mi,Mi] are independent,
    P(∑i=1N(Xi−EXi)≥t)≤exp⁡(−2t2∑i(Mi−mi)2).
    Chernoff. If Xi are independent Bernoulli(pi), S=∑Xi and μ=ES, then for t>μ,  P(S≥t)≤e−μ(eμ/t)t. For small μ this behaves like a Poisson tail and is far smaller than Hoeffding's bound.

    All of these come from one move: apply Markov to eλS, factor EeλS using independence, and optimise over λ.

    Subgaussian. ‖X‖ψ2=inf{K>0:Eexp⁡(X2/K2)≤2}. Finite ψ2 norm is equivalent, up to absolute constants, to tails P(|X|≥t)≤2e−t2/K2, to moments ‖X‖Lp≲Kp, and (for mean zero) to EeλX≤eCK2λ2.
    General Hoeffding. For independent mean-zero subgaussian Xi,  P(|∑Xi|≥t)≤2exp⁡(−ct2/∑‖Xi‖ψ22).
    Bernstein. For independent mean-zero subexponential Xi (‖X‖ψ1=inf{K:Ee|X|/K≤2} finite), with K=max‖Xi‖ψ1,
    P(|∑i=1NXi|≥t)≤2exp⁡(−cmin(t2∑i‖Xi‖ψ12, tK)):

    a Gaussian tail for moderate t, an exponential one far out.

    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 t falls off like e−t2, 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

    exact P(S≥k), S∼Bin(n,p) simulated Chebyshev Hoeffding Chernoff

    Worked example

    An A/B test estimates a click rate p by the fraction p^ of N independent users who click. We want |p^−p|<0.01 with probability at least 0.999. How many users are needed?

    1. Use Chebyshev, knowing only p(1−p)≤1/4.

      P(|p^−p|≥0.01)≤p(1−p)N⋅10−4≤14N⋅10−4. Setting this to 10−3 gives N≥2500000.

    2. Use Hoeffding (each click indicator lies in [0,1]).

      Two-sided: P(|p^−p|≥ε)≤2e−2Nε2. We need 2e−2N⋅10−4≤10−3, i.e. N≥ln⁡(2000)/(2⋅10−4)≈38005. Sixty-five times fewer users.

    3. Suppose you also know p≤0.02. Bernstein's inequality for variables with |Xi−p|≤1 reads P(|∑(Xi−p)|≥t)≤2exp⁡(−t2/2Nσ2+t/3). What N does it give?

      Here σ2=p(1−p)≤0.02⋅0.98=0.0196 and t=Nε, so the exponent is Nε2/(2(σ2+ε/3)). We need it to be at least ln⁡2000≈7.60:

      N ≥ 2(0.0196+0.00333)⋅7.6010−4 ≈ 3487.

      Another factor of 11. Hoeffding pays for the worst-case variance 1/4; Bernstein pays only for the actual variance.

    4. How does each answer scale with the failure probability δ?

      Chebyshev needs N∝1/δ; Hoeffding and Bernstein need N∝log⁡(1/δ). Asking for δ=10−6 instead of 10−3 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?

    1. A random variable with |X|≤5 almost surelyBounded variables are subgaussian: EeX2/K2≤e25/K2, which is at most 2 for large K.
    2. N(0,σ2)The Gaussian is the model subgaussian variable, with ‖X‖ψ2 a constant times σ.
    3. An exponential random variable
    4. A sum of 100 independent random signsThat sum is bounded by 100, and better, it has ψ2 norm of order 100.
    P(X≥t)=e−t decays only exponentially, so EeX2/K2=∞ for every K. The exponential is the model subexponential variable, which is where Bernstein's inequality takes over.

    S∼Bin(104,10−4), so ES=1. Hoeffding bounds P(S≥10) by about 0.98; Chernoff by about 8×10−7. Why is Hoeffding so weak here?

    1. It only uses that each term lies in [0,1], not that each term is almost always 0.
    2. Hoeffding needs identically distributed terms.It doesn't, and these terms are identically distributed anyway.
    3. Hoeffding needs symmetric terms.The version for bounded variables needs only independence and the ranges.
    4. Hoeffding only holds for large n.It holds for every n. It is a true bound here, just a useless one.
    Hoeffding's exponent 2t2/n is what you'd get if every term had the largest variance a [0,1] variable can have, namely 1/4. Here the variance is 10−4. Chernoff (or Bernstein) sees the true variance. Try p=0.005 in the explorer.

    Let Xi=gi2−1 with gi i.i.d. standard normal, so the Xi are mean-zero subexponential. For which deviations t does Bernstein give a Gaussian-type bound e−ct2/N for P(|∑i≤NXi|≥t)?

    1. For t≲N
    2. For t≳NCompare t2/N with t: which is smaller when t is large?
    3. For all tThen ∑Xi would be subgaussian, but P(X1≥t) alone already decays like e−t/2.
    4. Only for t≲NN is the typical size of the sum, but the Gaussian regime extends much further.
    The minimum of t2/N and t is t2/N exactly when t≤N. So the sum looks Gaussian (scale N) well into its tail, and only beyond t≈N does the exponential tail of a single term take over.

    Practice

    Two subgaussian normsComputing ψ₂ from the definition

    (a) Show that if |X|≤M, then ‖X‖ψ2≤M/ln⁡2, with equality for X=±M with equal probability. (b) Compute ‖g‖ψ2 for g∼N(0,1).

    Hint

    For (b), Eesg2=(1−2s)−1/2 for s<1/2.

    Solution

    (a) EeX2/K2≤eM2/K2≤2 once K2≥M2/ln⁡2; for X=±M the first inequality is an equality, so this K is the smallest. (b) Set (1−2/K2)−1/2=2: then 1−2/K2=1/4, K2=8/3, ‖g‖ψ2=8/3≈1.633.

    From MGFs to a tail boundThe exponential moment method

    Suppose X1,…,XN are independent and EeλXi≤eλ2σi2/2 for all λ∈R. Prove P(∑Xi≥t)≤exp⁡(−t2/2∑σi2) for t≥0.

    Solution

    For λ>0, Markov and independence give P(S≥t)≤e−λt∏EeλXi≤exp⁡(−λt+λ2V/2) with V=∑σi2. The exponent is smallest at λ=t/V, where it equals −t2/2V. Random signs satisfy the hypothesis with σi=|ai|, because cosh⁡x≤ex2/2; this recovers Hoeffding.

    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 X∼Pois(μ). Prove: (a) P{X≥t}≤e−μ(eμ/t)t for t≥μ; (b) P{X≤t}≤e−μ(eμ/t)t for 0<t≤μ; (c) P{|X−μ|≥δμ}≤2e−δ2μ/3 for δ∈[0,1]; (d) P{X=t}≥e−μ(μ/t)t for integers t>0.

    Hint

    EeλX=exp⁡(μ(eλ−1)). Optimise Markov's inequality over λ; the optimum is eλ=t/μ.

    Solution

    (a) For λ≥0, P{X≥t}≤e−λteμ(eλ−1). With eλ=t/μ≥1 this is (μ/t)tet−μ=e−μ(eμ/t)t.

    (b) For λ≥0, P{X≤t}=P{e−λX≥e−λt}≤eλteμ(e−λ−1). With e−λ=t/μ≤1 we get the same expression.

    (c) At t=(1±δ)μ the bounds read exp⁡(−μh(±δ)) with h(u)=(1+u)ln⁡(1+u)−u. Elementary calculus gives h(δ)≥δ2/3 and h(−δ)≥δ2/2 on [0,1] (compare derivatives: h′(u)=ln⁡(1+u), h″(u)=1/(1+u)≥1/2). Add the two tails.

    (d) P{X=t}=e−μμt/t!≥e−μ(μ/t)t, since t!≤tt.

    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 P{|X|≥t}≤2e−t2/K2 for some K. Compare each tail with e−ct2.

    Solution

    For each, find a lower bound on the tail that decays slower than any e−ct2:

    • Exponential: P{X>t}=e−t.
    • Geometric: P{X>k}=(1−p)k, again exponential.
    • Poisson: P{X≥t}≥P{X=t}≥e−μ(μ/t)t=e−tln⁡(t/μ)−μ, which is e−O(tlog⁡t).
    • Chi-squared with k degrees of freedom: X≥g12, and P{g12>t}≈e−t/2.
    • Gamma(k,θ): density ∝xk−1e−x/θ, tail of order tk−1e−t/θ.
    • Cauchy: P{X>t}∼1/(πt); it doesn't even have a mean.
    • Pareto: polynomial tail t−α.

    Since e−ct/e−c′t2→∞, none of these can satisfy a subgaussian tail bound. (The first five are subexponential; Cauchy and Pareto are heavier still.)

    SimulationVershynin, Ch. 5: Concentration Without Independence

    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: N points in any dimension can be projected to about log⁡N/ε2 dimensions with every pairwise distance preserved up to 1±ε.

    The idea

    Gaussian concentration. If X∼N(0,In) and f:Rn→R is L-Lipschitz, then for all t≥0
    P(|f(X)−Ef(X)|≥t)≤2e−t2/2L2.
    On the sphere. If X is uniform on nSn−1 and f is L-Lipschitz, then ‖f(X)−Ef(X)‖ψ2≤CL. The coordinates of X are not independent; the concentration comes from the geometry of the sphere (isoperimetry).
    Johnson–Lindenstrauss. Let x1,…,xN∈Rn and ε∈(0,1). If k≥Cε−2log⁡N and P is a k×n matrix with i.i.d. N(0,1/k) entries (or a suitably scaled random projection), then with high probability
    (1−ε)‖xi−xj‖2≤‖Pxi−Pxj‖2≤(1+ε)‖xi−xj‖2for all i,j.

    The target dimension depends on N and ε but not on n, and P is chosen without looking at the data. The proof: for one fixed vector u, ‖Pu‖/‖u‖ concentrates at 1 with subgaussian tails in kε; then union-bound over the (N2) differences.

    Matrix Bernstein. For independent mean-zero symmetric n×n random matrices Xi with ‖Xi‖≤K and σ2=‖∑EXi2‖,
    P(‖∑iXi‖≥t)≤2nexp⁡(−t2/2σ2+Kt/3).

    The dimension enters only as the factor n in front, i.e. as a log⁡n in the deviation. It handles covariance estimation for general (not subgaussian) distributions.

    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 d moves the output by at most a fixed multiple of d.
    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

    Data in ℝ³⁰⁰
    How each pairwise distance changes. [1−ε,1+ε], ε = worst pair
    worst distortion for this projection, every k rough guide 2ln⁡N/k

    Worked example

    Let g∼N(0,In) and M=maxi≤ngi. How large is M, and how much does it fluctuate?

    1. Bound EM. (Hint: eλEM≤EeλM.)

      By Jensen, eλEM≤EeλM≤∑iEeλgi=neλ2/2. So EM≤ln⁡nλ+λ2, and λ=2ln⁡n gives EM≤2ln⁡n. For n=106 that is about 5.26.

    2. Show that f(x)=maxixi is 1-Lipschitz for the Euclidean norm.

      If the max of x is at i, then f(x)−f(y)≤xi−yi≤‖x−y‖∞≤‖x−y‖2. Swap the roles of x and y for the other direction.

    3. What does Gaussian concentration give?

      P(|M−EM|≥t)≤2e−t2/2 for every n. The maximum of a million Gaussians grows like 2ln⁡n, but it fluctuates by O(1) regardless of n. (Its true fluctuations are even smaller, but the theorem needs no work to give O(1).) Independence was never used in step 3; only the Lipschitz property was.

    4. The same reasoning applies to f(x)=‖Px−Py‖ as a function of the Gaussian entries of P. Compute its Lipschitz constant and explain why JL needs k≳log⁡N/ε2.

      With u=x−y a unit vector and P=G/k, ‖Pu‖=‖Gu‖/k, and G↦‖Gu‖ is 1-Lipschitz in the Frobenius norm of G. So ‖Pu‖ deviates from its mean (which is close to 1) by more than ε with probability ≤2e−kε2/2, roughly. For all (N2) pairs to succeed we need N2e−kε2/2≪1, i.e. k≳4ln⁡N/ε2.

    Check your understanding

    In the Johnson–Lindenstrauss lemma, what does the target dimension k depend on?

    1. Only on the number of points N and the accuracy ε
    2. On the ambient dimension nThe proof handles one difference vector at a time, and the law of ‖Pu‖/‖u‖ is the same in every dimension.
    3. On how the points are arrangedThe projection is chosen without looking at the data. Switch data sets in the explorer.
    4. Only on εMore points mean more pairs that could fail; the union bound charges log⁡N.
    k≈Cε−2log⁡N. A million points can be embedded in a few thousand dimensions with 10% distortion, whether they started in R104 or R109.

    X∼N(0,In) and f is 1-Lipschitz. Which statement is guaranteed for every n?

    1. f(X) stays within O(1) of Ef(X) with high probability.
    2. f(X) is approximately Gaussian.Concentration controls the size of fluctuations, not their shape. Think of f(x)=|x1|.
    3. Ef(X) is bounded independently of n.f(x)=‖x‖2 is 1-Lipschitz and E‖X‖≈n.
    4. Var⁡f(X)=1.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 f.
    The tail bound 2e−t2/2 does not depend on n at all, while Ef(X) can grow with n. So in relative terms, functions like ‖X‖ become nearly deterministic.

    Fix the target dimension k and add more and more points. How does the worst distortion over all pairs typically grow with N?

    1. Like log⁡N
    2. It stays the same.Each new pair is another chance for an unlucky ratio.
    3. Like NThat would follow from Chebyshev-type tails. The per-pair tail is Gaussian.
    4. Like N2The number of pairs grows like N2, but the distortion only like the square root of its logarithm.
    The worst of M≈N2/2 roughly Gaussian deviations of size 1/2k is about 2ln⁡M/2k≈2ln⁡N/k. Slide N in the explorer: going from 10 to 150 points (fifteen times as many) raises the curve by less than half.

    Practice

    Sizing a projectionUnion bound arithmetic

    Suppose that for each fixed difference vector, a random projection to k dimensions distorts its length by more than ε with probability at most 2e−kε2/8. How large should k be so that N=104 points keep all pairwise distances within 20%, with failure probability at most 1%?

    Solution

    There are fewer than N2/2 pairs, so the failure probability is below N2e−kε2/8. Require N2e−kε2/8≤0.01: k≥8ln⁡(100N2)/ε2=8ln⁡(1010)/0.04≈4605. The original dimension never entered.

    The norm of a Gaussian imageLipschitz constant of x ↦ ‖Ax‖

    Let A be a fixed m×n matrix and g∼N(0,In). Show that ‖Ag‖2 fluctuates around its mean by O(‖A‖), while E‖Ag‖2≤‖A‖F. When is the fluctuation small compared with the mean?

    Hint

    |‖Ax‖−‖Ay‖|≤‖A(x−y)‖. For the mean, use Jensen and E‖Ag‖2=‖A‖F2.

    Solution

    x↦‖Ax‖ is ‖A‖-Lipschitz, so P(|‖Ag‖−E‖Ag‖|≥t)≤2e−t2/2‖A‖2. Also (E‖Ag‖)2≤E‖Ag‖2=‖A‖F2, and since the variance is O(‖A‖2), E‖Ag‖≥‖A‖F−C‖A‖. The fluctuation is small relative to the mean when ‖A‖F/‖A‖ is large, i.e. when the stable rank ‖A‖F2/‖A‖2 is large.

    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 Xi∼N(0,1), show ‖maxiXi−EmaxiXi‖ψ2≤C. (b) For jointly normal X1,…,Xn (any covariance), show ‖maxiXi−EmaxiXi‖ψ2≤CmaxiVar(Xi).

    Hint

    Gaussian concentration for Lipschitz functions. Write jointly normal variables as μi+⟨vi,g⟩ with g∼N(0,I).

    Solution

    (a) f(x)=maxixi is 1-Lipschitz for ‖⋅‖2: |maxx−maxy|≤maxi|xi−yi|≤‖x−y‖2. Gaussian concentration gives ‖f(g)−Ef(g)‖ψ2≤C.

    (b) Write X=μ+Vg with g∼N(0,In) and rows vi of V (e.g. V=Σ1/2). Then maxiXi=f(g) with f(x)=maxi(μi+⟨vi,x⟩), which is Lipschitz with constant maxi‖vi‖2=maxiVarXi. Apply Gaussian concentration again.

    Exercise 5.14Johnson–Lindenstrauss with subgaussian matrices

    Let A be m×n with independent, mean-zero, isotropic, subgaussian rows, and Q=A/m. Show the Johnson–Lindenstrauss lemma holds for Q: for N points and m≥CK4ε−2log⁡N, all pairwise distances are preserved up to a factor 1±ε with high probability. Why does this cover random ±1 matrices?

    Hint

    For a fixed unit vector z, Az has independent coordinates with unit variance. Apply concentration of the norm (Theorem 3.1.1), then a union bound over pairs.

    Solution

    Fix a unit vector z. The coordinates ⟨Ai,z⟩ of Az are independent, mean zero, with E⟨Ai,z⟩2=1 (isotropy) and ‖⟨Ai,z⟩‖ψ2≤K. Concentration of the norm gives ‖‖Az‖2−m‖ψ2≤CK2, so

    P{|‖Qz‖2−1|>ε}≤2exp⁡(−cε2m/K4).

    Apply this to zij=(xi−xj)/‖xi−xj‖2 for each of the fewer than N2 pairs. The union bound gives failure probability at most 2N2e−cε2m/K4, which is small once m≥CK4ε−2log⁡N. On the good event, (1−ε)‖xi−xj‖≤‖Qxi−Qxj‖≤(1+ε)‖xi−xj‖.

    A matrix with i.i.d. ±1 entries has independent rows, mean zero, isotropic (EAijAik=δjk), and bounded hence subgaussian entries, so its rows are subgaussian with K≤C.

    Simulation2026 P2, 2026 P4

    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

    Chernoff's method. For λ>0, Markov's inequality applied to eλZ gives P(Z≥ε)≤MZ(λ)e−λε. Compute MZ for a sum of independent terms as a product, then choose λ to make the bound small. Exact optimization is not required: any λ in the allowed range gives a valid bound.
    Gaussian facts. If A has i.i.d. N(0,1) entries and ‖b‖=1, then the entries of Ab are i.i.d. N(0,1), so ‖Ab‖2∼χm2, with M(λ)=(1−2λ)−m/2 for λ<12.
    Johnson–Lindenstrauss. k points in any dimension can be mapped linearly into m=O(η−2log⁡k) dimensions with all pairwise squared distances preserved within a factor 1±η. A scaled Gaussian matrix does it with high probability, and the target dimension doesn't depend on the original dimension at all. The proof is a Chernoff bound for one pair plus a union bound over (k2) pairs.
    First-step analysis. For a chain absorbed at 0 or N, let ϕi be the probability of absorption at N from i. Conditioning on the first step: ϕi=piϕi+1+qiϕi−1+(1−pi−qi)ϕi, i.e. pi(ϕi+1−ϕi)=qi(ϕi−ϕi−1). If pi/qi=r is constant this is the gambler's ruin: ϕi=1−r−i1−r−N (i/N when r=1). Expected absorption times satisfy the same recursion with a source term: (pi+qi)Ti=1+piTi+1+qiTi−1.

    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 a is at most its average divided by a.
    Moment generating function
    The average of eλX. It packs every moment of X 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

    For 40 random points in R300, the ratio ‖bi′−bj′‖2/‖bi−bj‖2 for all 780 pairs, after b↦1mAb. 1±η

    Explore: the Moran process

    ϕi from the formula simulated, with a 95% interval. The dashed line is the neutral case i/N.

    Worked example

    2026 P2(3): for ‖b‖=1 and 0<ε≤m, show P(‖Ab‖2−m≥ε)≤e−ε2/(8m), given log⁡(1+x)≥x−x2 for x≥−12.

    1. Apply (1) and (2) of the problem.

      Z=‖Ab‖2∼χm2 is a sum of m independent X2 terms, so MZ(λ)=(1−2λ)−m/2 and P(Z−m≥ε)≤(1−2λ)−m/2e−λ(m+ε) for 0<λ<12.

    2. Use the hint on (1−2λ)−m/2. Where does it apply?

      With x=−2λ≥−12, i.e. λ≤14: −m2log⁡(1−2λ)≤−m2(−2λ−4λ2)=mλ+2mλ2. So the bound is at most exp⁡(−λε+2mλ2).

    3. Choose λ.

      The exponent is minimized at λ=ε/(4m), which is ≤14 because ε≤m. Its value is −ε24m+ε28m=−ε28m. That is where the condition ε∈(0,m] comes from.

    Check your understanding

    In Johnson–Lindenstrauss, how must the target dimension m grow with the number of points k (fixed η, δ)?

    1. Like log⁡k
    2. Like kThe union bound over k2 pairs only costs a logarithm, since each pair fails with probability e−η2m/8.
    3. Like the original dimension nn doesn't appear at all.
    m≥8η2log⁡k(k−1)2δ. For the 40 points in the figure with η=0.3 and δ=0.1, the lemma asks for m≈800, yet almost every pair is already within tolerance at m=200. The constant is pessimistic, the shape is right.

    In the neutral Moran process (r=1), what is the probability that type A takes over starting from i individuals?

    1. i/N
    2. 1/2Larger starting groups are more likely to win.
    3. 1−(1−1/N)iThat would be right if each A lineage independently had probability 1/N; they aren't independent.
    With r=1, Xt is a martingale, so EX∞=i, and X∞∈{0,N} gives Nϕi=i. Equivalently, every individual is equally likely to be the eventual common ancestor.

    A single mutant (i=1) with r=1.1 in a large population fixes with probability about:

    1. 1−1/r≈0.09
    2. 1/NThat is the neutral answer; selection helps a lot.
    3. Close to 1Early on there is only one mutant, and it is easily lost by chance.
    ϕ1=(1−r−1)/(1−r−N)→1−1/r as N→∞. Most advantageous mutations are still lost to drift.
    Practice2026 P2, 2026 P4

    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 X standard normal and Y=X2, show MY(λ)=(1−2λ)−1/2 for λ<12. (2) Show P(Z≥ε)≤MZ(λ)/eλε for ε,λ>0. (3) For an m×n matrix A of i.i.d. standard normals and ‖b‖=1, ε∈(0,m], show P(‖Ab‖2−m≥ε)≤e−ε2/(8m). (4) For b1,…,bk∈Rn, bi′=Abi/m, and m≥8η2log⁡k(k−1)2δ, show that with probability at least 1−δ, ‖bi′−bj′‖2≤(1+η)‖bi−bj‖2 for all i,j.

    Solution

    (1) MY(λ)=∫12πe−(1−2λ)x2/2dx=(1−2λ)−1/2, a Gaussian integral with variance 1/(1−2λ).

    (2) 1[Z≥ε]≤eλ(Z−ε) pointwise; take expectations.

    (3) (Ab)i=∑jAijbj are independent N(0,‖b‖2)=N(0,1), so ‖Ab‖2 is a sum of m independent copies of Y. The rest is the worked example.

    (4) For a pair with bi≠bj, let u=(bi−bj)/‖bi−bj‖. Then ‖bi′−bj′‖2=‖bi−bj‖2‖Au‖2/m, and the bad event is ‖Au‖2−m>ηm. With ε=ηm∈(0,m], (3) bounds its probability by e−η2m/8≤2δk(k−1). Pairs with bi=bj, and i=j, never fail. A union bound over the (k2) unordered pairs gives total failure probability at most δ.

    2026 Problem 4Fixation in the Moran process

    A population of N≥2 has Xt individuals of type A (fitness fA) and the rest type B (fB), r=fA/fB. Each step one individual is chosen uniformly; with ut uniform on (0,1), a chosen A becomes B if ut>fAXtfAXt+fB(N−Xt), and a chosen B becomes A if ut is at most that. With pi=P(X1=i+1∣X0=i) and qi=P(X1=i−1∣X0=i): (1) show pi/qi=r. (2) Relate ϕi+1,ϕi,ϕi−1, where ϕi is the probability that Xt→N. (3) Find ϕi. (4) Relate Ti+1,Ti,Ti−1, where Ti is the expected absorption time. (5) For r=1, write Ti using i, N, LN, Li+1, LN−i+1, where Lj=∑k=1j−11/k (L1=0) and ∑j=1nLj=nLn+1−n.

    Hint

    (5) With Di=Ti−Ti−1, the recursion is Di+1−Di=−N(1i+1N−i). Sum twice, then fix D1 from TN=0.

    Solution

    (1) Let ρi=riri+N−i. pi=N−iNρi=(N−i)riN(ri+N−i) and qi=iN(1−ρi)=i(N−i)N(ri+N−i). The ratio is r.

    (2) First-step analysis: ϕi=piϕi+1+qiϕi−1+(1−pi−qi)ϕi, i.e. pi(ϕi+1−ϕi)=qi(ϕi−ϕi−1).

    (3) The differences satisfy di+1=di/r, with ϕ0=0, ϕN=1. So ϕi=d1∑k=0i−1r−k, and normalizing, ϕi=1−r−i1−r−N for r≠1, ϕi=i/N for r=1.

    (4) Ti=1+piTi+1+q