UTokyo Mathematical Informatics Exam · Study tools

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. The doctoral written exam (module 10) is online, in late August and again in late January (26–29 January 2027 for the winter round). 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 module 2).

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.

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.

Weeks 1–2: symmetric matrices
Module 2; Horn and Johnson §§4.1, 7.1–7.2, 7.7. Past problems 2020 P1, 2024 P1, 2025 P1, 2026 P1, then the six book exercises. Goal: diagonalize-first becomes automatic.
Weeks 3–4: probability and statistics
Module 6 and module 7, with a standard probability text from the department's list (伏見 or Grimmett and Welsh) for transforms, the exponential and Poisson families, and maximum likelihood. Six past problems. Goal: change of variables, memorylessness, first-step analysis and Chernoff bounds without notes.
Weeks 5–6: algorithms
Module 8; Kleinberg and Tardos §§3.6, 4.4, 6.8–6.10, 7.1–7.5, 11.1. Five past problems (including 2023 P5 from module 9), then the three book exercises. Goal: every algorithm answer has the four parts (algorithm, invariant, correctness, running time).
Week 7: differential equations
Module 3; Strogatz §§2.5, 6.3–6.5, 7.2. Four past problems and five book exercises. Goal: for any planar system, find the fixed points, a conserved or decreasing quantity, and the long-run behaviour.
Week 8: analysis
Module 5; Stein and Shakarchi Ch. 2 §4 and Ch. 3 §§1–2, 7. Four past problems and four book exercises.
Week 9: optimization, and algebra
Module 4 with Boyd and Vandenberghe §§2.6, 3.1, 5.2, 8.1, and module 9. 2024 P2, 2020 P3, and the five book exercises.
Weeks 10–12: full mock exams
Two mock exams a week from the generator above, three hours each, choosing three of five under exam conditions, then marking against the solutions. Spend the days in between on the stuck-list. In the final week, redo one full real paper (2026 or 2025) cold.

Applying to the doctoral program instead? Replace weeks 10–12 with module 10: one keyword essay a day from the drill, written in 30 minutes, with the five-part outline.

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?

Problem 1Problem 1 is usually linear algebra (four of five papers).
Problem 3The middle slots rotate between differential equations, analysis, optimization and algebra.
Problem 5

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?

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

The 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?

All five.Five are set, but you choose.
Three of the five.
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 module 2); 室田・杉原『線形代数 I・II』◎.
Differential equations: Strogatz, Nonlinear Dynamics and Chaos, §§2.5, 6.3–6.5, 7.2 (used in module 3). 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 module 5); 杉浦『解析入門 I・II』◎; 森・杉原『複素関数論』◎; Ahlfors, Complex Analysis.
Optimization: Boyd and Vandenberghe, Convex Optimization, §§2.6, 3.1, 5.2, 8.1 (used in module 4; 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 module 8); 渋谷『アルゴリズム』◎; Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms.
Algebra and discrete mathematics: 伊理・藤重『応用代数』◎; Lidl and Pilz, Applied Abstract Algebra.

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\Lambda Q^\top

with

Q

orthogonal and

\Lambda=\mathrm{diag}(\lambda_1,\dots,\lambda_n)

real.

B\succeq O

(positive semidefinite, 半正定値) means

x^\top Bx\ge0

for all

x

, equivalently all

\lambda_i\ge0

. Then

B^{1/2}=Q\Lambda^{1/2}Q^\top

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 $\tilde C=Q^\top CQ$ and $\tilde A=Q^\top AQ$ . The equation becomes $\Lambda\tilde C+\tilde C\Lambda=\tilde A$ , which is entrywise: $(\lambda_i+\lambda_j)\tilde C_{ij}=\tilde A_{ij}$ . Commuting with $B$ becomes $(\lambda_i-\lambda_j)\tilde C_{ij}=0$ .

Loewner order (H&J 7.7.1).

X\succeq Y

means

X-Y\succeq O

. It is a partial order: two symmetric matrices are often incomparable. Congruence preserves it:

X\succeq Y\Rightarrow S^\top XS\succeq S^\top 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\succeq O

then

\mathrm{tr}(AB)=\mathrm{tr}(A^{1/2}BA^{1/2})\ge0

, and

\mathrm{tr}(AB)=\lVert A^{1/2}B^{1/2}\rVert_F^2

, so

\mathrm{tr}(AB)=0

if and only if

AB=O

. Conversely,

A\succeq O

if and only if

\mathrm{tr}(AC)\ge0

for every PSD

C

(take

C=vv^\top

): 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\succeq B\succ O

then

B^{-1}\succeq A^{-1}

and

A^{1/2}\succeq B^{1/2}

. It does not follow that

A^2\succeq B^2

. (Functions that preserve the order are called operator monotone;

t^{1/2}

,

\log t

and

-1/t

are,

t^2

is not.)

Projection onto the PSD cone. With the inner product $\langle A,B\rangle=\mathrm{tr}(AB)$ , the nearest PSD matrix to a symmetric $A=Q\Lambda Q^\top$ clips the negative eigenvalues: $\phi(A)=Q\max(\Lambda,0)Q^\top$ . Like every projection onto a closed convex set, it is characterized by the variational inequality $\langle A-\phi(A),X-\phi(A)\rangle\le0$ for all $X$ in the set. The same inequality reappears for isotonic regression in module 8.

Orthogonal Procrustes (H&J 7.4.5). Over orthogonal

P

,

\lVert PX-Y\rVert_F^2=\lVert X\rVert_F^2+\lVert Y\rVert_F^2-2\,\mathrm{tr}(PXY^\top)

. Minimizing it means maximizing the trace; if

XY^\top=U\Sigma V^\top

, the maximizer is

P=VU^\top

.

Explore

The curve

x^\top Mx=1

of a positive definite

M

is an ellipse with semi-axes

1/\sqrt{\lambda_i}

along its eigenvectors. A larger matrix gives a smaller ellipse, so

P\succeq 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\times2$ symmetric $A\succeq B\succeq O$ with $A^2\not\succeq B^2$ .

Why must $A$ and $B$ fail to commute?

If $AB=BA$ they diagonalize in a common basis, and $a_i\ge b_i\ge0$ gives $a_i^2\ge b_i^2$ . So the counterexample needs tilted axes, as in the second preset above.
Take $B=\mathrm{diag}(1,0)$ and $A=B+\begin{pmatrix}1&1\\1&1\end{pmatrix}$ . Check $A\succeq B\succeq O$ .

$A-B=\begin{pmatrix}1&1\\1&1\end{pmatrix}=vv^\top$ with $v=(1,1)^\top$ , which is PSD. $B$ is PSD. So $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}\succeq B\succeq O$ .
Compute $A^2-B^2$ and decide.

$A^2=\begin{pmatrix}5&3\\3&2\end{pmatrix}$ , $B^2=B$ , so $A^2-B^2=\begin{pmatrix}4&3\\3&2\end{pmatrix}$ with determinant $8-9=-1<0$ . One eigenvalue is negative, so $A^2\not\succeq B^2$ . Writing out the matrices and the determinant is a complete answer for a "false" part.

Check your understanding

If $A\succeq B\succeq O$ , which of these must hold?

$A^2\succeq B^2$ The worked example above is a counterexample.
$A^{1/2}\succeq B^{1/2}$
$AB\succeq O$ $AB$ need not even be symmetric when they don't commute.

The square root is operator monotone. Proof: let

S=A^{1/2}

,

R=B^{1/2}

, and suppose

(S-R)v=-\mu v

with

\mu>0

,

\lVert v\rVert=1

. Since

S^2-R^2=(S-R)S+R(S-R)

, we get

v^\top(A-B)v=-\mu\,v^\top(S+R)v\le0

. But

A\succeq B

, so

v^\top(S+R)v=0

, forcing

Sv=Rv=0

and

(S-R)v=0

, a contradiction.

$X,Y\succeq O$ and $\mathrm{tr}(XY)=0$ . What follows?

$X=O$ or $Y=O$ $X=\mathrm{diag}(1,0)$ , $Y=\mathrm{diag}(0,1)$ .
$XY=O$
$X+Y$ is singularThe same example gives $X+Y=I$ .

\mathrm{tr}(XY)=\lVert X^{1/2}Y^{1/2}\rVert_F^2=0

forces

X^{1/2}Y^{1/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=\mathrm{diag}(3,-2)$ in the Frobenius norm?

$\mathrm{diag}(3,0)$
$\mathrm{diag}(3,2)$ That flips the sign. It is at distance 4, while clipping gives distance 2.
$\mathrm{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.

Practice

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\times n$ matrix and $B$ is symmetric positive definite. (1) Show there is exactly one real $C$ with $BC+CB=A$ ; call it $C_{A,B}$ . (2) Show $BC_{A,B}=C_{A,B}B$ 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\Lambda Q^\top$ with all $\lambda_i>0$ . With $\tilde C=Q^\top CQ$ and $\tilde A=Q^\top AQ$ , the equation is equivalent to $(\lambda_i+\lambda_j)\tilde C_{ij}=\tilde A_{ij}$ for all $i,j$ . Since $\lambda_i+\lambda_j>0$ , the unique solution is $\tilde C_{ij}=\tilde A_{ij}/(\lambda_i+\lambda_j)$ , and $C=Q\tilde CQ^\top$ is real. (Equivalently, the linear map $C\mapsto BC+CB$ has eigenvalues $\lambda_i+\lambda_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\in\R^{d\times m}$ , and let $\mathrm{OPT}(X,Y)$ be the set of minimizers of $\lVert PX-Y\rVert_F^2$ over $P\in\R^{d\times d}$ with $P^\top P=I$ . (1) Given $A,B\in\R^{d\times m}$ with columns $a_j,b_j$ and weights $w_j>0$ , find $X,Y$ so that $\mathrm{OPT}(X,Y)$ is the set of minimizers of $\sum_j w_j\lVert Pa_j-b_j\rVert_2^2$ . (2) Show $\mathrm{OPT}(X,Y)$ is the set of maximizers of $\mathrm{tr}(PXY^\top)$ over orthogonal $P$ . (3) If $XY^\top=U\Sigma V^\top$ is an SVD, give an element of $\mathrm{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; $\lVert PX\rVert_F=\lVert X\rVert_F$ when $P$ is orthogonal. (3) Write $\mathrm{tr}(PU\Sigma V^\top)=\mathrm{tr}(Z\Sigma)$ with $Z=V^\top PU$ orthogonal.

Solution

(1) $X=AW^{1/2}$ , $Y=BW^{1/2}$ with $W=\mathrm{diag}(w_1,\dots,w_m)$ . Column $j$ of $PX-Y$ is $\sqrt{w_j}(Pa_j-b_j)$ , so $\lVert PX-Y\rVert_F^2=\sum_jw_j\lVert Pa_j-b_j\rVert_2^2$ for every $P$ .

(2) $\lVert PX-Y\rVert_F^2=\mathrm{tr}(X^\top P^\top PX)-2\,\mathrm{tr}(Y^\top PX)+\lVert Y\rVert_F^2=\lVert X\rVert_F^2+\lVert Y\rVert_F^2-2\,\mathrm{tr}(PXY^\top)$ , using $P^\top P=I$ and $\mathrm{tr}(Y^\top PX)=\mathrm{tr}(PXY^\top)$ . The first two terms don't depend on $P$ , so minimizing the left side is the same as maximizing $\mathrm{tr}(PXY^\top)$ .

(3) $\mathrm{tr}(PU\Sigma V^\top)=\mathrm{tr}(V^\top PU\Sigma)=\sum_i\sigma_iZ_{ii}$ with $Z=V^\top PU$ orthogonal. Entries of an orthogonal matrix satisfy $|Z_{ii}|\le1$ , so the trace is at most $\sum_i\sigma_i$ , with equality at $Z=I$ , i.e. $P=VU^\top$ . This $P$ is in $\mathrm{OPT}(X,Y)$ . Horn and Johnson (7.4.5) state the same answer through the polar decomposition: if $YX^\top=HU_0$ with $H\succeq O$ , $U_0$ orthogonal, then $P=U_0$ .

2025 Problem 1True or false for the Loewner order

For real symmetric $d\times d$ matrices $A,B$ ( $d\ge2$ ), prove or give a counterexample: (1) $A,B\succeq O\Rightarrow\mathrm{tr}(AB)\ge0$ . (2) $A,B\succeq O$ and $\mathrm{tr}(AB)=0\Rightarrow A=O$ or $B=O$ . (3) $\mathrm{tr}(AC)\ge0$ for every PSD $C\Rightarrow A\succeq O$ . (4) $A\succeq B\succeq O\Rightarrow A^2\succeq B^2$ . (5) $A\succeq B\succ O\Rightarrow B^{-1}\succeq A^{-1}$ .

Hint

(5) Reduce to the case $B=I$ by congruence with $B^{-1/2}$ .

Solution

(1) True. $\mathrm{tr}(AB)=\mathrm{tr}(A^{1/2}BA^{1/2})$ , and $A^{1/2}BA^{1/2}\succeq O$ since $x^\top A^{1/2}BA^{1/2}x=(A^{1/2}x)^\top B(A^{1/2}x)\ge0$ . Its trace is a sum of nonnegative eigenvalues.

(2) False. $A=\mathrm{diag}(1,0,\dots,0)$ , $B=\mathrm{diag}(0,1,0,\dots,0)$ .

(3) True. For any $v$ , $C=vv^\top\succeq O$ , and $\mathrm{tr}(Avv^\top)=v^\top Av\ge0$ .

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

(5) True. $A\succeq B$ gives $M:=B^{-1/2}AB^{-1/2}\succeq I$ (congruence preserves $\succeq$ ), so every eigenvalue of $M$ is at least 1 and every eigenvalue of $M^{-1}=B^{1/2}A^{-1}B^{1/2}$ is at most 1, i.e. $B^{1/2}A^{-1}B^{1/2}\preceq I$ . Congruence with $B^{-1/2}$ gives $A^{-1}\preceq B^{-1}$ .

2026 Problem 1Projection onto the PSD cone

$\mathbb S^n$ is the space of real symmetric matrices with $\langle A,B\rangle=\mathrm{tr}(AB)$ , and $\mathbb S^n_+$ the PSD ones. (1) Show $\mathbb S^n_+$ is convex. (2) Show $\lVert X-A\rVert^2$ has a unique minimizer $\phi(A)$ over $X\in\mathbb S^n_+$ and write it using the eigen-decomposition of $A$ . (3) Show $\langle A-\phi(A),X-\phi(A)\rangle\le0$ for all $X\in\mathbb S^n_+$ . (4) For $X,Y\in\mathbb S^n_+$ , show $\langle X,Y\rangle=0$ if and only if $X=\phi(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 $\phi(A)$ .

Solution

(1) $x^\top(\alpha X+(1-\alpha)Y)x=\alpha x^\top Xx+(1-\alpha)x^\top Yx\ge0$ .

(2) Write $A=Q\Lambda Q^\top$ . For PSD $X$ , $\tilde X=Q^\top XQ$ is PSD (so $\tilde X_{ii}\ge0$ ) and $\lVert X-A\rVert^2=\lVert\tilde X-\Lambda\rVert^2=\sum_i(\tilde X_{ii}-\lambda_i)^2+\sum_{i\ne j}\tilde X_{ij}^2\ge\sum_i(\tilde X_{ii}-\lambda_i)^2\ge\sum_{i:\lambda_i<0}\lambda_i^2$ . Equality holds throughout exactly when $\tilde X$ is diagonal with $\tilde X_{ii}=\max(\lambda_i,0)$ . So the minimizer exists and is unique: $\phi(A)=\sum_i\max(\lambda_i,0)\,q_iq_i^\top$ , where $q_i$ are orthonormal eigenvectors.

(3) Let $N=\sum_{\lambda_i<0}(-\lambda_i)q_iq_i^\top\succeq O$ . Then $A-\phi(A)=-N$ and $N\phi(A)=O$ (they live on orthogonal eigenvectors), so $\langle A-\phi(A),X-\phi(A)\rangle=-\langle N,X\rangle+\langle N,\phi(A)\rangle=-\mathrm{tr}(NX)\le0$ by the trace fact. (A general proof: for $t\in(0,1]$ , $\phi+t(X-\phi)$ is PSD by (1), so $\lVert\phi+t(X-\phi)-A\rVert^2\ge\lVert\phi-A\rVert^2$ ; expand, divide by $t$ , let $t\to0$ .)

(4) First, if $Z$ is PSD and $\langle A-Z,W-Z\rangle\le0$ for all PSD $W$ , then $\lVert W-A\rVert^2=\lVert W-Z\rVert^2+\lVert Z-A\rVert^2-2\langle A-Z,W-Z\rangle\ge\lVert Z-A\rVert^2$ , so $Z=\phi(A)$ by uniqueness. Now take $A=X-Y$ , $Z=X$ : the inequality reads $\langle -Y,W-X\rangle=\langle X,Y\rangle-\langle Y,W\rangle\le0$ for all PSD $W$ .

(i)⇒(ii): if $\langle X,Y\rangle=0$ , this is $-\mathrm{tr}(YW)\le0$ , true by the trace fact, so $X=\phi(X-Y)$ . (ii)⇒(i): if $X=\phi(X-Y)$ , (3) gives the inequality for all PSD $W$ . With $W=O$ : $\langle X,Y\rangle\le0$ . The trace fact gives $\langle X,Y\rangle\ge0$ . So $\langle X,Y\rangle=0$ .

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

Numbers match the book, which works over $\mathbb C$ with Hermitian matrices; read "real symmetric" and $^\top$ 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\in M_n$ and $B\in M_m$ have no eigenvalue in common. Show that $X\mapsto AX-XB$ is invertible on $n\times m$ matrices, by showing that $T_1(X)=AX$ and $T_2(X)=XB$ commute and that the eigenvalues of $T_1-T_2$ are differences of eigenvalues of $A$ and $B$ .

Hint

$T_1$ acts on each column of $X$ by $A$ ; $T_2$ acts on each row by $B^\top$ . Commuting linear maps can be triangularized in one basis (H&J 2.3.3).

Solution

$T_1T_2(X)=AXB=T_2T_1(X)$ . Acting column by column, $T_1$ is $I_m\otimes A$ , with the eigenvalues $\lambda_i$ of $A$ ; acting row by row, $T_2$ is $B^\top\otimes I_n$ , with the eigenvalues $\mu_j$ of $B$ . Triangularize $T_1$ and $T_2$ simultaneously: the diagonal of $T_1-T_2$ then consists of differences $\lambda_i-\mu_j$ , none of which is 0. So $T_1-T_2$ is invertible.

For 2020 P1, $BC+CB=A$ is $BC-C(-B)=A$ : the relevant differences are $\lambda_i-(-\lambda_j)=\lambda_i+\lambda_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\le\mathrm{tr}\,AB\le\lambda_{\max}(A)\,\mathrm{tr}\,B$ (the book writes $\lambda_{\max}(A)$ as the spectral norm $|||A|||_2$ ).

Hint

Move the square root of $B$ to both sides and use $A\preceq\lambda_{\max}(A)I$ .

Solution

$\mathrm{tr}\,AB=\mathrm{tr}(B^{1/2}AB^{1/2})$ . Since $O\preceq A\preceq\lambda_{\max}(A)I$ , congruence gives $O\preceq B^{1/2}AB^{1/2}\preceq\lambda_{\max}(A)B$ , and the trace is monotone for $\preceq$ (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\succeq B\succeq O$ , show $\mathrm{range}\,B\subseteq\mathrm{range}\,A$ .

Hint

Compare null spaces, then take orthogonal complements.

Solution

If $Ax=0$ , then $0=x^\top Ax\ge x^\top Bx=\lVert B^{1/2}x\rVert^2\ge0$ , so $B^{1/2}x=0$ and $Bx=0$ . Hence $\mathrm{null}\,A\subseteq\mathrm{null}\,B$ . For symmetric matrices $\mathrm{range}=(\mathrm{null})^\perp$ , so $\mathrm{range}\,B\subseteq\mathrm{range}\,A$ . 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\succ O$ and $B\succeq O$ . Show that $cA\succeq B$ for some $c>0$ , and that the smallest such $c$ is the spectral radius $\rho(A^{-1}B)$ .

Hint

Congruence by $A^{-1/2}$ .

Solution

$cA\succeq B\iff cI\succeq A^{-1/2}BA^{-1/2}\iff c\ge\lambda_{\max}(A^{-1/2}BA^{-1/2})$ . The matrix $A^{-1/2}BA^{-1/2}$ is PSD and similar to $A^{-1}B$ , so its largest eigenvalue is $\rho(A^{-1}B)$ . This generalized eigenvalue is a quick test for $A\succeq B$ : it holds exactly when $\rho(A^{-1}B)\le1$ (H&J 7.7.3).

Problem 7.7.P44Inverses reverse the order, from the definition

If $A\succeq B\succ O$ , prove $B^{-1}\succeq A^{-1}$ directly: show $x^\top B^{-1}x\ge x^\top A^{-1}x$ for every $x$ , starting from $(y-B^{-1}x)^\top B(y-B^{-1}x)\ge0$ .

Hint

Expand the square, use $A\succeq B$ on the $y^\top By$ term, then choose $y=A^{-1}x$ .

Solution

Expanding, $y^\top By-2y^\top x+x^\top B^{-1}x\ge0$ , i.e. $x^\top B^{-1}x\ge2y^\top x-y^\top By\ge2y^\top x-y^\top Ay$ , the last step because $y^\top Ay\ge y^\top By$ . With $y=A^{-1}x$ the right side is $2x^\top A^{-1}x-x^\top A^{-1}x=x^\top A^{-1}x$ . 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\succ O$ , let $H=\begin{pmatrix}B^{-1}&I\\I&A\end{pmatrix}$ . Compute the Schur complements of $B^{-1}$ and of $A$ in $H$ , and explain why $A\succeq B\iff H\succeq O\iff B^{-1}\succeq A^{-1}$ .

Hint

If $P\succ O$ , then $\begin{pmatrix}P&Q\\Q^\top&R\end{pmatrix}\succeq O$ if and only if $R-Q^\top P^{-1}Q\succeq O$ .

Solution

$H/B^{-1}=A-I\,B\,I=A-B$ and $H/A=B^{-1}-I\,A^{-1}I=B^{-1}-A^{-1}$ . The hint follows from the congruence $\begin{pmatrix}I&0\\-Q^\top P^{-1}&I\end{pmatrix}\begin{pmatrix}P&Q\\Q^\top&R\end{pmatrix}\begin{pmatrix}I&-P^{-1}Q\\0&I\end{pmatrix}=\begin{pmatrix}P&0\\0&R-Q^\top P^{-1}Q\end{pmatrix}$ . Applying it with either diagonal block as the pivot gives $A-B\succeq O\iff H\succeq O\iff B^{-1}-A^{-1}\succeq 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

\dot 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

\frac{\d}{\d t}L(x(t))=\nabla L\cdot F<0

away from

x^*

, solutions are drawn toward

x^*

. For Lotka–Volterra systems

\dot x_i=x_i(v_i+(Ax)_i)

, Volterra's choice

L=\sum c_i(x_i-x_i^*\log x_i)+\text{const}

gives

\dot L=\tfrac12 z^\top(CA+A^\top C)z

with

z=x-x^*

.

Conserved quantities from $\d y/\d x$ (Strogatz §6.5). In the plane, dividing the equations gives

\d y/\d x=\dot y/\dot x

. If that separates or is exact, integrating gives

H(x,y)=\text{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

\dot x\ge x^2

and

x(0)=1

, then

\frac{\d}{\d t}(-1/x)\ge1

, so

x(t)\ge1/(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/N\Z

,

e^{2\pi imn/N}

is an eigenvector of the second difference with eigenvalue

-4\sin^2(\pi m/N)

. On

(0,L)

with zero-flux (Neumann) ends,

\cos(k\pi x/L)

is an eigenfunction of

\partial_x^2

with eigenvalue

-(k\pi/L)^2

. Every nonzero mode decays; the mean (mode 0) survives.

Gradient flows. The Allen–Cahn equation $u_t=u-u^3+u_{xx}$ is the steepest descent of the energy $H(u)=\int(\tfrac14u^4-\tfrac12u^2+\tfrac12u_x^2)\,\d x$ : a double well that prefers $u=\pm1$ , 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.

Explore: an epidemic in the phase plane

\dot x=-2xy,\ \dot y=2xy-y

(2026 P3). Read

x

as the susceptible and

y

as the infected fraction. trajectory equilibria

y=0

x=\tfrac12

. Faint curves are level sets of

H=x+y-\tfrac12\log x

. Drag the dot.

Starting point

Jump to

Explore: phase separation

Equation

Initial data

Length L

Space–time picture:

x

across, time down.

u\approx+1

u\approx-1

; pale means mixed (

u\approx0

).

The profile

u(t,\cdot)

now, between

-1

and

1

.

Worked example

2026 P3(3): start with $x(0),y(0)>0$ , $x(0)+y(0)=1$ . Can $\lim_{t\to\infty}x(t)$ lie in $[\tfrac12,1)$ ?

Find a conserved quantity.

$\dfrac{\d y}{\d x}=\dfrac{2xy-y}{-2xy}=-1+\dfrac1{2x}$ , so $y=-x+\tfrac12\log x+\text{const}$ . Check: $H=x+y-\tfrac12\log x$ has $\dot H=-2xy+(2xy-y)-\tfrac12\cdot\dfrac{-2xy}{x}=0$ .
Show the limits $x_\infty$ , $y_\infty$ exist, with $y_\infty=0$ and $x_\infty>0$ .

From (2), $x,y>0$ , so $x$ strictly decreases and is bounded below: $x_\infty$ exists. $x+y$ decreases ( $\frac{\d}{\d t}(x+y)=-y$ ) and is bounded below, so it has a limit and $\int_0^\infty y\,\d t=1-\lim(x+y)<\infty$ ; with $y$ converging (as the difference of convergent functions), $y_\infty=0$ . Finally $\log x(t)=\log x(0)-2\int_0^ty$ , which stays bounded, so $x_\infty>0$ .
Use $H$ to locate $x_\infty$ .

Let $g(x)=x-\tfrac12\log x$ , which decreases on $(0,\tfrac12]$ and increases on $[\tfrac12,\infty)$ . Conservation gives $g(x_\infty)=H(x(0),y(0))=g(x(0))+y(0)>g(x(0))$ . If $x_\infty\ge\tfrac12$ , then $\tfrac12\le x_\infty<x(0)$ and $g$ increasing there gives $g(x_\infty)<g(x(0))$ , a contradiction. So $x_\infty<\tfrac12$ always, and no such solution exists.

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

Check your understanding

Along solutions of $\dot x=-2xy,\ \dot y=2xy-y$ with $x>0$ , which quantity is constant?

$x+y$ $\frac{\d}{\d t}(x+y)=-y$ , which is why $x+y\le1$ in (2).
$x+y-\tfrac12\log x$
$xy$ $\frac{\d}{\d t}(xy)=xy(2x-2y-1)$ , not zero in general.

Integrate

\d y/\d x=-1+1/(2x)

. The level sets of this

H

are the trajectories in the figure.

Linearize $u_t=u-u^3+u_{xx}$ at $u=0$ on $(0,L)$ with zero-flux ends. When does the mode $\cos(k\pi x/L)$ grow?

When $(k\pi/L)^2<1$
Always: the reaction term pushes away from 0Diffusion damps short waves at rate $(k\pi/L)^2$ , which can beat the reaction's rate 1.
Never: diffusion smooths everythingMode 0 (and other long waves) grow at rate $1-(k\pi/L)^2>0$ .

The linearization is

u_t=u+u_{xx}

, with growth rate

1-(k\pi/L)^2

. Long waves grow and short ones die, which is why small noise first turns into a few broad bumps. If

L<\pi

, only the mean grows.

If $\dot x\ge x^2$ and $x(0)=1$ , what can you conclude?

$x$ blows up at some $T\le1$ .
$x$ grows at least exponentially, but exists for all time.Compare with $\dot u=u^2$ , whose solution $1/(1-t)$ blows up at 1.
Nothing without an upper bound on $\dot x$ .A lower bound is exactly what forces blow-up.

\frac{\d}{\d t}(1/x)=-\dot x/x^2\le-1

, so

1/x(t)\le1-t

. This is the last step of 2026 P3(4).

Practice

Past problems

Restated in our own words. Official statements: 2020, 2023, 2025, 2026.

2020 Problem 4Discrete heat equation on a ring

$\partial_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\ge3$ . Let $e(m,n)=e^{2\pi imn/N}$ . (1) If $x(n,t)=e(m,n)f_m(t)$ is a solution with $f_m(0)=c_m$ , find $f_m$ . (2) Solve with $x(n,0)=g_n$ , $n=0,\dots,N-1$ . (3) Find $\lim_{t\to\infty}x(n,t)$ .

Hint

$e(m,n\pm1)=e(m,n)e^{\pm2\pi im/N}$ . For (2), expand $g$ in the discrete Fourier basis.

Solution

(1) Substituting, $f_m'=(e^{-2\pi im/N}+e^{2\pi im/N}-2)f_m=-4\sin^2(\pi m/N)f_m$ , so $f_m(t)=c_me^{-4\sin^2(\pi m/N)\,t}$ . Periodicity holds because $e(m,n+N)=e(m,n)$ .

(2) By orthogonality $\sum_{n=0}^{N-1}e(m,n)\overline{e(m',n)}=N\delta_{mm'}$ , $g_n=\sum_{m=0}^{N-1}c_me(m,n)$ with $c_m=\frac1N\sum_{n=0}^{N-1}g_ne^{-2\pi imn/N}$ . By linearity, $x(n,t)=\sum_{m=0}^{N-1}c_m\,e^{2\pi imn/N}e^{-4\sin^2(\pi m/N)t}$ . (It satisfies (*), (**), and the initial condition; uniqueness for this linear ODE system makes it the solution.)

(3) For $1\le m\le N-1$ , $\sin^2(\pi m/N)>0$ , so those terms vanish. The limit is $c_0=\frac1N\sum_ng_n$ , the average of the initial values, for every $n$ .

2023 Problem 2Stability of a Lotka–Volterra system

$A$ is a real nonsingular $n\times n$ matrix, $F_i(x)=x_i(v_i+\sum_ja_{ij}x_j)$ on the positive orthant, and $x^*$ is a positive equilibrium. Consider $\dot x=F(x)$ . (1) For $c>0$ and $L(x)=\sum_ic_i[x_i^*\log(x_i^*/x_i)-x_i^*+x_i]$ , show $\dot L(x')<0$ for every positive $x'\ne x^*$ if and only if $CA+A^\top C$ is negative definite ( $C=\mathrm{diag}(c)$ ). (2) With $H_w(z)=\tfrac12\sum w_iz_i^2$ and $z=x-x^*$ , find $G(z)$ with $\dot z=G(z)\nabla H_w(z)$ , in terms of $A$ , $W$ , $X^*$ , $Z$ . (3) If such a $c$ exists, find $w>0$ so that $\frac{\d}{\d t}H_w(z(t))<0$ whenever $z(t)$ is in a punctured neighbourhood of 0.

Hint

Use $v_i=-\sum_ja_{ij}x_j^*$ to rewrite $F_i=x_i(Az)_i$ . In (3), choose $W$ so that $WX^*=C$ .

Solution

(1) $\partial L/\partial x_i=c_i(1-x_i^*/x_i)=c_iz_i/x_i$ and $F_i=x_i(Az)_i$ , so $\dot L=\sum_ic_iz_i(Az)_i=z^\top CAz=\tfrac12z^\top(CA+A^\top 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 $\dot L<0$ for every $z\ne0$ .

(2) $\dot z_i=\dot x_i=(x_i^*+z_i)(Az)_i$ , and $\nabla H_w=Wz$ , so $z=W^{-1}\nabla H_w$ . Hence $G(z)=(X^*+Z)AW^{-1}$ .

(3) Take $w_i=c_i/x_i^*$ , so $W=C(X^*)^{-1}$ . Then $\frac{\d}{\d t}H_w=\nabla H_w^\top G\nabla H_w=z^\top W(X^*+Z)Az=z^\top CAz+z^\top C(X^*)^{-1}ZAz$ . The first term is $\le-\mu\lVert z\rVert^2$ with $\mu>0$ (half the smallest eigenvalue of $-(CA+A^\top C)$ ); the second is $O(\lVert z\rVert^3)$ . So the derivative is negative for small $z\ne0$ .

2025 Problem 2Allen–Cahn and phase separation

(A): $u_t=u-u^3+u_{xx}$ on $0<x<L$ , $u_x(t,0)=u_x(t,L)=0$ , $u(0,x)=f(x)$ with $\sup|f|<1$ . (1) Show $H(u)=\int_0^L(\tfrac14u^4-\tfrac12u^2+\tfrac12u_x^2)\,\d x$ is non-increasing in $t$ . (2) For (B) $u_t=u_{xx}$ with the same boundary and initial conditions, write $u=\sum_kb_ke^{c_kt}\cos(k\pi x/L)$ ; find $b_k,c_k$ and the limit as $t\to\infty$ . (3) Solve (C) $v'=v-v^3$ , $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|\ll1$ .

Hint

(1) Differentiate under the integral and integrate $u_xu_{xt}$ by parts. (3) Separate variables; partial fractions in $1/(v-v^3)$ , or solve for $v^2$ .

Solution

(1) $\frac{\d H}{\d t}=\int_0^L\big((u^3-u)u_t+u_xu_{xt}\big)\d x=\int_0^L(u^3-u-u_{xx})u_t\,\d x+\big[u_xu_t\big]_0^L=-\int_0^Lu_t^2\,\d x\le0$ , since the boundary term vanishes by the Neumann condition.

(2) Each term must solve (B): $c_k=-(k\pi/L)^2$ . Matching $t=0$ with the cosine series: $b_0=\frac1L\int_0^Lf$ , $b_k=\frac2L\int_0^Lf(x)\cos(k\pi x/L)\,\d x$ for $k\ge1$ . As $t\to\infty$ , $u\to b_0$ , the mean of $f$ .

(3) $\frac{\d}{\d t}(v^{-2})=-2v'/v^3=2-2v^{-2}$ (for $a\ne0$ ), so $v^{-2}-1=(a^{-2}-1)e^{-2t}$ , giving $v(t)=\dfrac{ae^t}{\sqrt{1-a^2+a^2e^{2t}}}$ (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 $\pm1$ (0 is unstable), producing noise-scale fragments. In (A) they compete: $H$ is a double-well energy minimized by $u=\pm1$ 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|\ll1$ : an early linear stage where long-wave modes with $(k\pi/L)^2<1$ grow like $e^{(1-(k\pi/L)^2)t}$ and short ones decay; then saturation into plateaus at $\pm1$ joined by $\tanh$ -shaped interfaces of width about $\sqrt2$ ; 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

$\dot x=-2xy,\ \dot 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\ge0$ and $x+y\le1$ for $t\ge0$ . (3) Under (2), can $\tfrac12\le\lim x(t)<1$ ? (4) From $(1,-1)$ , show $x(t)\to\infty$ as $t\uparrow T$ for some finite $T>0$ .

Hint

(2) Write $x(t)=x(0)\exp(-2\int_0^ty)$ . (4) On the conserved level through $(1,-1)$ , express $y$ in terms of $x$ and compare with $\dot x\ge x^2$ .

Solution

(1) $-2xy=0$ and $y(2x-1)=0$ . If $y\ne0$ 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\in\R$ .

(2) $x(t)=x(0)e^{-2\int_0^ty}>0$ and $y(t)=y(0)e^{\int_0^t(2x-1)}>0$ . Then $\frac{\d}{\d t}(x+y)=-y\le0$ , so $x+y\le1$ .

(3) No; see the worked example: $\lim x(t)<\tfrac12$ always.

(4) $y(t)=-e^{\int_0^t(2x-1)}<0$ for all $t$ , so $\dot x=-2xy>0$ while $x>0$ : $x$ increases from 1. $H=x+y-\tfrac12\log x$ equals $0$ at $(1,-1)$ , so $y=\tfrac12\log x-x$ and $\dot x=x(2x-\log x)$ . Since $\log x\le x-1$ , $2x-\log x\ge x+1>x$ , so $\dot x>x^2$ with $x(0)=1$ , and $x(t)\ge1/(1-t)$ . Hence the solution cannot exist on $[0,1)$ with $x$ finite: there is $T\le1$ with $x(t)\to\infty$ as $t\uparrow T$ . In fact $T=\int_1^\infty\frac{\d x}{x(2x-\log x)}\approx0.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\ge0$ and sick $y\ge0$ evolve by $\dot x=-kxy$ , $\dot y=kxy-\ell y$ with $k,\ell>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\to\infty$ ? (e) An epidemic occurs if $y$ increases at first. When does that happen?

Hint

(c) Form $\d y/\d x$ and separate variables. With $k=2$ , $\ell=1$ this is the exam's system.

Solution

(a) $kxy=0$ and $y(kx-\ell)=0$ force $y=0$ : every point $(x^*,0)$ is fixed, a whole line of them. The Jacobian there is $\begin{pmatrix}0&-kx^*\\0&kx^*-\ell\end{pmatrix}$ , with eigenvalues $0$ (along the line) and $kx^*-\ell$ . Points with $x^*<\ell/k$ attract nearby trajectories; points with $x^*>\ell/k$ repel them. Being non-isolated, none is a node or saddle in the usual sense.

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

(c) $\d y/\d x=-1+\ell/(kx)$ , so $E=kx+ky-\ell\log x$ is conserved.

(d) Every trajectory in the open quadrant ends on the line of fixed points at some $x_\infty<\ell/k$ , with $y\to0$ : the argument of the worked example, with $\ell/k$ in place of $\tfrac12$ .

(e) $\dot y(0)=y_0(kx_0-\ell)>0$ exactly when $x_0>\ell/k$ : the epidemic threshold. In the exam's units, $\ell/k=\tfrac12$ , which is why the gold line in the figure sits at $x=\tfrac12$ , and why 2026 P3(3) asks about $[\tfrac12,1)$ .

Exercise 2.5.2Blow-up without an exact solution

Show that every solution of $\dot x=1+x^{10}$ escapes to $+\infty$ in finite time.

Hint

Don't solve it. Compare with $\dot x=1+x^2$ , whose solutions are shifted tangents.

Solution

Since $\dot x\ge1$ , $x$ reaches the value 1 by time $t_1=\max(0,1-x_0)$ . From then on $x\ge1$ , so $x^{10}\ge x^2$ and $\dot x\ge1+x^2$ , i.e. $\frac{\d}{\d t}\arctan x\ge1$ . Hence $\arctan x(t)\ge\frac\pi4+(t-t_1)$ , which reaches $\frac\pi2$ by $t=t_1+\frac\pi4$ : $x$ must blow up before then. This is the same comparison as 2026 P3(4), where $\dot x=x(2x-\log x)\ge x^2$ .

Exercise 6.4.1Two competing species

For $\dot x=x(3-x-y)$ , $\dot y=y(2-x-y)$ with $x,y\ge0$ , find and classify the fixed points and describe the long-run behaviour.

Hint

Look at $\frac{\d}{\d t}\log(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 $\begin{pmatrix}3-2x-y&-x\\-y&2-x-2y\end{pmatrix}$ . At $(0,0)$ : eigenvalues 3, 2, an unstable node. At $(3,0)$ : $\begin{pmatrix}-3&-3\\0&-1\end{pmatrix}$ , eigenvalues $-3,-1$ , a stable node. At $(0,2)$ : $\begin{pmatrix}1&0\\-2&-2\end{pmatrix}$ , eigenvalues $1,-2$ , a saddle.

Globally, for $x,y>0$ , $\frac{\d}{\d t}\log(x/y)=(3-x-y)-(2-x-y)=1$ , so $y/x\to0$ 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 $\dot x=y-x^3$ , $\dot y=-x-y^3$ has no closed orbits, by finding $V=ax^2+by^2$ that decreases along trajectories.

Solution

$\dot V=2ax(y-x^3)+2by(-x-y^3)=2(a-b)xy-2ax^4-2by^4$ . With $a=b=1$ the cross term cancels and $\dot V=-2(x^4+y^4)<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 $\pm i$ .

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

Show that $V=ax^2+2bxy+cy^2$ is positive definite if and only if $a>0$ and $ac-b^2>0$ .

Solution

If $a\le0$ , $V(1,0)=a\le0$ . If $a>0$ , complete the square: $V=a\big(x+\tfrac bay\big)^2+\tfrac{ac-b^2}a\,y^2$ , positive for all $(x,y)\ne0$ exactly when $ac-b^2>0$ . This is the $2\times2$ case of the leading-minor test for $\begin{pmatrix}a&b\\b&c\end{pmatrix}\succ O$ , the matrix fact behind 2023 P2(1) (see module 2).

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)\ge f(x)+\nabla f(x)^\top(y-x)

for all

x,y

. With

y=x^*

:

f(x)-f^*\le\nabla f(x)^\top(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(x_k)-f^*\le L\lVert x_0-x^*\rVert^2/(2k)

. Nesterov's accelerated method,

y_k=x_k+\frac{k-1}{k+2}(x_k-x_{k-1})

,

x_{k+1}=y_k-\frac1L\nabla f(y_k)

, achieves

O(1/k^2)

, which is optimal for first-order methods in this class.

The continuous-time picture. Letting the step size shrink, Nesterov's method tracks $\ddot x+\frac3t\dot x+\nabla f(x)=0$ (Su, Boyd and Candès). 2024 P2 writes a shifted version as a first-order system in $(x,v)$ with $\dot x=\frac2{t+1}(v-x)$ and $\dot v=-\frac{t+1}2\nabla f(x)$ , and the energy $E(t)=(t+1)^2(f(x)-f^*)+2\lVert v-x^*\rVert^2$ . The growing weight $(t+1)^2$ on the gap is the rate.

Discrete energies. For sequences,

\delta^+y^{(k)}=(y^{(k+1)}-y^{(k)})/h

obeys a product rule

\delta^+(a^{(k)}b^{(k)})=(\delta^+a^{(k)})b^{(k+1)}+a^{(k)}\delta^+b^{(k)}

and

\delta^+\lVert y^{(k)}\rVert^2=2y^{(k+1)\top}\delta^+y^{(k)}-h\lVert\delta^+y^{(k)}\rVert^2

. The extra

-h\lVert\cdot\rVert^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

x_{k+1}=\mathrm{prox}_{\gamma g}(x_k-\gamma\nabla f(x_k))

, where

\mathrm{prox}_{\gamma g}(y)=\arg\min_u\big(g(u)+\frac1{2\gamma}\lVert u-y\rVert^2\big)

. For

g=\lambda\lVert\cdot\rVert_1

the prox is soft-thresholding; for

g

the indicator of a convex set it is the projection (for the PSD cone, the

\phi

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^\top x:Ax\le b,\ x\ge0\}

the dual is

\min\{b^\top y:A^\top y\ge c,\ y\ge0\}

. Weak duality

c^\top x\le b^\top y

is one line; strong duality says the optima are equal when either is finite, and complementary slackness

y^\top(b-Ax)=0=x^\top(A^\top y-c)

characterizes optimal pairs. The max-flow min-cut theorem and the minimum-cost flow optimality conditions are special cases.

Explore

Condition number κ

gradient descent (dashed, a dot every 10 steps) Nesterov, both with step

1/L

. Drag the start.

f(x_k)-f^*

against

k

on log–log axes. Dashed guides have slopes

-1

and

-2

.

Worked example

2024 P2(1): show $\dot E\le0$ for $E(t)=(t+1)^2(f(x)-f^*)+2\lVert v-x^*\rVert^2$ , then deduce $f(x(t))-f^*\le C/t^2$ .

Differentiate each term of $E$ .

$\dot E=2(t+1)(f-f^*)+(t+1)^2\nabla f^\top\dot x+4(v-x^*)^\top\dot v$ .
Substitute the dynamics.

$(t+1)^2\nabla f^\top\dot x=2(t+1)\nabla f^\top(v-x)$ and $4(v-x^*)^\top\dot v=-2(t+1)\nabla f^\top(v-x^*)$ . The $v$ terms cancel: $\dot E=2(t+1)\big[f(x)-f^*-\nabla f(x)^\top(x-x^*)\big]$ .
Finish with convexity.

The bracket is $\le0$ by $f^*\ge f(x)+\nabla f(x)^\top(x^*-x)$ . So $E(t)\le E(0)$ , and $f(x(t))-f^*\le E(0)/(t+1)^2\le E(0)/t^2$ : take $C=E(0)=f(x(0))-f^*+2\lVert v(0)-x^*\rVert^2$ .

Check your understanding

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

Convexity, in the form $f(x^*)\ge f(x)+\nabla f(x)^\top(x^*-x)$
Strong convexityNot assumed; with it you would get a linear rate.
A Lipschitz gradientNeeded for discrete step-size choices in general, but not in the continuous-time argument.

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?

$O(1/k)$
$O(1/k^2)$ That is the accelerated rate.
Linear, $O(\rho^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/k^2

for Nesterov, and no first-order method can beat

1/k^2

in general.

What is $\mathrm{prox}_{\gamma\lambda|\cdot|}(y)$ for $y\in\R$ ?

$\mathrm{sign}(y)\max(|y|-\gamma\lambda,0)$
$y/(1+\gamma\lambda)$ That is the prox of $\frac\lambda2y^2$ .
$\max(y,0)$ That is projection onto $[0,\infty)$ , the prox of its indicator.

Minimize

\lambda|u|+\frac1{2\gamma}(u-y)^2

: the optimality condition

0\in\lambda\,\partial|u|+(u-y)/\gamma

gives soft-thresholding. Proximal gradient with this prox is ISTA for the lasso.

Practice

Past problem

Restated in our own words. Official statement: 2024. 2024 P1 and 2026 P1 are optimization problems too; they are worked in module 2.

2024 Problem 2Accelerated gradient as a differential equation

$f$ is smooth and convex on $\R^d$ with a minimizer $x^*$ . (1) For the system above, show $\dot E\le0$ and $f(x(t))-f^*\le C/t^2$ . (2) Discretize as $\delta^+x^{(k)}=\frac{2hk+h+2}{(hk+1)^2}(v^{(k+1)}-x^{(k+1)})$ , $\delta^+v^{(k)}=-\frac{2hk+h+2}4\nabla f(x^{(k+1)})$ , with $E^{(k)}=(hk+1)^2(f(x^{(k)})-f^*)+2\lVert v^{(k)}-x^*\rVert^2$ . Show $\delta^+\lVert v^{(k)}-x^*\rVert^2=2(v^{(k+1)}-x^*)^\top\delta^+v^{(k)}-h\lVert\delta^+v^{(k)}\rVert^2$ and $\delta^+E^{(k)}\le0$ . (3) Show $f(x^{(k)})-f^*\le C'/k^2$ .

Hint

Write $s_k=2hk+h+2$ and $A_k=(hk+1)^2$ . Then $\delta^+A_k=s_k$ : 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^*$ : $\lVert a\rVert^2-\lVert b\rVert^2=2a^\top(a-b)-\lVert a-b\rVert^2$ . Divide by $h$ and use $a-b=h\,\delta^+v^{(k)}$ .

Now $(h(k+1)+1)^2-(hk+1)^2=h(2hk+h+2)$ , so $\delta^+A_k=s_k$ . Write $D_k=f(x^{(k)})-f^*$ and $g=\nabla f(x^{(k+1)})$ . The product rule gives $\delta^+E^{(k)}=s_kD_{k+1}+A_k\,\delta^+D_k+4(v^{(k+1)}-x^*)^\top\delta^+v^{(k)}-2h\lVert\delta^+v^{(k)}\rVert^2$ .

Convexity between $x^{(k)}$ and $x^{(k+1)}$ : $f(x^{(k)})\ge f(x^{(k+1)})+g^\top(x^{(k)}-x^{(k+1)})$ , so $\delta^+D_k\le g^\top\delta^+x^{(k)}=\frac{s_k}{A_k}g^\top(v^{(k+1)}-x^{(k+1)})$ .
The $v$ update: $4(v^{(k+1)}-x^*)^\top\delta^+v^{(k)}=-s_kg^\top(v^{(k+1)}-x^*)$ .

Adding, the $v^{(k+1)}$ terms cancel: $\delta^+E^{(k)}\le s_k\big[f(x^{(k+1)})-f^*-g^\top(x^{(k+1)}-x^*)\big]-2h\lVert\delta^+v^{(k)}\rVert^2\le0$ , by convexity between $x^{(k+1)}$ and $x^*$ .

(3) $E^{(k)}\le E^{(0)}$ , so $f(x^{(k)})-f^*\le E^{(0)}/(hk+1)^2\le E^{(0)}/(h^2k^2)$ . Take $C'=E^{(0)}/h^2$ .

Fresh practiceThe dual of a transportation LP

Supplies $a_i\ge0$ at sources $i$ , demands $b_j\ge0$ at sinks $j$ with $\sum a_i=\sum b_j$ , and costs $c_{ij}$ . Write the LP for the cheapest shipment $x_{ij}\ge0$ , its dual, and the complementary slackness conditions. Interpret the dual variables.

Solution

Primal: minimize $\sum c_{ij}x_{ij}$ subject to $\sum_jx_{ij}=a_i$ , $\sum_ix_{ij}=b_j$ , $x\ge0$ . Dual: maximize $\sum_ia_iu_i+\sum_jb_jv_j$ subject to $u_i+v_j\le c_{ij}$ (free $u,v$ , because the primal constraints are equalities). Complementary slackness: $x_{ij}>0\Rightarrow u_i+v_j=c_{ij}$ . Read $-u_i$ as the price paid to pick up a unit at $i$ and $v_j$ 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\subseteq\R^n$ be nonempty, closed and convex. Show that every $x_0$ 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\in C$ . The nearest point, if any, lies in $C\cap\{x:\lVert x-x_0\rVert\le\lVert c-x_0\rVert\}$ , which is closed and bounded, hence compact, and $\lVert x-x_0\rVert$ is continuous: a minimizer exists. If $x\ne y$ both attain the minimum distance $d$ , then $m=\frac{x+y}2\in C$ by convexity, and the parallelogram law gives $\lVert m-x_0\rVert^2=\frac{d^2+d^2}2-\frac{\lVert x-y\rVert^2}4<d^2$ , a contradiction. With matrices and $\langle A,B\rangle=\mathrm{tr}(AB)$ in place of $\R^n$ , 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 $x_0$ onto $\R^n_+$ replaces each negative entry by 0. (b) Show that the Frobenius projection of a symmetric $X_0=\sum_i\lambda_iv_iv_i^\top$ onto the PSD cone is $\sum_i\max(\lambda_i,0)v_iv_i^\top$ .

Hint

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

Solution

(a) $\lVert x-x_0\rVert^2=\sum_k(x_k-x_{0k})^2$ , and each term is minimized over $x_k\ge0$ at $x_k=\max(x_{0k},0)$ . (b) Exactly the argument of 2026 P1(2): in the eigenbasis of $X_0$ , off-diagonal entries only add to the distance and the diagonal is problem (a). Part (a) also explains the variational inequality there: $x_0-P(x_0)$ is the negative part of $x_0$ , which is orthogonal to $P(x_0)$ and has non-positive inner product with every point of the orthant.

Exercise 2.28The PSD cone in coordinates

Describe $\mathbb S^n_+$ by inequalities on the entries for $n=1,2,3$ , writing a general element as $x_1$ , $\begin{pmatrix}x_1&x_2\\x_2&x_3\end{pmatrix}$ and $\begin{pmatrix}x_1&x_2&x_3\\x_2&x_4&x_5\\x_3&x_5&x_6\end{pmatrix}$ .

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$ : $x_1\ge0$ . $n=2$ : $x_1\ge0$ , $x_3\ge0$ , $x_1x_3\ge x_2^2$ . $n=3$ : $x_1,x_4,x_6\ge0$ ; $x_1x_4\ge x_2^2$ , $x_1x_6\ge x_3^2$ , $x_4x_6\ge x_5^2$ ; and $\det\ge0$ . For $n=2$ the cone is a round cone in $(x_1,x_2,x_3)$ -space ( $x_1x_3\ge x_2^2$ with $x_1+x_3\ge0$ ), which is why the ellipse picture in module 2 works: each interior point of this cone is an ellipse. Only checking the leading minors $x_1\ge0$ , $x_1x_3-x_2^2\ge0$ would wrongly admit $\mathrm{diag}(0,-1)$ .

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

For the LP $\min\{c^\top x:Ax\preceq b\}$ and any $w\succeq0$ , every feasible $x$ satisfies $w^\top Ax\le w^\top b$ . (a) Find $\min\{c^\top x:w^\top Ax\le w^\top 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 $-\infty$ unless $c$ points out of it: unless $c=-\lambda A^\top w$ for some $\lambda\ge0$ . Then $c^\top x=-\lambda w^\top Ax\ge-\lambda w^\top b$ , with equality on the boundary, so the minimum is $-\lambda w^\top b$ . (b) Maximize $-\lambda w^\top b$ over $w\succeq0$ , $\lambda\ge0$ with $c=-\lambda A^\top w$ . (c) Put $z=\lambda w$ : maximize $-b^\top z$ subject to $A^\top z+c=0$ , $z\succeq0$ . 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", the same reasoning as the worked example in module 10.

Exercise 5.5The dual of a general LP

Find the dual function and dual problem of $\min\{c^\top x:Gx\preceq h,\ Ax=b\}$ , with the implicit constraints made explicit.

Solution

$L(x,\lambda,\nu)=c^\top x+\lambda^\top(Gx-h)+\nu^\top(Ax-b)=(c+G^\top\lambda+A^\top\nu)^\top x-h^\top\lambda-b^\top\nu$ . Minimizing over $x$ : $g(\lambda,\nu)=-h^\top\lambda-b^\top\nu$ if $c+G^\top\lambda+A^\top\nu=0$ , and $-\infty$ otherwise. Dual: maximize $-h^\top\lambda-b^\top\nu$ subject to $G^\top\lambda+A^\top\nu+c=0$ , $\lambda\succeq0$ . Inequality constraints get sign-constrained multipliers; equalities get free ones, which is the pattern behind the transportation dual above.

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

\Gamma

except for isolated poles

z_k

inside, then

\oint_\Gamma g\,\d z=2\pi i\sum_k\mathrm{Res}_{z_k}g

. At a simple pole of

p/q

with

q(z_k)=0\ne q'(z_k)

, the residue is

p(z_k)/q'(z_k)

; 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)}(z_0)|\le n!\,\lVert f\rVert_C/R^n

, bound Taylor coefficients by

\lVert f\rVert R^{-n}

, which is the other route to the trapezoid bound below.

Parametrize the circle. On $|z|=1$ , $z=e^{i\theta}$ and $\d\theta=-i\,\d z/z$ , so $\int_0^{2\pi}f(e^{i\theta})\d\theta=\oint\frac{-i}zf(z)\,\d z$ . Since $\frac{z^{N-1}}{z^N-1}$ has simple poles of residue $\frac1N$ at the $N$ -th roots of unity, the equally weighted sum $\frac{2\pi}N\sum_kf(e^{2\pi 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

\lVert t'\rVert_\infty\le n\lVert t\rVert_\infty

. So if

f

is approximated within

c/n^3

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

t_n\to f

uniformly and

t_n'\to s

uniformly with

s

continuous, then

f

is differentiable with

f'=s

. Proof: pass to the limit in

t_n(\theta)-t_n(0)=\int_0^\theta t_n'

, 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

\int_0^1Q(u)\,\d u

, and the median is

Q(\tfrac12)

. So "mean minus median" is

\int_0^{1/2}\big(Q(\tfrac12+v)+Q(\tfrac12-v)-2Q(\tfrac12)\big)\d v

, which is positive whenever

Q

is strictly convex, i.e. whenever

f

is strictly decreasing.

Exchanging limits. 2023 P1(3) takes

n\to\infty

and then

m\to\infty

. Each limit is a Riemann sum of a continuous function; say so explicitly rather than exchanging silently.

Explore

\log_{10}|I(f)-I_N(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

Pole position a

Worked example

2023 P3(4): show the constant $2\pi$ in $|I(f)-I_N(f)|\le\dfrac{2\pi\lVert f\rVert}{r^N-1}$ cannot be improved, i.e. $\limsup_N\big(r^N\sup_f|I(f)-I_N(f)|/\lVert f\rVert\big)=2\pi$ .

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

$f(z)=z^N$ . Its integral over the circle is $I=\int_0^{2\pi}e^{iN\theta}\d\theta=0$ , but at every node $z^N=1$ , so $I_N=2\pi$ . The error is $2\pi$ .
Compute the ratio for this $f$ .

$\lVert f\rVert=\sup_{|z|<r}|z|^N=r^N$ , so $r^N|I-I_N|/\lVert f\rVert=2\pi$ . Hence the sup is at least $2\pi$ for every $N$ .
Combine with the upper bound.

From (3), the quantity is at most $2\pi r^N/(r^N-1)\to2\pi$ . With the lower bound $2\pi$ , the limsup (in fact the limit) is $2\pi$ .

Check your understanding

The $N$ -point trapezoid rule on the circle is exact for $z^k$ exactly when:

$k$ is not a nonzero multiple of $N$
$|k|\le N$ $k=N$ is the worst case: error $2\pi$ .
alwaysThe nodes can't tell $z^N$ from the constant 1.

\frac1N\sum_{j=1}^N\omega^{jk}

is 1 if

N\mid k

and 0 otherwise. This aliasing is the whole error: for

f=\sum a_kz^k

,

I_N-I=2\pi\sum_{m\ge1}a_{mN}

, and

|a_{mN}|\le\lVert f\rVert r^{-mN}

by Cauchy's estimate, which is another proof of the bound.

If $\lVert f-t_n\rVert\le c/n^3$ for trigonometric polynomials $t_n$ of degree $n$ , what can you conclude?

$f$ is continuously differentiable
$f$ is analyticAnalyticity needs geometric rates $\rho^n$ , not polynomial ones.
Nothing beyond continuityBernstein's inequality converts the approximation rate into control of derivatives.

This is 2024 P3. The same argument gives

C^1

from any rate

n^{-2-\varepsilon}

: after multiplying by

n

it is still summable.

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

mean > median
mean < medianThe long tail is on the right.
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

\tfrac34

above median

\tfrac23

for a density that isn't decreasing, which is why part (4) asks about every sub-interval.

Practice

Past problems

Restated in our own words. Official statements: 2023, 2024, 2025.

2023 Problem 1A log-average dissimilarity

For finite real sequences $A=\{a_i\}_{i=1}^m$ , $B=\{b_j\}_{j=1}^n$ , let $f(A,B)=\ln\Big(\frac1m\sum_i\frac1{K_i}\Big)$ with $K_i=\frac1n\sum_je^{-|a_i-b_j|}$ . (1) Show $f\ge0$ and find when $f=0$ . (2) Show $f(A,C)\le f(A,B)+f(B,C)$ . (3) With $A_m(s)=\{s+i/m\}$ , $B_n=\{j/n\}$ , find $h$ with $g(s)=\lim_m\lim_nf(A_m(s),B_n)=\ln\int_s^{1+s}\frac{\d z}{h(z)}$ . (4) Find the $s$ minimizing $g$ .

Hint

(2) $e^{-|a-c|}\ge e^{-|a-b|}e^{-|b-c|}$ gives, for every $j$ , $\frac1{K^{AC}_i}\le\frac{e^{|a_i-b_j|}}{K^{BC}_j}$ . Average this over $j$ with weights proportional to $e^{-|a_i-b_j|}$ . (4) $h$ is symmetric about $\tfrac12$ .

Solution

(1) $0<K_i\le1$ , so each $1/K_i\ge1$ and $f\ge\ln1=0$ . Equality needs every $K_i=1$ , i.e. $a_i=b_j$ for all $i,j$ : all entries of $A$ and $B$ are one common number. Conversely that gives $f=0$ .

(2) Write $K^{AB}_i$ , $K^{BC}_j$ , $K^{AC}_i$ for the three averages. For each $j$ , $K^{AC}_i=\frac1p\sum_le^{-|a_i-c_l|}\ge e^{-|a_i-b_j|}K^{BC}_j$ , so $1/K^{AC}_i\le e^{|a_i-b_j|}/K^{BC}_j$ . Average over $j$ with weights $q_j=e^{-|a_i-b_j|}/(nK^{AB}_i)$ , which sum to 1: $\frac1{K^{AC}_i}\le\sum_jq_j\frac{e^{|a_i-b_j|}}{K^{BC}_j}=\frac1{K^{AB}_i}\cdot\frac1n\sum_j\frac1{K^{BC}_j}$ . Averaging over $i$ gives $e^{f(A,C)}\le e^{f(A,B)}e^{f(B,C)}$ .

(3) As $n\to\infty$ , $K_i$ is a Riemann sum for $h(a_i)=\int_0^1e^{-|a_i-y|}\d y$ . Then the outer average is a Riemann sum for $\int_0^1\frac{\d u}{h(s+u)}$ ( $h$ is continuous and positive). So $h(z)=2-e^{-z}-e^{z-1}$ for $0\le z\le1$ , $h(z)=(1-e^{-1})e^z$ for $z<0$ , and $h(z)=(1-e^{-1})e^{1-z}$ for $z>1$ .

(4) $G(s)=\int_s^{s+1}\d z/h(z)$ has $G'(s)=1/h(s+1)-1/h(s)$ . Since $h(z)=h(1-z)$ and $h$ strictly increases on $(-\infty,\tfrac12]$ , $G'<0$ for $s<0$ and $G'>0$ for $s>0$ (the endpoint closer to $\tfrac12$ 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 $D_r=\{|z|<r\}$ , $\lVert f\rVert=\sup_{D_r}|f|$ , $I(f)=\int_0^{2\pi}f(e^{i\theta})\d\theta$ and $I_N(f)=\frac{2\pi}N\sum_{k=1}^Nf(e^{2\pi ik/N})$ . (1) Show $I(f)=\oint_{|z|=1}\frac{-i}zf(z)\,\d z$ . (2) Find the poles of $g_N[f](z)=\frac{-iz^{N-1}}{z^N-1}f(z)$ in $D_r$ and the residues. (3) If $\lVert f\rVert<\infty$ , show $|I(f)-I_N(f)|\le2\pi\lVert f\rVert/(r^N-1)$ . (4) Show the constant $2\pi$ is optimal.

Hint

(3) Express both $I$ and $I_N$ as integrals over $|z|=R$ for $1<R<r$ , subtract, and simplify $\frac1z-\frac{z^{N-1}}{z^N-1}$ .

Solution

(1) With $z=e^{i\theta}$ , $\d z=iz\,\d\theta$ , so $\d\theta=-i\,\d z/z$ .

(2) The poles are the zeros of $z^N-1$ , the roots of unity $\omega_k=e^{2\pi ik/N}$ , all simple and inside $D_r$ . $\mathrm{Res}_{\omega_k}=\frac{-i\omega_k^{N-1}f(\omega_k)}{N\omega_k^{N-1}}=-\frac iNf(\omega_k)$ (the pole is removable if $f(\omega_k)=0$ ).

(3) Fix $1<R<r$ . By the residue theorem, $\oint_{|z|=R}g_N=2\pi i\sum_k(-\tfrac iN)f(\omega_k)=I_N$ . The integrand $-if/z$ has only the pole at 0, so (1) also holds on $|z|=R$ . Subtracting, $I-I_N=\oint_{|z|=R}(-i)f(z)\Big(\frac1z-\frac{z^{N-1}}{z^N-1}\Big)\d z=\oint_{|z|=R}\frac{i\,f(z)}{z(z^N-1)}\d z$ . On $|z|=R$ , $|z^N-1|\ge R^N-1$ , so $|I-I_N|\le2\pi R\cdot\frac{\lVert f\rVert}{R(R^N-1)}$ . Let $R\uparrow r$ .

(4) The worked example.

2024 Problem 3Fast approximation implies differentiability

$\mathcal T_n$ is the set of functions $\theta\mapsto P(e^{i\theta})$ with $P$ a complex polynomial of degree $n$ . $f$ is continuous and $2\pi$ -periodic, and for each $n$ some $t_n\in\mathcal T_n$ has $\lVert f-t_n\rVert\le c/n^3$ . (1) Show $\lVert t_{n+1}-t_n\rVert\le2c/n^3$ . (2) Using completeness of $C[0,2\pi]$ and $\lVert t'\rVert\le n\lVert t\rVert$ for $t\in\mathcal T_n$ , show $t_n'$ converges uniformly to a continuous periodic $s$ . (3) Show $f$ is differentiable on $\R$ .

Solution

(1) $\lVert t_{n+1}-t_n\rVert\le\lVert t_{n+1}-f\rVert+\lVert f-t_n\rVert\le\frac c{(n+1)^3}+\frac c{n^3}\le\frac{2c}{n^3}$ .

(2) $t_{n+1}-t_n$ comes from a polynomial of degree at most $n+1$ , so Bernstein's inequality (which holds for degree at most $n+1$ ) gives $\lVert t_{n+1}'-t_n'\rVert\le(n+1)\frac{2c}{n^3}\le\frac{4c}{n^2}$ . For $m>n$ , $\lVert t_m'-t_n'\rVert\le\sum_{k\ge n}4c/k^2\to0$ : the sequence is Cauchy in the sup norm, so it converges uniformly to some continuous $s$ . Each $t_n'$ is $2\pi$ -periodic, hence so is $s$ .

(3) $t_n(\theta)-t_n(0)=\int_0^\theta t_n'$ . Let $n\to\infty$ , using uniform convergence on both sides: $f(\theta)=f(0)+\int_0^\theta s$ . Since $s$ is continuous, $f$ is differentiable with $f'=s$ , on $[0,2\pi]$ and then on $\R$ by periodicity.

2025 Problem 3Mean versus median

$\mathcal F_{a,b}$ is the set of continuous densities on $(a,b)$ with $\inf f>0$ . (1) For $g\in\mathcal F_{0,5/3}$ equal to $\tfrac32x+\tfrac12$ on $(0,\tfrac13]$ , $-\tfrac32x+\tfrac32$ on $(\tfrac13,\tfrac23]$ , $\tfrac12$ on $(\tfrac23,\tfrac53)$ , find the mean and median. (2) With $Q=F^{-1}$ , show the mean is $\int_0^1Q$ . (3) If $f$ is strictly decreasing, show mean > median. (4) If $f'$ is continuous and for every $a<c<d<b$ the normalized restriction $f_{cd}$ has mean > median, show $f$ is strictly decreasing.

Solution

(1) The three pieces have mass $\tfrac14,\tfrac14,\tfrac12$ , so the CDF at $\tfrac23$ is $\tfrac12$ : median $\tfrac23$ . $\int x\,g$ over the pieces is $\tfrac5{108}+\tfrac{13}{108}+\tfrac{63}{108}=\tfrac34$ : mean $\tfrac34$ .

(2) $F$ is $C^1$ with $F'=f>0$ , a bijection $(a,b)\to(0,1)$ . Substituting $x=Q(u)$ , $\d u=f(x)\d x$ : $\int_a^bxf(x)\d x=\int_0^1Q(u)\d u$ .

(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 $=\int_0^1(Q(u)-Q(\tfrac12))\d u=\int_0^{1/2}\big(Q(\tfrac12+v)+Q(\tfrac12-v)-2Q(\tfrac12)\big)\d v>0$ .

(4) Contrapositive. Suppose $f$ is not strictly decreasing. If $f'(x_0)>0$ somewhere, then by continuity $f'>0$ on some $[c,d]$ , $f_{cd}$ is strictly increasing, and the mirror of (3) ( $Q$ strictly concave) gives mean < median. Otherwise $f'\le0$ 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 $f_{cd}$ 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 $\displaystyle\int_0^{2\pi}\frac{\d\theta}{a+b\cos\theta}=\frac{2\pi}{\sqrt{a^2-b^2}}$ whenever $a>|b|$ , $a,b$ real.

Hint

Substitute $z=e^{i\theta}$ , so $\cos\theta=\frac12(z+z^{-1})$ and $\d\theta=-i\,\d z/z$ , as in 2023 P3(1).

Solution

For $b=0$ it is immediate. Otherwise the integral becomes $\oint_{|z|=1}\frac{-2i\,\d z}{bz^2+2az+b}$ . The roots $z_\pm=\frac{-a\pm\sqrt{a^2-b^2}}b$ are real with $z_+z_-=1$ , and $|z_+|<1<|z_-|$ . The residue at $z_+$ is $\frac{-2i}{b(z_+-z_-)}=\frac{-2i}{2\sqrt{a^2-b^2}}$ , so the integral is $2\pi i\cdot\frac{-i}{\sqrt{a^2-b^2}}=\frac{2\pi}{\sqrt{a^2-b^2}}$ .

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 $\displaystyle\int_0^{2\pi}\frac{\d\theta}{(a+\cos\theta)^2}=\frac{2\pi a}{(a^2-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)=\int_0^{2\pi}\frac{\d\theta}{a+\cos\theta}=2\pi(a^2-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,\infty)$ ): $-\int_0^{2\pi}\frac{\d\theta}{(a+\cos\theta)^2}=F'(a)=-2\pi a(a^2-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\pi z=\frac{e^{i\pi z}-e^{-i\pi z}}{2i}$ , show that the zeros of $\sin\pi z$ are exactly the integers, each of order 1, and find the residue of $1/\sin\pi z$ at $z=n$ .

Solution

$\sin\pi z=0\iff e^{2\pi iz}=1\iff z\in\Z$ . The derivative $\pi\cos\pi n=\pi(-1)^n\ne0$ , so each zero is simple, and the residue is $\frac1{\pi\cos\pi n}=\frac{(-1)^n}\pi$ (the $p/q'$ rule). The same rule gave the residues of $g_N[f]$ at the roots of unity in 2023 P3(2).

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

Show that $\displaystyle\int_0^{2\pi}\log|1-ae^{i\theta}|\,\d\theta=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 $\mathrm{Re}\,f=\log|1-az|$ . The mean-value property (Ch. 3, Corollary 7.3) at $z_0=0$ , $r=1$ gives $\frac1{2\pi}\int_0^{2\pi}\log|1-ae^{i\theta}|\,\d\theta=\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\pi f(0)$ for every $f$ in 2023 P3.

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\le y)

in terms of the original variable, then differentiate. For

Y=1/X^2

with

X

standard normal,

P(Y\le y)=P(|X|\ge y^{-1/2})

.

Exponential and Poisson.

X\sim\mathrm{Exp}(\lambda)

is memoryless:

X-c

given

X\ge c

is again

\mathrm{Exp}(\lambda)

. The minimum of independent

\mathrm{Exp}(\lambda_1)

,

\mathrm{Exp}(\lambda_2)

is

\mathrm{Exp}(\lambda_1+\lambda_2)

; a sum of

n

i.i.d.

\mathrm{Exp}(\lambda)

is

\mathrm{Gamma}(n,\lambda)

with density

\lambda^nx^{n-1}e^{-\lambda x}/(n-1)!

; and the number of arrivals by time

a

is

\mathrm{Poisson}(\lambda 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 (

\theta=1/\mu

) and show the score is strictly monotone, from

+\infty

to a negative value.

Transforms. The Laplace transform

L(u)=E[e^{-uY}]

, moment generating function

M(\lambda)=E[e^{\lambda Y}]

and characteristic function

\varphi(u)=E[e^{iuY}]

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\in E)-P(T\in E)|\le P(S\ne T)

. Constructing

\xi

and

\eta

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(\mathrm{Bin}(n,p)\le K)-P(\mathrm{Poisson}(np)\le K)|\le np^2

.

Explore

\mathrm{Bin}(n,p)

\mathrm{Poisson}(np)

, probabilities of each

k

. The panel on the right compares the largest gap between their distribution functions with the bound

np^2

.

Trials n Success probability p

Keep μ = np fixed at 3 and grow n

Worked example

2024 P4(4): $X_1,X_2,\dots$ i.i.d. $\mathrm{Exp}(\lambda)$ , and $N$ is the number of partial sums $S_k=X_1+\dots+X_k$ that are $\le a$ . Find the maximum likelihood estimate of $\lambda$ from $N$ , and its mean and variance.

Find the distribution of $N$ .

$N=k$ means $S_k\le a<S_k+X_{k+1}$ . Conditioning on $S_k=s$ (Gamma density) and using independence: $P(N=k)=\int_0^a\frac{\lambda^ks^{k-1}e^{-\lambda s}}{(k-1)!}e^{-\lambda(a-s)}\d s=e^{-\lambda a}\frac{(\lambda a)^k}{k!}$ . So $N\sim\mathrm{Poisson}(\lambda a)$ (and $P(N=0)=e^{-\lambda a}$ directly).
Maximize the likelihood.

$\ell(\lambda)=-\lambda a+N\log\lambda+\text{const}$ , $\ell'(\lambda)=-a+N/\lambda$ . For $N\ge1$ the unique maximizer is $\hat\lambda=N/a$ . For $N=0$ , $\ell$ decreases on $\lambda>0$ and the supremum is approached at $\lambda\to0$ ; the formula $N/a=0$ is the natural boundary value, and worth a sentence in an answer.
Mean and variance.

$E\hat\lambda=E N/a=\lambda$ (unbiased) and $\mathrm{Var}\,\hat\lambda=\lambda a/a^2=\lambda/a$ .

Check your understanding

$X_1,X_2$ i.i.d. $\mathrm{Exp}(\lambda)$ . What is the distribution of $\max(X_1,X_2)-\min(X_1,X_2)$ ?

$\mathrm{Exp}(\lambda)$
$\mathrm{Exp}(2\lambda)$ That is the minimum.
$\mathrm{Gamma}(2,\lambda)$ That is the sum.

Once the first one fires, the other has a fresh

\mathrm{Exp}(\lambda)

lifetime by memorylessness. (2024 P4(2).)

$Y_k=1/X_k^2$ with $X_k$ i.i.d. standard normal. What does $(Y_1+\dots+Y_n)/n^2$ do as $n\to\infty$ ?

It has the same distribution as $Y_1$ for every $n$ .
It tends to 0 by the law of large numbers. $E[Y]=\infty$ , and the scaling is $n^2$ , not $n$ .
It becomes normal after centring.The variance is infinite; the central limit theorem doesn't apply.

\varphi_Y(u)=\exp(-\sqrt{|u|}(1-i\,\mathrm{sgn}\,u))

, so

\varphi_Y(u/n^2)^n=\varphi_Y(u)

. This is the Lévy distribution, stable with index

\tfrac12

: sums are dominated by their largest term.

Le Cam's inequality bounds $|P(\mathrm{Bin}(n,p)\le K)-P(\mathrm{Poisson}(np)\le K)|$ by:

$np^2=\mu^2/n$
$np=\mu$ That is what you get from $P(\xi_j\ne\eta_j)\le p$ . The coupling does better: about $p^2$ per trial.
$1/\sqrt n$ That is the Berry–Esseen rate for the normal approximation.

Each Bernoulli–Poisson pair disagrees with probability

p(1-e^{-p})\le p^2

, and there are

n

pairs. Use the figure: with

\mu

fixed, doubling

n

halves the bound.

Practice

Past problems

Restated in our own words. Official statements: 2020, 2023, 2024, 2025.

2020 Problem 2Lifetimes censored at birth

$X_1,\dots,X_n$ i.i.d. exponential with mean $\mu$ . We observe $Y_i=a$ if $X_i\le a$ and $Y_i=X_i$ otherwise. (1) Find $g(\mu)=E[Y_1]$ . (2) If $\bar Y>a$ , show $g(\hat\mu)=\bar Y$ has a unique solution. (3) With $M=\#\{i:Y_i=a\}$ , find $h$ with $P(M=m,\bar Y\le b)=\int_a^bh(m,y;\mu)\d y$ for $0\le m\le n-1$ , $b>a$ . (4) For $m<n$ , $y>a$ , show $h(m,y;\mu)$ has a unique maximizer in $\mu$ .

Hint

(3) Given which $m$ are censored, the others are $a+E_i$ with $E_i\sim\mathrm{Exp}$ by memorylessness, and $n\bar Y=na+\sum E_i$ . (4) Put $\theta=1/\mu$ .

Solution

(1) $g(\mu)=aP(X\le a)+E[X;X>a]=a(1-e^{-a/\mu})+(a+\mu)e^{-a/\mu}=a+\mu e^{-a/\mu}$ .

(2) $g'(\mu)=e^{-a/\mu}(1+a/\mu)>0$ , $g(\mu)\to a$ as $\mu\to0^+$ and $g\to\infty$ as $\mu\to\infty$ . By continuity and strict monotonicity, each value in $(a,\infty)$ is taken exactly once.

(3) Choose the censored set ( $\binom nm$ ways, probability $(1-e^{-a/\mu})^m$ ). The other $k=n-m\ge1$ exceed $a$ (probability $e^{-ka/\mu}$ ) and, given that, are $a+E_i$ with $E_i$ i.i.d. mean $\mu$ . Then $\bar Y=a+S/n$ with $S\sim\mathrm{Gamma}(k,1/\mu)$ . Changing variables, $h(m,y;\mu)=\binom nm(1-e^{-a/\mu})^me^{-ka/\mu}\cdot\frac{n\,(n(y-a))^{k-1}e^{-n(y-a)/\mu}}{\mu^k(k-1)!}$ for $y>a$ .

(4) With $\theta=1/\mu$ , $\log h=m\log(1-e^{-a\theta})-T\theta+k\log\theta+\text{const}$ , where $T=ka+n(y-a)=ny-ma>0$ . Then $\frac{\d}{\d\theta}\log h=\frac{ma}{e^{a\theta}-1}+\frac k\theta-T$ . The first two terms strictly decrease from $+\infty$ (as $\theta\to0$ ) to 0 (as $\theta\to\infty$ ), so the derivative crosses zero exactly once, from positive to negative: a unique maximizer $\theta$ , hence a unique $\mu$ .

2023 Problem 4The reciprocal of a squared normal

$X$ standard normal, $Y=1/X^2$ with density $f$ . (1) Find $f$ . (2) For $L(u)=\int_0^\infty e^{-uy}f(y)\d y$ , show $L'(u)=-L(u)/\sqrt{2u}$ for $u>0$ . (3) Find $\varphi(u)=E[e^{iuY}]$ . (4) For i.i.d. $Y_k\sim f$ , show $(Y_1+\dots+Y_n)/n^2$ converges in distribution and find the limit density.

Hint

(2) Write $L(u)=2\int_0^\infty\frac1{\sqrt{2\pi}}e^{-x^2/2-u/x^2}\d x$ , differentiate, and substitute $x=\sqrt{2u}/t$ , which swaps $x^2/2$ and $u/x^2$ .

Solution

(1) $P(Y\le y)=2(1-\Phi(y^{-1/2}))$ , so $f(y)=\frac1{\sqrt{2\pi}}y^{-3/2}e^{-1/(2y)}$ for $y>0$ .

(2) Differentiating under the integral (dominated for $u$ in compact subsets of $(0,\infty)$ ), $L'(u)=-2\int_0^\infty\frac1{\sqrt{2\pi}}x^{-2}e^{-x^2/2-u/x^2}\d x$ . With $x=\sqrt{2u}/t$ , $x^{-2}\d x$ becomes $\frac1{\sqrt{2u}}\d t$ (orientation reversed, limits swapped) and the exponent is unchanged, so $L'(u)=-\frac1{\sqrt{2u}}L(u)$ .

(3) Solving with $L(0^+)=1$ : $L(u)=e^{-\sqrt{2u}}$ . $E[e^{-zY}]$ is holomorphic for $\mathrm{Re}\,z>0$ and continuous up to $\mathrm{Re}\,z=0$ ; it agrees with $e^{-\sqrt{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$ : $\varphi(u)=\exp(-\sqrt{-2iu})=\exp\big(-\sqrt{|u|}\,(1-i\,\mathrm{sgn}\,u)\big)$ .

(4) The characteristic function of the scaled sum is $\varphi(u/n^2)^n=\exp\big(-n\sqrt{|u|}/n\,(1-i\,\mathrm{sgn}\,u)\big)=\varphi(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

$X_1,X_2,\dots$ i.i.d. $\mathrm{Exp}(\lambda)$ . (1) Density of $X_1-c$ given $X_1\ge c$ . (2) Densities of $Y=\min(X_1,X_2)$ and $Z-Y$ with $Z=\max$ . (3) Density of $X_1+\dots+X_n$ . (4) The MLE of $\lambda$ from $N$ (defined by $S_N\le a<S_{N+1}$ ), its mean and variance.

Solution

(1) $P(X_1-c>x\mid X_1\ge c)=e^{-\lambda(x+c)}/e^{-\lambda c}=e^{-\lambda x}$ : density $\lambda e^{-\lambda x}$ , $x\ge0$ .

(2) $P(Y>y)=e^{-2\lambda y}$ , so $Y$ has density $2\lambda e^{-2\lambda y}$ . For $Z-Y$ : $P(Z-Y>w)=2\int_0^\infty\lambda e^{-\lambda x}e^{-\lambda(x+w)}\d x=e^{-\lambda w}$ , density $\lambda e^{-\lambda w}$ (and $Y$ , $Z-Y$ are independent).

(3) By induction on convolutions, $\lambda^nx^{n-1}e^{-\lambda x}/(n-1)!$ for $x>0$ .

(4) The worked example: $\hat\lambda=N/a$ , mean $\lambda$ , variance $\lambda/a$ .

2025 Problem 4Poisson approximation by coupling

(1) Show the sum of independent Poisson( $\lambda_1$ ) and Poisson( $\lambda_2$ ) is Poisson( $\lambda_1+\lambda_2$ ). (2) For any $\xi_j,\eta_j$ on one space, show $|P(\sum\xi_j\le K)-P(\sum\eta_j\le K)|\le\sum_jP(\xi_j\ne\eta_j)$ . (3) With $U$ uniform on $(0,1)$ , $\xi=\mathbf 1[U>1-p]$ and $\eta=\min\{\ell:U\le q_\ell\}$ where $q_\ell=e^{-p}\sum_{i\le\ell}p^i/i!$ , show $P(\xi\ne\eta)\le p^2$ . (4) Show $|P(Y\le K)-e^{-\mu}\sum_{i\le K}\mu^i/i!|\le\mu^2/n$ for $Y\sim\mathrm{Bin}(n,p)$ , $\mu=np$ .

Solution

(1) $P(X_1+X_2=k)=\sum_{j=0}^ke^{-\lambda_1}\frac{\lambda_1^j}{j!}e^{-\lambda_2}\frac{\lambda_2^{k-j}}{(k-j)!}=\frac{e^{-(\lambda_1+\lambda_2)}}{k!}\sum_j\binom kj\lambda_1^j\lambda_2^{k-j}=e^{-(\lambda_1+\lambda_2)}\frac{(\lambda_1+\lambda_2)^k}{k!}$ .

(2) Let $E=\{\sum\xi_j\le K\}$ , $F=\{\sum\eta_j\le K\}$ . $|P(E)-P(F)|\le P(E\,\triangle\,F)\le P(\sum\xi_j\ne\sum\eta_j)\le P(\bigcup_j\{\xi_j\ne\eta_j\})\le\sum_jP(\xi_j\ne\eta_j)$ .

(3) $\eta$ is Poisson( $p$ ) (it is the inverse-CDF construction) and $\xi$ is Bernoulli( $p$ ). Since $1-p\le e^{-p}=q_0$ : on $U\le1-p$ both are 0; on $1-p<U\le q_0$ , $\xi=1\ne0=\eta$ ; on $q_0<U\le q_1$ both are 1; on $U>q_1$ , $\eta\ge2\ne\xi$ . So $P(\xi\ne\eta)=(e^{-p}-(1-p))+(1-e^{-p}(1+p))=p(1-e^{-p})\le p\cdot p$ .

(4) Build $n$ independent pairs $(\xi_j,\eta_j)$ from independent uniforms. $\sum\xi_j\sim\mathrm{Bin}(n,p)$ and, by (1), $\sum\eta_j\sim\mathrm{Poisson}(np)$ . By (2) and (3) the difference is at most $np^2=\mu^2/n$ .

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

\lambda>0

, Markov's inequality applied to

e^{\lambda Z}

gives

P(Z\ge\varepsilon)\le M_Z(\lambda)e^{-\lambda\varepsilon}

. Compute

M_Z

for a sum of independent terms as a product, then choose

\lambda

to make the bound small. Exact optimization is not required: any

\lambda

in the allowed range gives a valid bound.

Gaussian facts. If

A

has i.i.d.

N(0,1)

entries and

\lVert b\rVert=1

, then the entries of

Ab

are i.i.d.

N(0,1)

, so

\lVert Ab\rVert^2\sim\chi^2_m

, with

M(\lambda)=(1-2\lambda)^{-m/2}

for

\lambda<\tfrac12

.

Johnson–Lindenstrauss.

k

points in any dimension can be mapped linearly into

m=O(\eta^{-2}\log k)

dimensions with all pairwise squared distances preserved within a factor

1\pm\eta

. 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

\binom k2

pairs.

First-step analysis. For a chain absorbed at 0 or

N

, let

\phi_i

be the probability of absorption at

N

from

i

. Conditioning on the first step:

\phi_i=p_i\phi_{i+1}+q_i\phi_{i-1}+(1-p_i-q_i)\phi_i

, i.e.

p_i(\phi_{i+1}-\phi_i)=q_i(\phi_i-\phi_{i-1})

. If

p_i/q_i=r

is constant this is the gambler's ruin:

\phi_i=\frac{1-r^{-i}}{1-r^{-N}}

(

i/N

when

r=1

). Expected absorption times satisfy the same recursion with a source term:

(p_i+q_i)T_i=1+p_iT_{i+1}+q_iT_{i-1}

.

For more, the High-Dimensional Probability and Markov Chains pages go further in each direction.

Explore: random projection

For 40 random points in

\R^{300}

, the ratio

\lVert b_i'-b_j'\rVert^2/\lVert b_i-b_j\rVert^2

for all 780 pairs, after

b\mapsto\frac1{\sqrt m}Ab

.

1\pm\eta

Target dimension m Tolerance η

Explore: the Moran process

\phi_i

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

i/N

.

Population N Fitness ratio r = f_A/f_B Start with i type-A

Worked example

2026 P2(3): for $\lVert b\rVert=1$ and $0<\varepsilon\le m$ , show $P(\lVert Ab\rVert^2-m\ge\varepsilon)\le e^{-\varepsilon^2/(8m)}$ , given $\log(1+x)\ge x-x^2$ for $x\ge-\tfrac12$ .

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

$Z=\lVert Ab\rVert^2\sim\chi^2_m$ is a sum of $m$ independent $X^2$ terms, so $M_Z(\lambda)=(1-2\lambda)^{-m/2}$ and $P(Z-m\ge\varepsilon)\le(1-2\lambda)^{-m/2}e^{-\lambda(m+\varepsilon)}$ for $0<\lambda<\tfrac12$ .
Use the hint on $(1-2\lambda)^{-m/2}$ . Where does it apply?

With $x=-2\lambda\ge-\tfrac12$ , i.e. $\lambda\le\tfrac14$ : $-\tfrac m2\log(1-2\lambda)\le-\tfrac m2(-2\lambda-4\lambda^2)=m\lambda+2m\lambda^2$ . So the bound is at most $\exp(-\lambda\varepsilon+2m\lambda^2)$ .
Choose $\lambda$ .

The exponent is minimized at $\lambda=\varepsilon/(4m)$ , which is $\le\tfrac14$ because $\varepsilon\le m$ . Its value is $-\frac{\varepsilon^2}{4m}+\frac{\varepsilon^2}{8m}=-\frac{\varepsilon^2}{8m}$ . That is where the condition $\varepsilon\in(0,m]$ comes from.

Check your understanding

In Johnson–Lindenstrauss, how must the target dimension $m$ grow with the number of points $k$ (fixed $\eta$ , $\delta$ )?

Like $\log k$
Like $k$ The union bound over $k^2$ pairs only costs a logarithm, since each pair fails with probability $e^{-\eta^2m/8}$ .
Like the original dimension $n$ $n$ doesn't appear at all.

m\ge\frac8{\eta^2}\log\frac{k(k-1)}{2\delta}

. For the 40 points in the figure with

\eta=0.3

and

\delta=0.1

, the lemma asks for

m\approx800

, 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?

$i/N$
$1/2$ Larger starting groups are more likely to win.
$1-(1-1/N)^i$ That would be right if each A lineage independently had probability $1/N$ ; they aren't independent.

With

r=1

,

X_t

is a martingale, so

E X_\infty=i

, and

X_\infty\in\{0,N\}

gives

N\phi_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/r\approx0.09$
$1/N$ That is the neutral answer; selection helps a lot.
Close to 1Early on there is only one mutant, and it is easily lost by chance.

\phi_1=(1-r^{-1})/(1-r^{-N})\to1-1/r

as

N\to\infty

. Most advantageous mutations are still lost to drift.

Practice

Past problems

Restated in our own words. Official statement: 2026.

2026 Problem 2The Johnson–Lindenstrauss lemma

(1) For $X$ standard normal and $Y=X^2$ , show $M_Y(\lambda)=(1-2\lambda)^{-1/2}$ for $\lambda<\tfrac12$ . (2) Show $P(Z\ge\varepsilon)\le M_Z(\lambda)/e^{\lambda\varepsilon}$ for $\varepsilon,\lambda>0$ . (3) For an $m\times n$ matrix $A$ of i.i.d. standard normals and $\lVert b\rVert=1$ , $\varepsilon\in(0,m]$ , show $P(\lVert Ab\rVert^2-m\ge\varepsilon)\le e^{-\varepsilon^2/(8m)}$ . (4) For $b_1,\dots,b_k\in\R^n$ , $b_i'=Ab_i/\sqrt m$ , and $m\ge\frac8{\eta^2}\log\frac{k(k-1)}{2\delta}$ , show that with probability at least $1-\delta$ , $\lVert b_i'-b_j'\rVert^2\le(1+\eta)\lVert b_i-b_j\rVert^2$ for all $i,j$ .

Solution

(1) $M_Y(\lambda)=\int\frac1{\sqrt{2\pi}}e^{-(1-2\lambda)x^2/2}\d x=(1-2\lambda)^{-1/2}$ , a Gaussian integral with variance $1/(1-2\lambda)$ .

(2) $\mathbf 1[Z\ge\varepsilon]\le e^{\lambda(Z-\varepsilon)}$ pointwise; take expectations.

(3) $(Ab)_i=\sum_jA_{ij}b_j$ are independent $N(0,\lVert b\rVert^2)=N(0,1)$ , so $\lVert Ab\rVert^2$ is a sum of $m$ independent copies of $Y$ . The rest is the worked example.

(4) For a pair with $b_i\ne b_j$ , let $u=(b_i-b_j)/\lVert b_i-b_j\rVert$ . Then $\lVert b_i'-b_j'\rVert^2=\lVert b_i-b_j\rVert^2\lVert Au\rVert^2/m$ , and the bad event is $\lVert Au\rVert^2-m>\eta m$ . With $\varepsilon=\eta m\in(0,m]$ , (3) bounds its probability by $e^{-\eta^2m/8}\le\frac{2\delta}{k(k-1)}$ . Pairs with $b_i=b_j$ , and $i=j$ , never fail. A union bound over the $\binom k2$ unordered pairs gives total failure probability at most $\delta$ .

2026 Problem 4Fixation in the Moran process

A population of $N\ge2$ has $X_t$ individuals of type A (fitness $f_A$ ) and the rest type B ( $f_B$ ), $r=f_A/f_B$ . Each step one individual is chosen uniformly; with $u_t$ uniform on $(0,1)$ , a chosen A becomes B if $u_t>\frac{f_AX_t}{f_AX_t+f_B(N-X_t)}$ , and a chosen B becomes A if $u_t$ is at most that. With $p_i=P(X_1=i+1\mid X_0=i)$ and $q_i=P(X_1=i-1\mid X_0=i)$ : (1) show $p_i/q_i=r$ . (2) Relate $\phi_{i+1},\phi_i,\phi_{i-1}$ , where $\phi_i$ is the probability that $X_t\to N$ . (3) Find $\phi_i$ . (4) Relate $T_{i+1},T_i,T_{i-1}$ , where $T_i$ is the expected absorption time. (5) For $r=1$ , write $T_i$ using $i$ , $N$ , $L_N$ , $L_{i+1}$ , $L_{N-i+1}$ , where $L_j=\sum_{k=1}^{j-1}1/k$ ( $L_1=0$ ) and $\sum_{j=1}^nL_j=nL_{n+1}-n$ .

Hint

(5) With $D_i=T_i-T_{i-1}$ , the recursion is $D_{i+1}-D_i=-N\big(\frac1i+\frac1{N-i}\big)$ . Sum twice, then fix $D_1$ from $T_N=0$ .

Solution

(1) Let $\rho_i=\frac{ri}{ri+N-i}$ . $p_i=\frac{N-i}N\rho_i=\frac{(N-i)ri}{N(ri+N-i)}$ and $q_i=\frac iN(1-\rho_i)=\frac{i(N-i)}{N(ri+N-i)}$ . The ratio is $r$ .

(2) First-step analysis: $\phi_i=p_i\phi_{i+1}+q_i\phi_{i-1}+(1-p_i-q_i)\phi_i$ , i.e. $p_i(\phi_{i+1}-\phi_i)=q_i(\phi_i-\phi_{i-1})$ .

(3) The differences satisfy $d_{i+1}=d_i/r$ , with $\phi_0=0$ , $\phi_N=1$ . So $\phi_i=d_1\sum_{k=0}^{i-1}r^{-k}$ , and normalizing, $\phi_i=\frac{1-r^{-i}}{1-r^{-N}}$ for $r\ne1$ , $\phi_i=i/N$ for $r=1$ .

(4) $T_i=1+p_iT_{i+1}+q_iT_{i-1}+(1-p_i-q_i)T_i$ , i.e. $p_i(T_{i+1}-T_i)-q_i(T_i-T_{i-1})=-1$ , with $T_0=T_N=0$ .

(5) With $r=1$ , $p_i=q_i=i(N-i)/N^2$ , giving the hint's recursion. Summing, $D_j=D_1-N\big(L_j+L_N-L_{N-j+1}\big)$ , and summing again with the given identity, $T_i=iD_1-N\big(iL_{i+1}+(N-i)L_{N-i+1}-(N-i)L_N-1\big)$ . $T_N=0$ forces $D_1=NL_N$ . Therefore

T_i=N\big(NL_N+1-iL_{i+1}-(N-i)L_{N-i+1}\big).

Check $N=2$ : $T_1=2(2+1-1-1)=2$ , matching $T_1=1+\tfrac12T_1$ .

Step-through2020 P5, 2024 P5, 2025 P5, 2026 P5; Kleinberg and Tardos Ch. 3, 6, 7, 11

Algorithms: design and proof

Problem 5 always asks for an algorithm with a running-time bound, and the marks go to the argument as much as the pseudocode. The earlier parts usually hand you the structural lemma the algorithm needs; spot it, then the algorithm is a short loop.

The idea

An answer to an algorithm part should have four pieces, each short: the algorithm (numbered steps or pseudocode), the invariant or lemma it relies on, why it is correct, and its running time with the data structure that achieves it. "Linear time" on a graph means $O(n+m)$ with adjacency lists: each vertex and edge handled a constant number of times.

Peeling (Kleinberg–Tardos §3.6). Many linear-time graph algorithms repeatedly remove a vertex that is forced, maintaining counters and a queue (or bucket array) of candidates. Topological sorting removes sources; the degeneracy ordering removes a minimum-degree vertex. Both are

O(n+m)

because each edge decrements a counter once. The proof that a DAG always has a source, and so a topological order, is K&T (3.19)–(3.20).

Lower bounds on the optimum (K&T §11.1). To prove an approximation ratio, find simple quantities the optimum can't beat. For scheduling:

T^*\ge\frac1m\sum_w\ell_w

(average load) and

T^*\ge\max_w\ell_w

(some machine runs the longest job). Graham's greedy rule comes within

T^*+\max\ell\le2T^*

: these are K&T (11.1)–(11.3), essentially 2024 P5(2) word for word. Sorting the jobs longest first adds a third bound,

T^*\ge2t_{m+1}

(11.4), and improves the ratio to

\tfrac32

(11.5).

Reductions (K&T §§7.1, 7.5, 6.8, 6.10). Assignment with capacities is a flow problem; "max total weight of a walk" is a shortest-path problem after negating weights; "is there an unbounded walk" is negative-cycle detection (Bellman–Ford,

O(n^3)

on a dense graph).

The max-plus view. If every entry of

A

is a monomial

x^{z_{ij}}

with positive coefficient, the entries of

A^\ell

are sums over walks of length

\ell

of

x^{\text{(walk weight)}}

, and no cancellation can happen. So the top degree of

(S_k)_{ij}

is the largest weight of an

i\to j

walk of length at most

k

: matrix powers become longest walks (2025 P5).

Isotonic regression. The best non-decreasing fit

B

to data

A

in squared error is a projection onto a convex cone, so it is unique and characterized by a variational inequality, as in module 2. Its solution is a sequence of blocks, each set to the mean of its data. The pool-adjacent-violators algorithm (PAVA) builds it left to right with a stack: push each point as a block, and while the last two blocks are out of order, merge them. Each element is pushed once and merged at most once:

O(n)

.

Explore

data

A[i]

(drag up and down) blocks on the stack so far a violation about to be merged

Worked example

2026 P5(3): in linear time, find an acyclic orientation of $G$ minimizing the maximum in-degree.

Turn an ordering of the vertices into an acyclic orientation. What is each in-degree?

Given an order $v_{\sigma(1)},\dots,v_{\sigma(n)}$ , orient every edge from the later vertex to the earlier one. Every edge points backwards, so there is no cycle. The in-degree of a vertex is its number of neighbours that come after it.
Which ordering makes the largest such count small?

Repeatedly remove a vertex of minimum degree in the remaining graph, and list vertices in removal order. When $v$ is removed, its remaining degree is exactly its number of later neighbours. So the maximum in-degree is $k=\max_v(\text{degree of }v\text{ at removal})$ , the degeneracy of $G$ .
Why can't any acyclic orientation do better?

At the moment the removed vertex had degree $k$ , the remaining subgraph $H$ had minimum degree $k$ . In any acyclic orientation of $G$ , restricted to $H$ , take the last vertex of $H$ in a topological order: all its $H$ -edges point into it, so its in-degree is at least $k$ .
Make it linear time.

Keep vertices in buckets by current degree (degrees are at most $n-1$ ) and a pointer to the lowest non-empty bucket. Removing a vertex moves each neighbour down one bucket in $O(1)$ , and the pointer only drops by one per removal, so the total is $O(n+m)$ (Matula and Beck).

Check your understanding

Greedy list scheduling (each job to the currently least-loaded machine) has makespan at most $2T^*$ . Which two facts does the proof use?

$T^*\ge\frac1m\sum\ell_w$ and $T^*\ge\max\ell_w$
$T^*\ge\sum\ell_w$ and $T^*\le m\max\ell_w$ The first is false when $m>1$ ; the second is an upper bound, not useful here.
The jobs are sorted by length firstSorting (LPT) improves the ratio to 4/3, but the plain greedy bound needs no sorting.

The last job

w

placed on the busiest machine started when that machine had the minimum load, at most

\frac1m\sum_{w'\ne w}\ell_{w'}

. Adding

\ell_w

gives at most

T^*+T^*

.

Why does the top degree of $(S_k)_{ij}$ equal the largest weight of an $i\to j$ walk of length at most $k$ ?

All coefficients are positive integers (they count walks), so nothing cancels.
Because $z_{ij}\le0$ .The sign of the exponents doesn't matter for this; positivity of the coefficients does.
It doesn't; cancellation can lower the degree.Cancellation needs negative coefficients, and every entry of $A$ has coefficient 1.

(A^\ell)_{ij}=\sum_{\text{walks}}x^{z_{iv_1}+\dots+z_{v_{\ell-1}j}}

. The identity term

A^0

contributes

x^0

on the diagonal, which is why

D_n[i,i]\ge0

.

To maximize $\sum_ic_i\,d_{\vec G}(v_i)$ over acyclic orientations, orient each edge:

into the endpoint with larger $c$ (ties by index)
into the endpoint of larger degreeThe objective counts $c$ at the head of each edge, not degrees.
along a DFS tree, then the rest arbitrarilyThat ignores $c$ entirely.

The objective is

\sum_{\text{edges}}c_{\text{head}}\le\sum_{uv\in E}\max(c_u,c_v)

, and this rule attains it. It is acyclic because every edge goes up in the total order by

(c,\text{index})

. That is 2026 P5(4), in

O(n+m)

.

Practice

Past problems

Restated in our own words. Official statements: 2020, 2024, 2025, 2026. 2023 P5 is in module 9.

2020 Problem 5Isotonic regression

An approximate array of $A$ (length $n$ ) is a non-decreasing $B$ minimizing $\sum(A[i]-B[i])^2$ . Let $A'$ be $A$ with one element appended, and $B,B'$ the approximate arrays of $A,A'$ . (1-1) If $A'[n+1]\ge B[n]$ , show $B'=(B,A'[n+1])$ . (1-2) If $B$ is constant and $A'[n+1]<B[n]$ , show $B'$ is constant with $B'[n+1]<B[n]$ , and find it. (2) Give a polynomial-time algorithm for the approximate array.

Hint

The feasible set is a closed convex cone, so the minimizer is unique and $B$ is optimal if and only if $\sum_i(A[i]-B[i])(D[i]-B[i])\le0$ for every non-decreasing $D$ . For a constant $B\equiv t$ , writing $D$ as $D[1]$ plus non-negative increments shows this is equivalent to: $\sum_i(A[i]-t)=0$ and every tail sum $\sum_{i\ge j}(A[i]-t)\le0$ .

Solution

Uniqueness: the objective is strictly convex and the set of non-decreasing arrays is convex and closed, so each approximate array is unique.

(1-1) $(B,A'[n+1])$ is non-decreasing and costs $\mathrm{cost}_A(B)$ . Any non-decreasing $C$ of length $n+1$ costs at least $\mathrm{cost}_A(C[1..n])\ge\mathrm{cost}_A(B)$ . So the candidate is optimal, hence equal to $B'$ .

(1-2) Let $c$ be the constant value of $B$ ; optimality among constants gives $c=\frac1n\sum A[i]$ , and the hint's tail condition gives $\sum_{i=j}^n(A[i]-c)\le0$ for $j\ge2$ (take $D=c+\delta\mathbf 1_{i\ge j}$ ). Set $t=\frac{nc+A'[n+1]}{n+1}$ , the mean of $A'$ ; clearly $t<c$ . The total sum $\sum(A'[i]-t)=0$ . For $2\le j\le n+1$ , the tail sum is $\sum_{i=j}^n(A[i]-c)+(n+1-j)(c-t)+(A'[n+1]-t)$ , and the last two terms combine to $(c-A'[n+1])\frac{1-j}{n+1}<0$ . So all tail sums are $\le0$ , the constant array $t$ satisfies the optimality condition, and $B'\equiv t=\frac{nB[n]+A'[n+1]}{n+1}<B[n]$ .

(2) PAVA, as in the figure. Maintain a stack of blocks (sum, count). For each $i$ : push $(A[i],1)$ ; while the stack has two blocks with mean(second-to-top) $>$ mean(top), merge them. Output each block's mean over its range. Correctness: keep the invariant that block means increase up the stack and, inside each block with mean $t$ , every tail sum $\sum_{i\ge j}(A[i]-t)$ over the block is $\le0$ . A new single-element block satisfies it. Merging a block of mean $p$ with the next of mean $q<p$ gives mean $t\in(q,p)$ ; tails starting in the second part only gain $(q-t)$ per element, and tails starting in the first part change by $(p-t)(\text{tail length}-|P|)\le0$ , so the invariant survives (this is the computation of (1-2)). At the end, for any non-decreasing $D$ , each block contributes $\sum(A[i]-t)D[i]\le0$ (write $D$ as its first value plus non-negative increments), and $\sum_i(A[i]-B[i])B[i]=0$ ; together, $\sum(A-B)(D-B)\le0$ , so $B$ is optimal. Each element is pushed once and each merge removes a block, so the running time is $O(n)$ .

2024 Problem 5Minimum makespan

Jobs $w_i$ with lengths $\ell_{w_i}\in\mathbb N$ , each allowed only on machines $V_{w_i}\subseteq V$ . Minimize the maximum machine load. (1) If all lengths are equal, give a polynomial-time algorithm. (2) If every $V_w=V$ , show the greedy rule (each job, in order, to a currently least-loaded allowed machine) has $T(\pi_{\mathrm{ALG}})\le2T^*$ .

Solution

(1) With common length $\ell$ , the makespan is $\ell$ times the largest number of jobs on one machine. For a capacity $k$ , build a flow network: source → each job (capacity 1), job → each allowed machine (capacity 1), machine → sink (capacity $k$ ). An assignment with at most $k$ jobs per machine exists if and only if the max flow is $n$ (integrality of max flow). Binary search $k\in\{1,\dots,n\}$ : $O(\log n)$ max-flow computations, each polynomial. Output the assignment from the integral flow at the smallest feasible $k$ .

(2) Let $v$ be a machine with $T(\pi_{\mathrm{ALG}},v)=T(\pi_{\mathrm{ALG}})$ , and $w$ the last job put on $v$ . When $w$ was placed, $v$ had the minimum load $L$ , so $L\le\frac1m\sum_{w'\ne w}\ell_{w'}\le\frac1m\sum\ell\le T^*$ . Then $T(\pi_{\mathrm{ALG}})=L+\ell_w\le T^*+T^*$ , since some machine must run $w$ .

2025 Problem 5Degrees of matrix powers

$A[i,j]=x^{z_{ij}}$ for integers $z_{ij}$ , $S_k=\sum_{\ell=0}^kA^\ell$ , and $D_k[i,j]$ is the top degree of $S_k[i,j]$ . (1) For $z_{ij}\le0$ , reduce computing $D_n$ to shortest paths in polynomial time. (2) Show: every entry of $D_k$ converges as $k\to\infty$ if and only if $D_n[i,i]\le0$ for all $i$ . (3) Decide convergence in polynomial time. (4) With $z_{ij}=s_{ij}+t_{ij}\lambda$ , decide in polynomial time whether $\Lambda=\{\lambda\in\Z:\text{every entry of }D_k\text{ converges}\}$ is empty.

Hint

Read $D_k[i,j]$ as the largest weight of a walk of length at most $k$ (length-0 walk at $i=j$ included). For (4), the condition at $\lambda$ is "no cycle $C$ with $s(C)+\lambda t(C)>0$ ", and a positive cycle found at $\lambda$ tells you which direction to move.

Solution

(1) By the max-plus view, $D_n[i,j]=\max$ weight of an $i\to j$ walk of length $\le n$ . Make the complete digraph with edge weights $c_{ij}=-z_{ij}\ge0$ . With non-negative weights, a shortest walk can be taken to be a simple path (length $\le n-1$ ), so $D_n[i,j]=-\mathrm{dist}_c(i,j)$ (with $\mathrm{dist}(i,i)=0$ ). That is $n^2$ shortest-path queries (or $n$ runs of Dijkstra).

(2) $D_k$ is non-decreasing in $k$ and integer-valued, so each entry converges if and only if it is bounded. If some closed walk has positive weight, repeating it makes $D_k[i,i]\to\infty$ . If none does, every walk decomposes into a simple path plus closed walks of weight $\le0$ , so walk weights are bounded by the best simple path. A positive closed walk exists if and only if a positive simple cycle exists (decompose), and simple cycles have length $\le n$ , so if and only if some $D_n[i,i]>0$ . Since $D_n[i,i]\ge0$ always, convergence $\iff D_n[i,i]\le0$ for all $i$ .

(3) Run Bellman–Ford (or Floyd–Warshall) with weights $-z_{ij}$ and report whether a negative cycle exists: $O(n^3)$ .

(4) Every cycle gives a linear constraint $s(C)+\lambda t(C)\le0$ , so $\Lambda$ is the set of integers in an interval (possibly empty or unbounded). Each breakpoint $-s(C)/t(C)$ has absolute value at most $M=n\max|s_{ij}|$ , so if $\Lambda\ne\emptyset$ it meets $[-M-1,M+1]$ . Binary search on that range: at the midpoint $\lambda$ , run (3). If there is no positive cycle, $\Lambda\ne\emptyset$ . Otherwise Bellman–Ford returns a positive cycle $C$ : if $t(C)=0$ , $s(C)>0$ and $\Lambda=\emptyset$ ; if $t(C)>0$ , every $\lambda'\ge\lambda$ also fails, so search left; if $t(C)<0$ , search right. This takes $O(\log M)$ rounds of $O(n^3)$ , polynomial in the input size.

2026 Problem 5Acyclic orientations

$G=(V,E)$ is simple with $n$ vertices and $m$ edges, in adjacency lists. (1) Show distinct acyclic orientations have distinct in-degree sequences. (2) In linear time, decide whether some acyclic orientation has in-degree sequence $(h_1,\dots,h_n)$ . (3) In linear time, find an acyclic orientation minimizing the maximum in-degree. (4) In linear time, find one maximizing $\sum_ic_id(v_i)$ .

Solution

(1) Induction on $n$ . An acyclic orientation has a source $s$ (in-degree 0). If two acyclic orientations share in-degrees, $s$ has in-degree 0 in both, so all its edges point out of $s$ in both. Delete $s$ : both orientations of $G-s$ are acyclic and have equal in-degree sequences (each neighbour of $s$ lost exactly one incoming edge in both). By induction they agree, so the originals agree.

(2) Keep a counter $h(v)$ (required in-degree from vertices not yet removed) and a queue of vertices with $h=0$ . Repeatedly pop $v$ , orient all its remaining edges out of $v$ , decrement $h$ of each remaining neighbour, failing if any goes negative and enqueuing any that reach 0. Answer yes if and only if all $n$ vertices are removed. Each edge is processed once: $O(n+m)$ . Correctness: if a valid orientation exists, any remaining vertex with $h=0$ has no incoming edges from remaining vertices, so it is a source there, and removing it keeps the remaining requirements valid; the queue empties early only if no remaining vertex is a source, impossible for an acyclic orientation. If the algorithm succeeds, the orientation it built is acyclic (edges point from earlier-removed to later) with the right in-degrees.

(3) The worked example: the degeneracy ordering, $O(n+m)$ .

(4) Orient each edge $uv$ towards the endpoint larger in the order $(c,\text{index})$ . Acyclic, attains the upper bound $\sum_{uv}\max(c_u,c_v)$ , and $O(n+m)$ .

From Kleinberg and Tardos, Algorithm Design (Pearson, 2006)

Exercise numbers are chapter and exercise (3.3 is Exercise 3 of Chapter 3). Each is restated in our own words; the hints and solutions are written for this page.

Exercise 3.3A topological order, or a cycle as proof that there is none

Extend the source-removal algorithm of §3.6 so that on any directed graph it outputs either a topological ordering or a directed cycle, in $O(m+n)$ time.

Hint

If the algorithm gets stuck, every remaining node has an incoming edge from another remaining node. Follow those edges backwards.

Solution

Keep in-degree counters and a queue of nodes with count 0; repeatedly remove one, output it, and decrement its out-neighbours. If all $n$ nodes are output, that is a topological order. If the queue empties early, every remaining node $v$ has an edge $(u,v)$ with $u$ remaining. Start anywhere among them and repeatedly step to such a predecessor, marking nodes; within $n$ steps a node repeats, and the nodes between its two visits, reversed, form a directed cycle. Everything is a constant amount of work per node and edge: $O(m+n)$ . This is the certificate pattern that 2026 P5(2) uses: the peeling algorithm either succeeds or shows exactly why no answer exists.

Exercise 6.13Arbitrage: a cycle whose product exceeds 1

For $n$ assets, one unit of $i$ trades for $r_{ij}$ units of $j$ . An opportunity cycle is a cycle of trades along which the product of the ratios exceeds 1. Give a polynomial-time algorithm that finds one if it exists.

Hint

Logarithms turn products into sums.

Solution

Give edge $(i,j)$ the cost $c_{ij}=-\log r_{ij}$ . A cycle has $\prod r_{ij}>1$ exactly when $\sum c_{ij}<0$ , so opportunity cycles are negative cycles. Add a source joined to every node at cost 0 and run Bellman–Ford for $n$ rounds (§6.10): if some distance still improves in round $n$ , a negative cycle exists, and following predecessor pointers from an improved node recovers it. Time $O(n^3)$ on the complete graph. Compare 2025 P5: there the weights are exponents $z_{ij}$ , the question is whether a cycle has positive total weight, and the same detection with costs $-z_{ij}$ answers it.

Exercise 11.5Why greedy is much better than 2 in practice

Ten machines run Greedy-Balance (§11.1). Every job has length $1\le t_i\le50$ , and the total load $\sum t_i$ is always at least 3,000. Prove that the makespan is never more than 20% above the average load $\frac1{10}\sum t_i$ .

Hint

The proof of (11.3) actually shows $T\le\frac1m\sum t_i+\max t_i$ , which is sharper than $2T^*$ .

Solution

Let $A=\frac1{10}\sum t_i\ge300$ . Take the busiest machine and the last job $j$ put on it. When $j$ arrived that machine had the least load, at most $A$ , so $T\le A+t_j\le A+50\le A+\frac A6=\frac76A<1.2A$ . The factor 2 is only approached when one job is comparable to the whole average load; with many small jobs, greedy is nearly optimal. Bounds in terms of the instance, not just worst-case ratios, are what you need when an exam part asks you to explain observed behaviour.

Calculator2020 P3, 2023 P5

Algebra and number representations

Algebra appears less often, but when it does the problems reward the same habit: find a normal form. Every polynomial reduces to one in which $x_i$ and $y_i$ never meet; every integer has exactly one signed binary expansion with no two adjacent nonzero digits.

The idea

Ideals and homomorphisms. For a ring homomorphism

\varphi:R\to L

, the preimage of an ideal is an ideal,

\ker\varphi

is an ideal, and if

\varphi

is onto,

L\cong R/\ker\varphi

(first isomorphism theorem).

Normal forms prove kernels. To show $\ker\varphi=I$ for an explicit ideal $I=(g_1,\dots,g_n)$ : first $I\subseteq\ker\varphi$ (check the generators). For the other inclusion, show every $p$ can be written $p=\sum h_ig_i+r$ with $r$ in a set of "reduced" polynomials on which $\varphi$ is injective. This is the idea behind Gröbner bases: $\{x_iy_i-1\}$ is one, and its normal forms are the polynomials in which no monomial contains both $x_i$ and $y_i$ .

Signed binary. A ternary (signed-digit) representation of

d

is

d=\sum_{i=0}^nd_i2^i

with

d_i\in\{-1,0,1\}

and

d_n=1

. It is sparse, the non-adjacent form (NAF), if

d_{i-1}d_i=0

for all

i

.

The NAF rule. If

d

is even, the last digit is 0. If

d

is odd, it is

+1

when

d\equiv1\pmod4

and

-1

when

d\equiv3\pmod4

, which makes

(d-d_0)/2

even, so the next digit is 0. Repeating this on

(d-d_0)/2

builds the NAF; there is no choice at any step, which proves uniqueness. It has the fewest nonzero digits of any signed representation, and about one third of its digits are nonzero on average, against one half for binary.

Why it matters. In elliptic-curve cryptography, computing $dP$ by double-and-add costs one addition per nonzero digit; negating a point is free, so the NAF cuts the additions from about $n/2$ to $n/3$ . The department's cryptography group works on exactly this kind of efficiency question, alongside post-quantum schemes.

Explore

Number d (1 to 2⁴⁰)

Average over all d ≤ Lₙ, n =

Worked example

Find the NAF of $d=59$ (binary $111011$ , five nonzero digits).

$59\equiv3\pmod4$ . What are $d_0$ and the next number?

$d_0=-1$ and $(59+1)/2=30$ .
Continue: $30$ , then what?

$30$ is even: $d_1=0$ , next $15$ . $15\equiv3\pmod4$ : $d_2=-1$ , next $8$ . Then $8,4,2$ give $d_3=d_4=d_5=0$ , and $1$ gives $d_6=1$ .
Write the result and check it.

$(d_0,\dots,d_6)=(-1,0,-1,0,0,0,1)$ : $64-4-1=59$ . Three nonzero digits instead of five, and no two adjacent.

Check your understanding

What is the NAF of 7?

$1,1,1$ (that is, $4+2+1$ )Adjacent nonzero digits aren't allowed.
$8-1$ : digits $(-1,0,0,1)$
$8-2+1$ Correct value, but $-2+1$ puts nonzero digits side by side.

7\equiv3\pmod4

gives

d_0=-1

, then

4\to2\to1

. Runs of ones become one

+1

and one

-1

.

In 2020 P3, why is $\varphi$ (substituting $y_i=x_i^{-1}$ ) injective on polynomials where no monomial contains both $x_i$ and $y_i$ ?

Distinct such monomials map to distinct Laurent monomials.
Because $\varphi$ is a ring homomorphism.It isn't injective on all of $R$ : $x_1y_1-1\mapsto0$ .
Because $K$ is a field.The field matters for linear independence of monomials, but the key is the exponent bookkeeping.

\prod x_i^{a_i}y_i^{b_i}\mapsto\prod x_i^{a_i-b_i}

, and when

a_ib_i=0

the exponent

a_i-b_i

determines both

a_i

and

b_i

. Since distinct Laurent monomials are linearly independent over

K

,

\varphi(r)=0

forces

r=0

.

The largest number with an $(n+1)$ -digit NAF, $L_n$ , equals:

$\lfloor2^{n+2}/3\rfloor$
$2^{n+1}-1$ That is the largest with $n+1$ binary digits; it needs a NAF digit at position $n+1$ .
$2^n$ Too small: $2^n+2^{n-2}+\dots$ is allowed.

Take

d_n=1

and alternate

0,1,0,1,\dots

downwards:

2^n+2^{n-2}+\dots

. For

n

even this is

(2^{n+2}-1)/3

; for

n

odd,

(2^{n+2}-2)/3

.

Practice

Past problems

Restated in our own words. Official statements: 2020, 2023.

2020 Problem 3Laurent polynomials as a quotient ring

$L=K[x_1^{\pm1},\dots,x_n^{\pm1}]$ , $R=K[x_1,\dots,x_n,y_1,\dots,y_n]$ , and $\varphi:R\to L$ substitutes $y_i=x_i^{-1}$ . (1) Show $\varphi^{-1}(J)$ is an ideal for every ideal $J$ of $L$ . (2) With $g_i=x_iy_i-1$ and $R'$ the polynomials in which no monomial contains both $x_i$ and $y_i$ (for every $i$ ), show every $p\in R$ is $\sum h_ig_i+r$ with $r\in R'$ . (3) For $I=(g_1,\dots,g_n)$ , show $\ker\varphi=I$ and $L\cong R/I$ .

Solution

(1) If $a,b\in\varphi^{-1}(J)$ and $s\in R$ : $\varphi(a-b)=\varphi(a)-\varphi(b)\in J$ and $\varphi(sa)=\varphi(s)\varphi(a)\in J$ . Also $0\in\varphi^{-1}(J)$ .

(2) For a monomial $u\,x_i^ay_i^b$ with $a,b\ge1$ : $x_i^ay_i^b=x_i^{a-1}y_i^{b-1}(g_i+1)$ , so $u\,x_i^ay_i^b\equiv u\,x_i^{a-1}y_i^{b-1}$ modulo a multiple of $g_i$ . Each replacement lowers $\sum_i\min(a_i,b_i)$ for that monomial, so after finitely many steps (induction on this quantity, summed over monomials) every monomial is in $R'$ , and the multiples of $g_i$ collected along the way give the $h_i$ .

(3) $\varphi(g_i)=x_ix_i^{-1}-1=0$ , so $I\subseteq\ker\varphi$ . Conversely let $\varphi(p)=0$ and write $p=\sum h_ig_i+r$ by (2). Then $\varphi(r)=0$ . As in the quiz above, $\varphi$ maps distinct monomials of $R'$ to distinct Laurent monomials, which are linearly independent over $K$ , so $r=0$ and $p\in I$ . $\varphi$ is onto, since $x_i^{-1}=\varphi(y_i)$ and $\varphi$ is a homomorphism, so $L\cong R/I$ by the first isomorphism theorem.

2023 Problem 5The non-adjacent form

(1) Find the largest $L_n$ with a sparse ternary representation $(d_0,\dots,d_n)$ . (2) Show the sparse representation of each $d$ is unique. (3) Give an $O(\log d)$ algorithm from binary to sparse ternary. (4) Show the sparse representation has the fewest nonzero digits among all ternary representations of $d$ . (5) For $X_n$ uniform on $\{1,\dots,L_n\}$ and $Y_n$ the number of nonzero digits of its sparse representation, show $E[Y_n]/n\to\tfrac13$ .

Hint

(4) Let $W(d)$ be the minimum weight over all signed representations. Show $W(x)\le W(y)+1$ when $|x-y|=1$ , and that when $d$ is odd, $W(d)=1+\min(W(\frac{d-1}2),W(\frac{d+1}2))$ is attained by the even neighbour. (5) Count digit strings built from blocks "0" and " $\pm1$ then 0".

Solution

(1) Greedy from the top: $d_n=1$ , $d_{n-1}=0$ , $d_{n-2}=1,\dots$ This is the maximum: sparsity forces $d_{n-1}=0$ , so $d\le2^n+L_{n-2}$ (with $L_{-1}=0$ , $L_0=1$ ), and induction gives $L_n=2^n+2^{n-2}+\cdots$ . $L_n=\lfloor2^{n+2}/3\rfloor$ .

(2) Induction on $d$ . $d_0\equiv d\pmod2$ . If $d$ is even, $d_0=0$ . If $d$ is odd, $d_0=\pm1$ and sparsity forces $d_1=0$ , so $d\equiv d_0\pmod4$ , fixing $d_0$ . Then $(d_1,\dots,d_n)$ is a sparse representation of $(d-d_0)/2$ , which is a smaller positive integer for $d\ge2$ (and $d=1$ has only $(1)$ ). By induction it is unique.

(3) Scan the bits $b_0,b_1,\dots$ of $d$ with a carry $c\in\{0,1\}$ . At position $i$ let $t=b_i+c$ . If $t=0$ : digit 0, carry 0. If $t=2$ : digit 0, carry 1. If $t=1$ : digit $+1$ , carry 0 when $b_{i+1}=0$ ; digit $-1$ , carry 1 when $b_{i+1}=1$ . Continue past the top bit until the carry is 0. This is the mod-4 rule applied to the running value, with $O(1)$ work per bit, so $O(\log d)$ in total.

(4) A signed representation can be seen as a multiset of terms $\pm2^i$ ; combining equal or opposite terms never increases the count, so $W$ is the same whether or not repeated positions are allowed. Adding one term $\pm1$ shows $W(x)\le W(y)+1$ for $|x-y|=1$ . For even $d$ , any representation has $d_0=0$ , so $W(d)=W(d/2)$ . For odd $d$ , $W(d)=1+\min(W(a),W(b))$ where $a,b=(d\mp1)/2$ ; one, say $a$ , is even. Then $b$ is odd and $W(b)=1+\min(W(\frac{b-1}2),W(\frac{b+1}2))$ ; one of these arguments is $a/2$ and the other is $a/2\pm1$ , so by the lemma $W(b)\ge1+(W(a/2)-1)=W(a)$ . Hence the minimum is always attained at the even neighbour, which is exactly the NAF's choice, and by induction the NAF has weight $W(d)$ .

(5) The numbers $1,\dots,L_n$ are exactly those whose NAF has at most $n+1$ digits. Reading from the bottom, a NAF of length at most $n+1$ (allowing leading zeros, with the top nonzero digit $+1$ ) is a sequence of blocks "0" (length 1) and " $\pm1$ 0" (length 2, two choices). The number of block sequences of length $\ell$ satisfies $a_\ell=a_{\ell-1}+2a_{\ell-2}$ , growing like $2^\ell$ . In a long uniformly random such sequence, each block is "0" with probability $1\cdot2^{-1}=\tfrac12$ and " $\pm1$ 0" with probability $2\cdot2^{-2}=\tfrac12$ , independently in the limit, so a block has mean length $\tfrac32$ and carries $\tfrac12$ nonzero digit on average: a density of $\tfrac13$ . Making this precise with the generating function $\sum_\ell a_\ell(u)z^\ell=1/(1-z-2uz^2)$ ( $u$ marks nonzero digits) and differentiating in $u$ at $u=1$ gives $E[Y_n]=\tfrac n3+O(1)$ ; the sign constraint on the top digit and the boundary change only the $O(1)$ term.

Play it yourself2026 doctoral papers (summer and winter)

The doctoral keyword essay

The doctoral written exam is different in kind: ninety minutes, a list of keywords, and you explain three of them. It rewards the ability to state things precisely and connect them, which is also what the oral exam probes.

The idea

Format (2026 papers, 2027 guide). Online, 90 minutes. Choose three keywords from a list (ten in summer 2026, six in winter 2026). For each, describe its mathematical-informatics side: definition, relevant theorems, examples and applications, in at most three pages, each keyword on separate pages. Answer in Japanese or English. Applicants finishing a UTokyo master's may be exempted; the application also requires a research report of up to ten pages, an English summary and a two-page Q&A on aims, methods, state of the field, novelty and contribution.

The department says the doctoral paper tests whether you can describe and explain advanced topics across the fields of mathematical informatics. In practice that means 30 minutes per keyword, and a fixed shape for every answer:

Definition, with symbols
One precise definition, with every symbol introduced. If there are two standard formulations (primal/dual, discrete/continuous), give the one you will use and mention the other.
One theorem, stated exactly
Hypotheses and conclusion, with a proof or proof idea in a few lines. A precise statement of one theorem beats vague mentions of five.
A small example, worked
Numbers, a picture, or a two-variable case that the reader can check. This is where understanding shows.
Algorithms and complexity
How you compute it, and how fast. Most keywords on these lists are methods, so this is often half the answer.
Applications and connections
Two concrete applications and one link to another keyword on the list (LP duality ↔ interior point methods ↔ minimum-cost flow; diffusion models ↔ Lévy processes and MCMC; optimal control ↔ reinforcement learning ↔ state space models).

Drill

Draw from

1:30:00

Tick each part of the outline as you write it. In the real exam you choose your three from the whole list, so spend the first few minutes choosing the ones where you can state a theorem exactly.

Worked example

Outline an answer for "linear programming duality" in the five-part shape.

Definition.

Primal $\max\{c^\top x:Ax\le b,\ x\ge0\}$ , dual $\min\{b^\top y:A^\top y\ge c,\ y\ge0\}$ . The dual arises by bounding the primal objective with non-negative combinations of the constraints: if $A^\top y\ge c$ , $y\ge0$ , then $c^\top x\le y^\top Ax\le y^\top b$ .
Theorems.

Weak duality (the line above). Strong duality: if either problem has a finite optimum, both do and the optima are equal; proof via Farkas' lemma (a separating hyperplane argument), or as a by-product of the simplex method. Complementary slackness: feasible $x,y$ are both optimal if and only if $y_i(b-Ax)_i=0$ and $x_j(A^\top y-c)_j=0$ for all $i,j$ .
Example.

$\max\,x_1+x_2$ s.t. $x_1+2x_2\le4$ , $3x_1+x_2\le6$ , $x\ge0$ . Optimum $x=(1.6,1.2)$ , value $2.8$ . Dual $\min\,4y_1+6y_2$ s.t. $y_1+3y_2\ge1$ , $2y_1+y_2\ge1$ , $y\ge0$ : $y=(0.4,0.2)$ , value $2.8$ . Both primal constraints are tight and both $y_i>0$ , as complementary slackness requires. Read $y_i$ as the marginal value of resource $i$ (shadow prices).
Algorithms.

The simplex method maintains primal feasibility and finishes when the implied dual is feasible. Interior point methods follow the central path $x_js_j=\mu$ (with $s=A^\top y-c$ ) as $\mu\to0$ , shrinking the duality gap $c^\top x$ -vs- $b^\top y$ , in polynomial time. Duality gaps are the standard stopping certificate.
Applications and connections.

Max-flow min-cut and König's theorem are LP duality for totally unimodular matrices. Minimum-cost flow optimality is complementary slackness with node potentials. In game theory, von Neumann's minimax theorem is LP duality; in machine learning, the SVM dual leads to kernels. Lagrangian duality and KKT conditions generalize it to convex programs.

Check your understanding

When does strong duality hold for a linear program?

Whenever the primal (or the dual) has a finite optimum.
Only under Slater's condition.Slater's condition is needed for general convex programs, not for LPs.
Only when the optimal solution is unique.Uniqueness is irrelevant.

For LPs, feasibility and boundedness suffice. If the primal is unbounded the dual is infeasible, and both can be infeasible at once.

Why does the Metropolis–Hastings chain have the target $\pi$ as its stationary distribution?

Its acceptance probability makes the chain satisfy detailed balance with respect to $\pi$ .
Because the proposal distribution equals $\pi$ .The proposal can be almost anything; that is the point.
Because it is irreducible.Irreducibility gives uniqueness and convergence, not which distribution is stationary.

\pi(x)q(x,y)\alpha(x,y)=\min(\pi(x)q(x,y),\pi(y)q(y,x))

is symmetric in

x,y

, so

\pi

is reversible and stationary. Add irreducibility and aperiodicity for convergence, and only ratios

\pi(y)/\pi(x)

are needed, so the normalizing constant can be unknown.

A positive largest Lyapunov exponent for a dynamical system indicates:

sensitive dependence on initial conditions: nearby orbits separate exponentially
an asymptotically stable fixed pointThat has all exponents negative.
that a Lyapunov function existsDifferent Lyapunov idea: Lyapunov functions certify stability.

\lambda=\lim\frac1t\log\lVert D\Phi_t(x)v\rVert

. For the logistic map at

r=4

,

\lambda=\log2

. Keep the two Lyapunov notions apart in an essay; the contrast is worth a sentence.

Practice

Model outlines

Write your own first, then compare. Each is the skeleton of a three-page answer, not the answer.

Markov chain Monte Carlo2026 summer

Outline

Definition: sample from $\pi$ (known up to a constant) by running a Markov chain with stationary distribution $\pi$ ; estimate $E_\pi f$ by ergodic averages.
Theorems: detailed balance ⇒ stationarity; ergodic theorem for irreducible aperiodic chains; convergence in total variation at a rate set by the spectral gap; a CLT for ergodic averages with asymptotic variance involving the autocorrelation.
Example: random-walk Metropolis on a 1D bimodal density; show slow mixing between modes, cured by tempering.
Algorithms: Metropolis–Hastings, Gibbs sampling, Hamiltonian Monte Carlo, Langevin (link to diffusion models). Diagnostics: effective sample size, $\hat R$ .
Applications: Bayesian posteriors, the Ising model, counting via rapidly mixing chains.

Proximal gradient descent2026 winter

Outline

Definition: for $F=f+g$ , $f$ $L$ -smooth convex, $g$ closed convex, $x_{k+1}=\mathrm{prox}_{g/L}(x_k-\nabla f(x_k)/L)$ .
Theorems: prox is firmly non-expansive; $F(x_k)-F^*\le L\lVert x_0-x^*\rVert^2/(2k)$ ; FISTA accelerates to $O(1/k^2)$ (energy argument as in 2024 P2); linear rate under strong convexity.
Example: lasso, where the prox is soft-thresholding (ISTA). Work one step by hand.
Connections: projected gradient ( $g$ an indicator), the PSD projection of 2026 P1, ADMM, mirror descent.
Applications: sparse regression, compressed sensing, matrix completion with the nuclear norm (prox = singular value thresholding).

Minimum-cost flow problem2026 winter

Outline

Definition: directed graph, capacities $u$ , costs $c$ , supplies $b$ ; minimize $\sum c_ex_e$ over flows with $0\le x\le u$ and conservation.
Theorems: optimal iff the residual graph has no negative-cost cycle; equivalently, there are node potentials $p$ with reduced costs $c_e+p_u-p_v\ge0$ on residual arcs (LP duality); integrality for integer data (total unimodularity).
Example: a four-node network; cancel one negative cycle by hand.
Algorithms: cycle cancelling, successive shortest paths with potentials (Dijkstra), cost scaling; strongly polynomial algorithms exist (Tardos, Orlin).
Applications: transportation and assignment, optimal transport, image segmentation via cuts; special cases are shortest path and max flow.

Diffie–Hellman key exchange2026 summer

Outline

Definition: in a cyclic group $G=\langle g\rangle$ of order $q$ , Alice sends $g^a$ , Bob sends $g^b$ , both compute $g^{ab}$ .
Theorems: security rests on the computational/decisional Diffie–Hellman assumptions, implied to be no harder than discrete log; generic-group lower bound $\Omega(\sqrt q)$ ; Pohlig–Hellman shows why $q$ needs a large prime factor.
Example: $p=23$ , $g=5$ , $a=6$ , $b=15$ : shared key $2$ .
Algorithms: fast exponentiation (signed digits, see module 9), elliptic-curve groups for shorter keys; attacks by baby-step giant-step, Pollard rho, index calculus in $\mathbb F_p^*$ .
Applications and connections: TLS key exchange; man-in-the-middle needs authentication; Shor's algorithm breaks it, motivating post-quantum cryptography (another keyword on the list).

State space model2026 winter

Outline

Definition: hidden state $x_t=Fx_{t-1}+w_t$ , observation $y_t=Hx_t+v_t$ (linear Gaussian), or general $p(x_t\mid x_{t-1})$ , $p(y_t\mid x_t)$ .
Theorems: the Kalman filter computes $p(x_t\mid y_{1:t})$ exactly in the linear Gaussian case; observability and controllability; the Riccati recursion and its steady state.
Example: tracking position and velocity from noisy positions; write one predict–update step.
Algorithms: Kalman filter and RTS smoother, EM for parameters, extended/unscented Kalman filters, particle filters (sequential Monte Carlo).
Connections: optimal control (LQG duality with LQR), hidden Markov models, recent deep state space models for sequences.

The UTokyo Mathematical Informatics Exam

The idea

Explore

Mock exam

A twelve-week plan

Weeks 1–2: symmetric matrices

Weeks 3–4: probability and statistics

Weeks 5–6: algorithms

Week 7: differential equations

Week 8: analysis

Week 9: optimization, and algebra

Weeks 10–12: full mock exams

Words worth knowing in Japanese

Check your understanding

Reading

The idea

Explore

Worked example

Check your understanding

Practice

Past problems

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

The idea

Explore: an epidemic in the phase plane

Explore: phase separation

Worked example

Check your understanding

Practice

Past problems

From Strogatz, Nonlinear Dynamics and Chaos (2nd ed., CRC Press)

The idea

Explore

Worked example

Check your understanding

Practice

Past problem

From Boyd and Vandenberghe, Convex Optimization (Cambridge, 2004)

The idea

Explore

Worked example

Check your understanding

Practice

Past problems

From Stein and Shakarchi, Complex Analysis (Princeton Lectures in Analysis II, 2003)

The idea

Explore

Worked example

Check your understanding

Practice

Past problems

The idea

Explore: random projection

Explore: the Moran process

Worked example

Check your understanding

Practice

Past problems

The idea

Explore

Worked example

Check your understanding

Practice

Past problems

From Kleinberg and Tardos, Algorithm Design (Pearson, 2006)

The idea

Explore

Worked example

Check your understanding

Practice

Past problems

The idea

Definition, with symbols

One theorem, stated exactly

A small example, worked

Algorithms and complexity

Applications and connections

Drill

Worked example

Check your understanding

Practice