Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 210 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Use the natural cubic spline convention appropriate to the interior design knots: the spline is linear on and . We also need . These points will be important for uniqueness.
A cubic spline is a function in whose restriction to each of , , through is a polynomial of degree at most three. A spline knot is a junction between consecutive pieces. For a natural cubic spline, the two exterior pieces are affine functions; equivalently, one uses the natural endpoint conditions on the spline over and then extends linearly with matching derivatives. Merely prescribing on otherwise arbitrary exterior cubic pieces is a different condition and does not provide the unique interpolant invoked in this question.
The natural cubic spline interpolant to values is the natural cubic spline satisfying . Its existence and uniqueness for are the interpolant fact allowed in the PDF. The interpolation map is a linear map: a linear combination of interpolants satisfies the same spline, boundary and value conditions, so uniqueness identifies it with the interpolant to the corresponding linear combination of value vectors.
Let , let have the same values, and put . Then . We prove the orthogonalityApply integration by parts twice on each polynomial interval. On an interior interval, , andThe terms vanish because vanishes at the knots. The terms cancel at internal knots because and are continuous, and vanish at because is zero there. On the exterior intervals, identically. Summing therefore gives the claimed orthogonality without assuming that is continuous across knots.
Expanding the square now gives the minimum roughness property of the natural cubic spline interpolantEquality forces everywhere, since is continuous. Thus is an affine function. It vanishes at two distinct design points, so , proving equality if and only if .
For the penalized fit, take the allowed spline roughness penalty matrix to be a symmetric matrix with ; thus it is a positive semidefinite matrix. If its supplied representative were not symmetric, its symmetric part defines the same quadratic form and is all that is needed. For any , let . Replacing it by preserves every fitted value and can only decrease the second derivative roughness penalty. Therefore it is enough to minimizeover . The matrix is a positive-definite matrix, sinceCompleting the quadratic or differentiating gives the unique solutionThis is the cubic smoothing spline. More explicitly, the normal equations are , andFor an arbitrary function with fitted vector , the earlier orthogonality also givesBoth terms are nonnegative. Equality forces and, by the proved interpolation equality case, . This proves both existence in and uniqueness over the entire stated function class, not just over splines.
The argument is deterministic for each observed . The fixed-design nonparametric regression and homoscedasticity assumptions motivate the squared-error loss, but Gaussian errors are not required.
At least two distinct design points are required for uniqueness. Question 4 does not explicitly restate , and this hypothesis is necessary. With one design point, every function has zero residual and zero second derivative roughness penalty, for any real . Thus the printed unrestricted uniqueness conclusion would be false for . The corrected theorem assumes at least two distinct knots and the stated linear-tail convention. At , uniqueness over all of also fails; the stipulated eliminates that degeneracy.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 210 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Let and be Radon-Nikodym derivatives. Use the following normalizations of the Kullback-Leibler divergence, total variation distance and unnormalized Hellinger distance:We use and assign infinite Kullback-Leibler divergence if , where denotes absolute continuity of measures. Common domination alone also suffices for the inequalities with the extended-value convention. The negative part of the logarithmic integral is integrable: on , . Thus the extended-value integral defining the Kullback-Leibler divergence is well-defined. These expressions do not depend on which common dominating measure is chosen. The Kullback-Leibler divergence is generally asymmetric and therefore fails a defining property of a metric.
For completeness, the integral formula for total variation distance follows by taking : since , the positive and negative parts of have the same integral, and this set attains the supremum.
Put , by the Cauchy-Schwarz inequality. A second application givesThe logarithmic inequality in the hint implies for . Apply it to on :Multiplying by and integrating provesIf on a set of positive -measure, the right side is finite but the Kullback-Leibler divergence is infinite, so the inequality is immediate. ThusThis total variation–Hellinger–relative entropy inequality requires the stated Hellinger distance normalization for its first constant. With the alternative convention , the correct comparison is and . In particular, and have .
Here is a testing form of the Le Cam two-point lemma. Suppose two parameter values in a metric space have separation , and let be the corresponding observation laws. Every estimator satisfiesTo prove it, classify by the closer of the two parameters, breaking a tie in favour of one. Let . On , the triangle inequality implies , while on it implies . Hence the sum of the two probabilities in the display is at leastAt least one is at least half the sum, proving the claim. It also gives a lower bound for the maximum expected metric loss.
For absolute-error loss, or any loss given by a metric, there is a stronger expectation form. Take densities relative to and use the triangle inequality under their overlap:Therefore the Le Cam lower bound under absolute-error loss isBoth arguments are valid for randomized estimators as well, by adjoining the independent randomization to the observation; doing so does not change total variation distance.
For the normal distribution model, assume the usual nondegenerate convention and use the full product observation laws. ChooseFor one observation, its Gaussian log likelihood ratio isUnder the first law, and . Thus the Kullback-Leibler divergence between normal distributions isFor the independent and identically distributed random variables, the joint log likelihood ratio is the sum of the individual ones, so the Kullback-Leibler divergence of the two full statistical samples is . The comparison just proved implies . Applying the expectation form of the Le Cam two-point lemma givesThis is a Gaussian location minimax lower bound under absolute-error loss. The constant may depend on the fixed known , but neither on the estimator nor on . If a signed nonzero scale were used, the same result holds with in place of . If zero noise were allowed, would estimate exactly, so a positive lower bound would be false; positive variance is necessary.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 210 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Choose a Borel measurable function version of the posterior success probability . Conditional on , predicting zero has error probability and predicting one has error probability . A Bayes classifier for zero-one loss is thereforeEither decision is optimal when . The displayed Bayes risk also equals and is unaffected by changing on a -null set.
For any measurable set , independence and the uniform distribution of giveLikewise the probability with label zero is . These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.
Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the or labels. Let be the label attached to the th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When , this is the one-nearest-neighbour classifier .
Write for the selected original index. Conditional on all features , it is fixed, and is still uniform on . The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query , rather than being a fixed relabeling of the training data for all queries. For a variable with the uniform distribution on , the two threshold indicators at differ exactly when lies between them, an interval of length . This Bernoulli coupling by a shared uniform random variable proves
Take the test pair independent of the training data and its auxiliary uniforms. Let , and interpret as conditional misclassification risk given . The tower property of conditional expectation gives . Conditional on the test feature and all training features, and are independent variables with a Bernoulli distribution of parameter . Consequently, for every ,This is an exact finite-sample equality, not merely a limit.
The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk
For , put . Then , and . Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant , its limiting misclassification risk is , while .
Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary . For a counterexample, take almost surely and constant , and choose among the coincident neighbours the one with the smallest . Then the predicted label is one with probability , so its misclassification risk tends to , exceeding the claimed upper bound . The corrected theorem uses ties determined independently of the uniforms and labels, as above.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 210 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
For a kernel for density estimation with integral one and a smoothing bandwidth , the univariate kernel density estimator isIts expected value isThis is the convolution identity. It holds wherever the integral is defined, in particular everywhere for the bounded kernel used below. For a nonnegative kernel for density estimation, Tonelli theorem also gives the identity as an extended nonnegative integral. A signed kernel for density estimation instead requires absolute integrability for this interchange.
For the centred unit-width uniform kernel, substitute :Put . The Taylor theorem with Lagrange remainder givesThe odd function term integrates to zero, while . Hence the bias of a kernel density estimator obeysThis is a second-order pointwise bias bound for kernel density estimation. Existence and boundedness of the second derivative suffice for the stated remainder; continuity of that derivative is not an extra assumption.
For concentration, writeThe are independent and identically distributed random variables with a Bernoulli distribution, and . The required concentration bound follows from the Hoeffding lemma. We prove its Bernoulli case directly. Withwe have and , where is the exponentially tilted success probability. Therefore for every real . If or , the centred variable is identically zero and the same bound holds directly.
Independence and the exponential form of the Markov inequality now give, for ,Choose . Applying the same argument to the lower tail and adding the probabilities proves the Hoeffding inequality
To obtain the requested variance constant, use the additional bound that a probability is at most one. Set and . The tail integral formula for moments, justified by Tonelli theorem, yieldsThusThe clipping at one is essential for this integration argument to give that constant. It is an instance of a second moment bound from a clipped Gaussian tail. The exact Bernoulli distribution calculation also gives , an even stronger bound.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





