Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 33 1 Solution Created 2026-10-03 Updated 2026-10-06
For the normal linear model, the log-likelihood isThe full column rank of the design matrix makes invertible. Differentiating in gives the normal equations . With the minimized residual sum of squares substituted, differentiation in givesThese are the maximum-likelihood estimators almost surely; almost surely when and . The linear transformation of the multivariate normal distribution yieldsDefine the hat matrix . The fitted values are , the regression residuals are , and . The orthogonal projection has rank and annihilates . By Cochran's theorem,Consequently , with bias . The unbiased estimator isIts square root, the reported residual standard error, estimates ; the assertion of unbiasedness applies to the variance, not generally to its square root.
For the paper-strength analysis, let be the measured percentage and . Both normal linear models use independent errors of common variance . Their mean functions are for
lm1, and for lm2, with separately fitted coefficients. The reported residual standard errors are and , respectively.For
lm1, the estimated conditional expectation at a new percentage isThe original data mean must be used for centering the new percentage; its numerical value is not supplied in the excerpt. Because , the two columns of this design matrix are orthogonal, and . Hence the coefficient standard errors in the output giveThis estimates uncertainty in the mean. Predicting an individual future batch would additionally require the new-error variance, estimated by .To compare the nested normal linear models, test against within the quadratic model. The Student t-test statistic isIts two-sided p-value is . Equivalently is a partial F-test statistic with null distribution . Reject the linear restriction and prefer
lm2 at the 5% level. Its residual spread is much smaller; the increase in the coefficient of determination from to supports the same conclusion, although the test is the relevant complexity-adjusted comparison.For regression diagnostics, inspect regression residuals against fitted means and hardwood percentage for omitted curvature, a scale-location plot for nonconstant variance, and a quantile-quantile plot against the normal distribution for departures from the error assumption. Check unusual observations using regression leverage and Cook's distance, and examine residuals in collection or batch order if dependence is plausible. Independence and a common variance require substantive justification as well as these plots; a small p-value for a polynomial term does not itself check the error model.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 33 4 b Solution 2026-10-06
The chosen Poisson regression has fitted meanFor zero building cover, its fitted expected number of floods over the 25-year observation window is . Increasing the covered proportion by multiplies the fitted expected count by . Thus a ten-percentage-point increase, , multiplies the expected count by about , an increase of . A one-percentage-point increase multiplies it by about . The full-unit multiplier compares proportions differing by one, not percentages differing by one.
These are associations in the conditional expectation with the recorded final-year building cover. The regression coefficient is not automatically a causal effect of changing development, especially since the count covers 25 years while cover was measured at the end.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 37 6 c Solution Created 2026-10-03 Updated 2026-10-06
Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let be the resulting number of clause occurrences.
Assign independent fair truth values. A singleton clause is satisfied with probability , a proper two-variable clause with probability , and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least , hence at least .
To derandomize, use the method of conditional probabilities. After some variables have been fixed, let be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations satisfy . Fix the value with the larger expectation. This never decreases . When all variables have been fixed, is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio .
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 37 6 d Solution Created 2026-10-03 Updated 2026-10-06
Apply the condition after the usual clause normalization, so each variable has at most one singleton clause. For a variable with such a clause, make its favored literal true with probability ; for other variables use a fair value. Make these choices independently. Then every singleton is satisfied with probability .
Each literal of a proper two-variable clause is true with probability at least . Independence bounds the probability that both are false by , so the clause is satisfied with probability at least . Tautologies have probability one. Thus the expected fraction satisfied is at least . One term increases and the other decreases, so their intersection maximizes this bound:The method of conditional probabilities also works with these biased probabilities: before fixing a variable, the current expectation is the weighted average of its two conditional expectations, so choosing the larger cannot decrease it. Each clause contributes a constant-degree expression in ; since , these expectations can be compared exactly in the fixed quadratic field with polynomial bit complexity. The final deterministic assignment therefore hasThis is the golden ratio approximation for MAX-2SAT, under the stated restriction on normalized singleton clauses. Arbitrary conflicting singleton clauses do not admit the same independent-bias guarantee.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 38 1 c Solution Created 2026-10-03 Updated 2026-10-06
Predictability means is -measurable. If , each product is integrable, and the finite sum defining is integrable. Pulling the bounded predictable factor out of the conditional expectation givesTherefore the bounded predictable martingale transform is a martingale starting at zero.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 38 3 a Solution Created 2026-10-03 Updated 2026-10-06
Write the discount factor as . Splitting the time integral at givesThe random variable lies in because the short rate is nonnegative and continuous on the finite maturity interval. A process of conditional expectations of an integrable terminal variable is a martingale, by the tower property of conditional expectation. Therefore
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 38 3 d Solution Created 2026-10-03 Updated 2026-10-06
Use the same affine drift cancellation with terminal conditions , . It gives , , soThe process is bounded, which justifies the conditional expectation identity. The Bayes formula for conditional expectation for the forward measure now givesThe denominator is positive; the ratio lies in and equals at maturity. This is the forward-measure terminal rate in a linear bond model.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 79 4 Solution Created 2026-10-03 Updated 2026-10-07
A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.
The needed tetrahedron removal lemma says that for each there is such that a three-uniform hypergraph on vertices with fewer than copies of can be made -free by removing fewer than hyperedges. Equivalently, being a fixed positive edge-edit distance from -free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling .
Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.
Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than . A surviving selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.
To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on bywhere denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix first. Apply the Cauchy-Schwarz inequality over to remove , duplicating . Next apply the Cauchy-Schwarz inequality over the variables other than to remove the two factors from , duplicating . A third application removes the four factors from and duplicates . The resulting eighth power is exactly the cube average displayed above. Averaging over proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.
For example, on complete pair supports, if four triple-edge functions have constant parts and , telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from by at most , so it is positive when . On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.
We now prove the four-term progression hypergraph encoding completely. Let have subset density at least , choose , and take four disjoint copies of the cyclic group . Put a hyperedge on the three vertices excluding part precisely whenFor a transversal quadruple let and . Its four edge conditions are , . Thus a gives a four-term arithmetic progression with common difference modulo .
Suppose has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in must also be an integer progression: each consecutive second difference has absolute value less than , so its congruence to zero is an equality. Therefore every in this hypergraph has , and all four values equal some . For each , the system , has exactly solutions: choose , solve first for , and then for . There are exactly copies of .
These copies are edge-disjoint. Indeed, an edge missing part has exactly one completion with , obtained by setting . Its common value is the already prescribed . Hence destroying all copies requires at least edge deletions. Since , this is at least . Apply the tetrahedron removal lemma to the vertices with, for instance, . It would permit fewer than deletions once is large: the copy count is eventually below its fixed threshold . This is impossible.
Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 14 1 Solution Created 2026-10-03 Updated 2026-10-06
Use probability measure-preserving systems: is measurable and . Its invariant sigma-algebra isErgodicity means that every invariant measurable set has measure zero or one:Equivalently, every invariant measurable function is constant almost everywhere. Indeed all rational sublevel sets of a real invariant function belong to , so the zero-or-one alternative forces its distribution to concentrate at one value. Apply this to real and imaginary parts for complex functions. Conversely, an invariant set has an invariant indicator, so the function criterion implies the set criterion. This is the invariant-function characterization of ergodicity.
For an irrational rotation of the circle, with , an invariant has Fourier coefficients satisfyingFor the multiplier is nonzero. Completeness of the Fourier series basis therefore makes constant. Apply this to an invariant indicator to prove the irrational rotation is ergodic. A second example is the cyclic permutation of points with equal masses: a nonempty invariant set contains the whole cycle and hence has measure one.
The identity on with Lebesgue measure is not ergodic, since is invariant and has measure . Nor is rotation by on the circle: the setis invariant and has measure . These examples also show why preservation of measure does not imply ergodicity.
Let be the Koopman operator, , and setThe Von Neumann mean ergodic theorem says that, for , these Cesaro averages converge in to the orthogonal projection onto the invariant functions:For an invertible system, is a unitary operator. The Hilbert-space theorem states more generally that the Cesaro averages of any unitary operator converge strongly to its fixed-space projection.
Here is the requested invertible-case proof. Since ,Thus the orthogonal decomposition for unitary ergodic averages isOn the first summand, . On a vector , telescoping givesBecause , approximation extends this convergence to the closure of the range. The orthogonal decomposition now proves the theorem for every . An invariant function is -measurable, and an -measurable function is invariant by approximation with indicators; hence the projection is the stated conditional expectation.
In an ergodic system, invariant functions are constants by the criterion already proved. Their orthogonal projection is obtained by taking the inner product with , whose norm is one. Therefore the ergodic limit is the space average:
The Birkhoff ergodic theorem states that, for ,The limit is invariant, integrable, and has the same integral as . On a probability space convergence also holds in . In an ergodic system the limit is almost everywhere.
For the topological sharpening, take a continuous map on a compact metric space. Unique ergodicity means there is exactly one invariant Borel probability measure . The uniform ergodic convergence for uniquely ergodic systems says that every continuous real or complex satisfiesThus convergence holds at every point and uniformly in that point. The continuity, compactness and continuous-observable hypotheses belong to this theorem; it is not a claim of uniform convergence for all measurable functions.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 14 3 Solution Created 2026-10-03 Updated 2026-10-06
Use a standard Borel probability space so that conditional measures can be realized by measures. The disintegration theorem for a probability measure states the following. For a measurable map between standard Borel spaces and , there is a measurable probability kernel , unique for -almost every , such thatMeasurability means is measurable for every Borel set . More generallyfor integrable , with equality of the last expression almost everywhere. The are the conditional measures of a factor. This also defines conditional measures for a countably generated sub-sigma-algebra, or a measurable partition represented by such a map. Sigma-algebras are considered modulo null sets where necessary.
For an invariant probability measure, disintegrate over the invariant sigma-algebra . On a standard probability space it can be represented, modulo null sets, by a countably generated measurable factor . One justification for this countability is the separability of : a countable dense family of -measurable functions generates modulo null sets. The resulting conditional measures are the ergodic components:Their invariance is one of the permitted facts. It remains to prove that almost every component is ergodic, rather than simply invariant.
Choose a countable generating algebra generating the Borel sigma-algebra of . Apply the Birkhoff ergodic theorem simultaneously to its indicators. For -almost every and all ,Disintegration transfers this common full-measure set to -almost every , for -almost every . On that fiber the conditional expectation is constant and equals . Thus, simultaneously for every ,Fix such a , for which is also invariant. Applying the Birkhoff ergodic theorem to the system with measure identifies these limits withFinite linear combinations of the algebra's indicators are dense in , by the Monotone class theorem. Since conditional expectation is an contraction, its projection onto invariant functions consequently sends every function to its constant integral. In particular, for any -invariant set ,and so . This proves almost every component is ergodic. The countable-test proof of ergodicity of conditional components avoids taking an invalid intersection of uncountably many full-measure sets.
For rotation by , take the quotient map . Its fibers are exactly the five-point orbits. The ergodic components of a rational circle rotation are thereforeEquivalently the component through is . To check the disintegration, for bounded measurable use the change of variables on the five consecutive fifth-intervals:The rotation cyclically permutes the five atoms, preserving their equal masses. A set invariant modulo must contain all or none of this finite orbit, since every atom has positive mass. Thus each is ergodic. Finally, the invariant sigma-algebra is the pullback under : a function invariant under translation by is constant on each orbit and is a measurable function of . This confirms that these are the conditional measures over , not merely some decomposition into invariant measures.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 29 1 iii Solution Created 2026-10-03 Updated 2026-10-06
Put . The stopped martingale in discrete time identityshows that is a martingale: the indicator function is -measurable and the increment has zero conditional expectation. Integrability follows because is selected from the finitely many integrable values .
For the bounded stopping time , the optional stopping theorem in its conditional form givesHere is the stopping-time sigma-algebra. Indeed, for , partition into and apply the martingale identity on each piece. This proves the displayed conditional expectation identity directly.
Let and . Conditional absolute-value domination and the Markov inequality give and, for any ,First choose using the uniform integrability of , and then choose . The estimate is uniform in , proving uniform integrability of a stopped uniformly integrable martingale. No finiteness assumption on is needed.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 29 2 iv Solution Created 2026-10-03 Updated 2026-10-06
Fix deterministic and . The pasting ordered stopping times argument shows that is a bounded stopping time. The given stopped-expectation property, applied to and to the deterministic stopping time , yieldsThis holds for every . Since is -measurable and both time values are integrable, it is exactly the defining test for conditional expectation:Hence is a martingale. This proof of the characterization of a martingale by bounded continuous-time stopped expectations uses only deterministic two-time pastings; the càdlàg assumption and the usual conditions for a filtration are stronger than needed for this implication.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 34 1 b Solution Created 2026-10-03 Updated 2026-10-06
To distinguish the random intensity from its possible values, write it as . Its law is a gamma distribution with shape and rate . HenceFor the Poisson mixture, conditional expectation and conditional variance both equal . The law of total expectation and the law of total variance yieldwhere . Applying the random sum of independent claims formulas with the exponential distribution of the claim sizes gives the portfolio B momentsAt the matched intensity , the expected value for portfolio A is also , whereas its variance is . Thus the expected totals agree, but mixing increases the variance:The extra term is precisely .
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 34 4 Solution Created 2026-10-03 Updated 2026-10-06
In the Bühlmann model, a latent risk parameter is drawn from a population distribution. Conditional on , the yearly observations are independent and identically distributed random variables, with conditional expectation and conditional variance . Define the structural parametersHere is the expected process variance, while is the variance of hypothetical means. The Bühlmann credibility premium is the best affine estimate of from the observed claims, under mean squared error. Predicting the next claim gives the same affine estimate: the extra conditional observation noise contributes the constant to the prediction error.
The law of total variance and conditional independence giveAn affine estimate can be written as : for any chosen , optimizing the constant makes its expected value equal to . The normal equations for the linear least-squares projection areFor they force all to agree, with . Thus the credibility factor and premium areThe credibility factor increases with the observation count and between-risk variance, and decreases with within-risk variance. If , the risk mean is known and ; if and , one observation reveals it and . If both vanish, the premium is the fixed value and the factor is immaterial.
In the specified model, the conditional law is a gamma distribution with shape and scale . ThereforeThe prior is an inverse-gamma distribution with shape and scale . To obtain its moments directly, substitute in the defining integral, obtainingThe Gamma function recurrence yieldsThe assumption makes both structural variances finite. HenceIt follows that the model-specific credibility estimate is
For the Bayes estimator under squared error loss, the quantity to estimate is , so the optimum is its posterior mean. The likelihood function, viewed as a function of , is proportional toMultiplication by the prior shows gamma scale inverse-gamma conjugacy:Although the printed hint only mentions integer shapes, the same substitution and Gamma integral normalize this posterior for every positive real shape, so no integrality of is needed. Its posterior mean gives the Bayesian estimate and comparisonThis exact Bühlmann credibility for gamma claims holds for every observed sample, not merely on average. Here the posterior mean is affine in the sample mean, so the best affine Bühlmann credibility premium is also the unrestricted Bayes estimator under squared error loss.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 2 c Solution Created 2026-10-03 Updated 2026-10-06
First justify the dependence structure rather than assume that adjacent squares behave like an ordinary lag-one ARCH model. Write . Iterating its nonnegative recurrence givesThe product coefficient has expected value , so it tends to zero in probability. The stationary are a tight family; consequently the remainder tends to zero in probability, without needing independence between that remainder's factors. The increasing partial sums therefore give the representationThis proves the parity decomposition of a lag-two ARCH process: even and odd observations are functions of disjoint noise families. It also shows that the positive scale is a function of past noise, independent of . The conditional expectation of given past noise is zero, and the second-moment recursion is . independence of the parity families gives the adjacent-square covariance. ThusTo establish finiteness of the fourth moment before using its recursion, note that the norm of the th term in the positive series for is . The triangle inequality in L2 space makes the series square-integrable when . independence of the current noise and past scale then yieldsand henceIf , a finite would make , which is impossible. Its fourth moment is then infinite. The adjacent-square product remains integrable by parity independence, even in that case.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 2 d Solution Created 2026-10-03 Updated 2026-10-06
The useful autoregressive model is for the squares, not for signed observations. Put andThenThe errors form a martingale difference sequence relative to the noise history, because the current standardized noise is independent of the past. When the fourth moment is finite they have finite variance and are uncorrelated across distinct times, although their conditional variance depends on the regressor. In centered form, .
For ordinary least squares, use the response-regressor pairs , , . With their separate means and , minimize . If the regressor sum of squares is positive, the estimators areThe two means use the matched pairs; replacing them indiscriminately by a single full-sample mean is not the exact least-squares formula. The noise-series representation supplies an ergodic stationary process. If , finite regressor second moments and the error's zero conditional expectation justify the usual population regression and statistical consistency argument. The observations still define a finite-sample least-squares fit outside that moment range, but the ordinary finite-variance justification must not be claimed there. If parameter constraints are required, minimize the same criterion subject to and , rather than assert that unconstrained estimates automatically satisfy them.