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 2015 iii Paper 38 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
P is the class of decision problems decided by a deterministic algorithm in time polynomial in the encoded input length. NP is the class whose yes-instances have complexity certificates of polynomial length that a deterministic algorithm verifies in polynomial time.
A decision problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP admits a polynomial-time many-one reduction to it. Such a reduction maps an instance to an instance in polynomial time and satisfies is a yes-instance if and only if is a yes-instance. Membership in NP and NP-hardness are both required.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
On the dashed spanning tree, the nonzero flows arewith and all non-tree flows zero. The tree balances give supply four at vertex , demands one at and , and demand two at . Its cost is .
Choose and make the tree network reduced costs zero. The resulting network dual potentials areFor the non-tree edges, in the order , the network reduced costs areOnly has negative network reduced cost, so it enters the basis.
Adding this edge to the tree creates the graph cycle . Increasing its flow by adds on and subtracts on . These signed changes preserve every flow balance. The simplex ratio test allows , and the objective decreases by because the cycle's signed cost is .
Take and remove from the basis. The other tied edge remains a zero-flow basic edge; this is a legitimate degenerate tree basis and requires no extra pivot. The new flow isIts cost is . For the new tree, chooseEvery network reduced cost is nonnegative: the new non-tree costs for are . All positive-flow edges have zero network reduced cost, and the dual objective is . Thus complementary slackness gives
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Choose the oriented incidence matrix convention with at an edge's tail and at its head. Let be net supply, so . The uncapacitated minimum-cost flow problem on a finite directed graph isor . Negative denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.
For vertex network dual potentials , the optimization Lagrangian isThe infimum over is finite exactly when every network reduced cost is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.
If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank . A set of independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For the converse, construct a phase-I linear program with a common violation variable:where is unrestricted. This linear program is feasible for sufficiently large , bounded below by zero, and attains its optimum. If the two linear polyhedra are disjoint, its optimum is strictly positive: an attained zero optimum would give a common point.
For nonnegative vectors , its optimization Lagrangian isTaking the infimum over and gives the Lagrangian dual problemBy strong duality for linear programming, an optimal dual pair exists and has objective . It supplies the infeasibility certificateTake . Every and obeysThe assumed nonemptiness of each linear polyhedron also ensures : if , their feasibility would force both and to be nonnegative. This proves the strict separation of disjoint linear polyhedra using Lagrangian duality.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Setting the third coordinate to zero and the first to four leaves and . Thus works. Direct substitution givesHence this point lies in both linear polyhedra.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For any feasible , increasing lowers the objective, so the additional upper bound makes . Feasibility then requires . The lowest feasible value of on the circle occurs at the lower intersection with . Solving gives the candidateA global certificate avoids relying on the circle sketch. Introduce Lagrange multipliers for , and :ChooseThe coefficient of vanishes, and , . Therefore completing the square yieldsThe candidate minimizes globally and satisfies both active inequality constraints, so complementary slackness and the Lagrangian sufficiency theorem give
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For minimization, the optimization Lagrangian isIts coefficient of is , so its infimum over unrestricted is for every allowable Lagrange multiplier. There is no finite global minimizer of the optimization Lagrangian to which the Lagrangian sufficiency theorem could apply.
The primal minimization problem is also unbounded: set , and . These points are feasible, and . Hence
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
With and , the maximization optimization Lagrangian isA finite unconstrained maximum requires to cancel the coefficient of . With , completing the square givesThus its global maximizers have and . The equality constraint holds, and complementary slackness with makes , giving . The Lagrangian sufficiency theorem certifiesEvery feasible point has objective at most , so this is a global conclusion rather than just a stationary-point calculation.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a maximization problem with and , use the optimization LagrangianThe Lagrangian sufficiency theorem says: if is feasible, globally maximizes over its original domain, and complementary slackness holds, , then globally maximizes over the feasible set. Equality Lagrange multipliers have no sign restriction. For every feasible ,which proves the theorem.
For a minimization problem, reverse the signs in the optimization Lagrangian: take , with . If a feasible globally minimizes this optimization Lagrangian and satisfies complementary slackness, thenThe hypothesis is a global extremum of the Lagrangian. Merely solving its stationarity equations is insufficient; no convexity assumption is needed when the global extremum itself has been proved.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 5 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
First require a proper target: and . The Metropolis–Hastings algorithm uses the Metropolis–Hastings acceptance probabilitySufficient general conditions are phi-irreducibility, aperiodicity, and a drift-minorisation condition establishing geometric ergodicity of the resulting chain, together with a stationary th moment for the observable being averaged. These imply the central limit theorem for a geometrically ergodic Markov chain. The observable's moment condition must be included: conditions on the sampler alone cannot give the theorem for every arbitrary function.
A concrete stronger condition, directly in terms of the proposal, isTogether with a bounded observable, this is an especially simple sufficient answer. The accepted proposal density is , so it is at least . The kernel satisfies a global minorization condition with the target, hence uniform geometric ergodicity, positive Harris recurrence, and aperiodicity. An independent proposal whose importance weight is uniformly bounded is one example. No claim of these properties follows merely from writing down a positive proposal.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 5 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
A convenient general-state-space ergodic theorem is the following. For a positive Harris recurrent Markov chain with invariant probability measure , and a measurable function with ,Here is the stationary expected value. Harris recurrence means that every set of positive irreducibility measure is visited almost surely from every state; positive recurrence supplies an invariant probability rather than only an infinite invariant measure. The ergodic theorem for a positive Harris recurrent Markov chain holds from any starting state under these Harris hypotheses. aperiodicity is not necessary just for averages.
A useful sufficient form of the central limit theorem for a geometrically ergodic Markov chain adds aperiodicity, geometric ergodicity, and for some . It givesThese are sufficient hypotheses, not a claim that irreducibility alone ensures a central limit theorem. The Markov chain Monte Carlo asymptotic variance uses stationary covariances , with . The series is absolutely convergent under the stated sufficient assumptions. If , write and , where the integrated autocorrelation time is . When , the effective sample size of a Markov chain is approximately . Negative correlations can reduce the asymptotic variance; a zero asymptotic variance gives a degenerate normal limit. For constant , variance is zero and the autocorrelation normalization is undefined.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 5 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure such that, for every measurable and every starting state ,Equivalently, there is positive probability of eventually reaching every set of positive reference measure. For a finite state space with counting measure, this becomes ordinary irreducible Markov chain accessibility. On a continuous space, requiring access to each individual point would usually be inappropriate; positive-measure sets play that role. Irreducibility requires positive probability, rather than probability one, and does not itself assert recurrence or a finite mean return time.
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






