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 2009 iii Paper 32 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use the natural filtration and the usual integrable definition of the Snell envelope. Since the factors are positive, its terminal value is . If , independence of random variables givesThe backward recursion therefore becomesThis proves the assertion by backward induction. All constants are finite and at least one. More explicitly,where the empty product is one. This is the Snell envelope of a multiplicative process. The standard Snell envelope hypothesis includes integrable rewards; independence of random variables and positivity then give finite first moments of the factors. If that hypothesis is dropped, an infinite-mean factor gives an infinite continuation value, so finite constants need not exist.
For the discrete-time binomial market, write . The assumptions give , positive bank account and stock prices, andThusThe finite discrete-time fundamental theorem of asset pricing states that a market with a strictly positive numéraire has no arbitrage if there is an equivalent probability measure under which all numéraire-denominated asset prices are martingales. The original probability measure is already such an equivalent martingale measure, proving no arbitrage.
The complete-market American-option pricing theorem identifies the discounted replication or superhedging value with the Snell envelope of the discounted exercise rewards. HereThe independent factors have common meanThe Snell envelope recursion consequently gives . At every time before , the continuation value strictly exceeds immediate exercise, so optimal exercise is at maturity. The undiscounted value process is , and the time-zero replication cost isIn fact is a martingale, not just a supermartingale, because the Snell envelope has no exercise compensator before maturity.
To hedge the optimally exercised payoff, subtract the two next-state portfolio equations. The first-period delta hedge isThe corresponding bank account holding, since , is . Substitution into either next-state equation verifies both terminal values at time one. Repeating this two-state calculation at every node gives a self-financing strategy replicating the maturity payoff. It also covers earlier exercise: at all dates, so the seller can meet any earlier payment with the available wealth.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 32 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A one-period self-financing strategy is a deterministic holdings vector , with initial cost and terminal wealth . In the zero-initial-cost convention, an arbitrage satisfiesThe convention allowing a nonpositive initial cost is equivalent here: invest any initial proceeds in the strictly positive numéraire to obtain a zero-cost portfolio with nonnegative terminal wealth.
Suppose a strictly positive state-price density satisfies the asset-pricing equations, with the indicated products integrable. By linearity,For an arbitrage, the right-hand side is zero while the left-hand side is strictly positive, since the integrand is nonnegative and is positive with positive probability. This contradiction proves absence of arbitrage.
An attainable European contingent claim is a terminal random payoff for which some holdings vector satisfies almost surely; its replication cost is . To prove uniqueness in a complete market, suppose is another positive state-price density. For every event , attainability gives a portfolio replicating . Its initial cost has both representations, soThe signed random variable here is integrable, because . Take to be the event where it is positive and then where it is negative. Both its positive and negative parts have expectation zero, and hence vanish almost surely. Since ,This proves that complete markets have unique state-price densities without requiring an extra lower bound on the random terminal numéraire.
For the finite-state example, order the states from top to bottom in the diagram and write the density values as . The two pricing equations areAdding gives . Put ; substitution then givesThese are all the strictly positive solutions, and each satisfies both equations. The parameter is a state-price-density value, not a probability.
For a concrete unattainable contingent claim, take the payoff vector . A replicating portfolio would have to satisfy and in the first and third states. These imply , contradicting the required payoff one in the middle state. Thus the market is an incomplete market, despite having strictly positive state-price densities.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 31 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A martingale describes an observable after its predictable drift has been removed. For a Markov chain the drift is the change produced by its transition operator; for Brownian motion it is one half of the Laplacian. Requiring the resulting processes to be martingales for a sufficiently rich class of observables determines the transition law itself. The same identities, combined with optional stopping, determine hitting probabilities, expected exit times and recurrence or transience. The duplicated Q5 paragraph in the PDF is a repeated printing of this one essay request.
For a finite or countable-state Markov chain with transition matrix , define for a bounded test function . The Markov property says . Consequentlyis a martingale, since each increment has conditional expected value zero. Conversely, if these processes are martingales for every bounded , taking the conditional expectation of an increment recovers that identity. With it gives for every state . Thus, given the initial law, these identities characterize the Markov chain, not merely a few of its moments. This is the discrete-time Markov chain martingale characterization.
The drift operator is . If away from a target set, is a stopped martingale, where is the first hit of that set. Under boundedness or suitable uniform integrability, the optional stopping theorem expresses in terms of boundary hitting probabilities. Similarly, if away from the target and on it, then is a martingale, giving when the terminal limit is justified.
For a concrete calculation, take a simple symmetric random walk on stopped at , its first hit of or . In the interior, has zero drift, while satisfiesThe stopped identity gives , proving finite with finite mean. Bounded convergence in both stopped identities now yields the gambler's ruin answersThis illustrates why the integrability justification is part of using a martingale, rather than an automatic consequence of writing an equation.
For a finite-state continuous-time Markov chain with generator matrix , the corresponding martingale problem for a continuous-time Markov chain usesThese are martingales. Conversely, suppose an adapted càdlàg finite-state process satisfies these identities. Let , fix , and set . Then . Apply deterministic integration by parts to the finite collection of indicator martingales to obtain the time-dependent Dynkin formula: is a martingale. ThereforeThis recovers the Markov property and the entire semigroup, proving the characterization. On countable spaces one uses nonexplosion and localization to justify the analogous unbounded-rate formulas.
For -dimensional Brownian motion, the Itô formula shows that, for ,is a true martingale, since its bounded derivatives make the integral square-integrable on each bounded horizon. This is the martingale problem for Brownian motion with generator .
Here is why it also characterizes Brownian motion. Suppose a continuous adapted process , with , satisfies that martingale problem. Use smooth cutoff test functions equal to and inside successively larger balls, and stop before leaving those balls. The coordinate tests show that are continuous local martingales; the product tests show that are local martingales. The Itô product rule consequently givesthe difference between the two proposed compensators is a continuous finite-variation local martingale, hence constant and zero at time zero. For each , another application of the Itô formula gives the exponential local martingaleIts modulus is the deterministic quantity , so it is a true martingale on every bounded time interval. Taking its conditional expectation and dividing by its known value at time givesThe conditional characteristic function identifies a centered multivariate normal distribution of covariance , independent of the past. Together with continuity, this is the defining law of Brownian motion. This proves the Lévy characterization of multidimensional Brownian motion in the form needed for the generator characterization.
The analytic use of these martingales parallels the chain case. A harmonic function satisfies , so it yields a stopped local martingale until the process leaves its domain of harmonicity. Bounded stopped observables permit optional stopping and solve boundary hitting problems. A solution of with zero boundary values gives an expected exit time. For example, in the ball of radius , gives ; stopping first at proves finiteness and justifies the limiting calculation. The Brownian local time construction in Q4 is another example: the predictable compensators of approximations to recover its increasing occupation term.
We now prove the required three-dimensional transience of Brownian motion in dimension at least three, in the strong sense almost surely. Start first at a point with , and let be the first exit from this annulus. The radial Laplacian in dimension three givesThus is a bounded martingale. The exit time is finite: stopping gives . At exit, continuity puts at either or . The optional stopping theorem therefore yieldsand hence the Brownian sphere-hitting probability in dimension threeAs , the events increase to : a continuous path is bounded on the finite interval preceding any finite inner hit. This argument assumes no transience. ConsequentlyTo pass from a positive escape probability to almost-sure eventual escape, take Brownian motion started at zero. Let be its first hit of the sphere of radius . Stopping the squared-norm martingale proves . At , the Strong Markov property and the preceding hitting formula giveThe Strong Markov property here follows from independent Brownian increments by approximating a stopping time from above with dyadic-valued stopping times and using path continuity. Choose . The exit times increase to infinity, since a continuous path is bounded on every compact time interval. The events of a return to the closed ball of radius after decrease and have probabilities . Their intersection has probability zero. Thus almost surely there is some finite exit time after which the path never again enters that ball. Apply this simultaneously to all positive integer . This proves the last visit to a bounded ball for three-dimensional Brownian motion conclusion and therefore
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 31 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For , the continuous martingale is . Since has the centered normal distribution of variance ,For , the continuous martingale is . The Gaussian fourth moment givesThis verifies both cases. The time integral in the printed identity is understood with its omitted .
Write . The derivatives of the approximations areThus . The Itô formula gives . This use of the formula is valid despite the two second-derivative discontinuities: mollify the function , whose derivative is Lipschitz. Its smooth derivatives converge boundedly, while the second derivatives are bounded by and converge except at . For every , the normal distribution of assigns those points zero probability. Dominated convergence for the drift integral and the Itô isometry for the stochastic integral pass the smooth formula to . Equivalently, this identifies the martingale in the assumed decomposition and permits its cross-covariances to be calculated.
If , then . The Itô isometry and Doob L2 maximal inequality therefore give, for every fixed ,The Gaussian density is bounded by , soConsequently the processes are Cauchy in the complete space of continuous random paths with norm . They have a continuous-path limit there. Limits obtained for different integer horizons agree on overlaps; choose these versions consistently. Each is adapted, and passing to the limit in shows that is a continuous martingale. Letting in the preceding bound proves the requested convergence, with an explicit rate:The same Itô isometry identifies , with .
There is a genuine factor-of-two error in the last printed conclusion. The stated has second derivative almost everywhere, and the generator in the decomposition is one half of the second derivative. Hence the exact identity isBecause and , this already proves uniform convergence on bounded intervals to . It does not by itself prove almost-sure convergence of the full sequence, so we supply that additional step.
Take . For each fixed integer and each , the maximal-error bound and Markov's inequality implyThe first Borel-Cantelli lemma, applied to rational positive and integer , gives uniform almost-sure convergence of this subsequence on every bounded interval. Therefore uniformly there almost surely.
For , the indicator windows are nested. The ratio-one interpolation for shrinking-window occupation integrals givesBoth ratios tend uniformly to one as . The two bounds converge uniformly to the continuous nonnegative process , so the entire sequence does too. Thus the correct normalized conclusion isand with the factor actually printed in the question the limit isThese are the occupation approximations for Brownian local time. In the Tanaka formula convention, is the local time of a semimartingale at zero. It is not identically zero: for , since starts at zero and is a martingale. Thus the discrepancy cannot be removed by treating the two limits as equal. The standard normalization is also given in Lalley's notes on the Itô calculus and local time.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 31 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
On the real line, Prohorov's theorem states that a sequence of probability measures is uniformly tight if and only if every subsequence has a further subsequence converging weakly to a probability measure. Here uniformly tight means that, for every , some compact interval contains mass at least for every measure in the sequence. This is relative sequential compactness for weak convergence of probability measures, not merely the existence of one convergent subsequence.
We first prove the characteristic-function tail bound. Put . For ,At the expression is zero by continuity. If , the supplied elementary bound, with , makes it at least . The integrand is nonnegative, so Tonelli's theorem yieldsThus one valid universal constant isThe estimate controls spatial tails using only the characteristic function near zero.
Apply it to each . For fixed , pointwise convergence of the characteristic functions and the bound allow dominated convergence on the finite integration interval, givingContinuity of a characteristic function and make the last expression tend to zero as . Given , choose making it less than ; then for all sufficiently large , the preceding tail is less than . Enlarge the compact interval to handle the finitely many remaining probability measures. This proves uniform tightness of the whole sequence.
By Prohorov's theorem, every subsequence has a further weakly convergent subsequence, say with limit . The real and imaginary parts of are bounded continuous functions, so along that subsequenceThe uniqueness theorem for characteristic functions implies . All subsequential weak limits are therefore . If the original sequence failed to converge weakly to , a bounded continuous test function and a subsequence would keep its integrals a fixed distance from the limiting integral; a further weakly convergent subsequence would contradict that. HenceThis supplies the required proof of the Lévy continuity theorem in the stated case.
For the final request, the printed is not defined; the intended function is , the characteristic function of a summand. We prove that without assuming integrability. Write . Independence gives . Moreover convergence in probability to implies uniform convergence of these characteristic functions on each bounded frequency interval: for and ,First let , then .
The potential logarithm-branch ambiguity needs to be resolved, not discarded. By continuity of near zero, its principal complex logarithm is defined at for all and all large , with value zero at . Alsouniformly on , so uniformly there. The two continuous logarithms differ by an integer multiple of :That integer is continuous in and zero at zero, hence identically zero. ConsequentlyFor arbitrary nonzero , take and . Eventually , so dividing the preceding error by shows . Exponentiating at zero proves the derivative forced by the weak law:This is the weak law forces a characteristic-function derivative argument. Its estimates use bounded exponentials, not . If is integrable, dominated convergence permits differentiation inside the expectation and gives , so then .
Absolute integrability is genuinely unnecessary. For an explicit weak law without an absolute first moment, take a symmetric variable withwith mass at zero and no mass with . This is a valid law: the specified tail decreases from to zero, and its derivative defines the continuous part beyond . Its absolute first moment is infinite because . For independent copies, set . Symmetry gives , and integration of the tail givesFor the last estimate, split the integral at ; the initial part is and the remainder is at most , apart from a fixed initial constant. Chebyshev's inequality now gives in probability. The probability that any truncation changes a summand is at most , so in probability although . The derivative is zero, but the usual expectation of does not exist.
If either the positive or negative part is integrable, the finite weak-law limit does force full integrability. For example, if , then is integrable and its sample averages have the weak law of large numbers limit . Since they are bounded above by the original averages, for every . Letting shows . The symmetric argument handles the other one-sided hypothesis. The nonintegrable example necessarily has both one-sided expectations infinite.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 31 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A Lévy measure on the real line is a nonnegative Borel measure satisfyingIt records the intensity per unit time of jumps of a Lévy process. Under the additional small-jump first-moment condition, the uncompensated Lévy–Khintchine formula iswhere and . The integral is absolutely convergent: near zero its integrand has absolute value at most , while outside a neighborhood of zero it is at most and has finite mass. If the usual compensated Lévy–Khintchine formula uses drift , this convention has .
A Lévy process starts at zero and has stationary independent increments and stochastic continuity. Its characteristic function at time is , with and continuous. The given time-one characteristic function is strictly positive. It therefore has the unique continuous logarithm vanishing at zero,Any other continuous exponent would differ by an integer multiple of ; continuity on the real line and the value at zero make that integer identically zero. This determines all increment laws. More explicitly, for ,Thus it determines every finite-dimensional distribution. For the standard càdlàg version of a Lévy process, coordinates at rational times determine the path, so these laws determine the entire process law on its canonical path space as well.
To find the Lévy measure, try the symmetric density . Its jump exponent isDifferentiation under the integral is justified by the integrable bound . The elementary Fourier sine transform givesSince , integration in yields . Choosing matches the prescribed exponent exactly. This is the Lévy measure of a symmetric Laplace time-one law:The candidate satisfies the Lévy measure condition because its density is of order near zero and decays exponentially at infinity; moreover . Uniqueness of the triplet in the Lévy–Khintchine formula proves that these are the required coefficients. The infinite mass near zero means infinitely many small jumps, not a Gaussian component; their total variation is finite on bounded time intervals because .
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 31 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For , let be the number of completed upcrossings by the observations : buy when the value is at most , sell at the first subsequent value at least , and repeat. With , one form of the Doob upcrossing inequality for a martingale isFor completeness, hold either zero or one unit according to this rule. The holding at each step is measurable before the next martingale increment, so the total gain has expected value zero. Completed trades earn at least each; an unfinished trade loses at most . Thus , proving the inequality.
Suppose . For each rational pair the inequality and monotone convergence giveEvery rational interval therefore has only finitely many upcrossings, simultaneously outside a countable union of null sets. If , there is a rational interval strictly between them and infinitely many upcrossings, a contradiction. Thus the limit exists in the extended real line almost surely. Fatou's lemma now givesThe limit is finite almost surely and integrable. This proves the martingale convergence theorem rather than using it as the deduction.
The exact extra condition for convergence in L1 is uniform integrability:To see sufficiency, first discard the tails of uniformly and the tail of the integrable . On the set where both absolute values are at most , their difference is bounded by and tends to zero almost surely; dominated convergence finishes the proof. Conversely, if in , thenMake the first term uniformly small for all sufficiently large , then control the finitely many remaining integrable variables by increasing . Hence uniform integrability is necessary too. In this case the conditional expectation identity follows by taking the limit in for .
The coin-doubling martingale shows why an bound is not enough. Let be independent fair coin indicators and setConditional on the first coins, the next value is either or zero with equal probabilities, so this is a nonnegative martingale. Its expected value is always , while a first failure occurs almost surely, giving almost surely. Yet for every . Indeed, whenever , its tail expected value above is still . Thus convergence in L1 fails because uniform integrability fails.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 30 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Here is the rate per individual active flow, and is its route's aggregate rate. On routes with , a proportionally fair allocation is a feasible positive rate vector satisfyingfor every feasible competitor , where feasibility means . This is equivalent to maximizing weighted logarithmic utility : its gradient gives the displayed inequality, and the supporting-tangent inequality proves sufficiency. The objective is strictly concave on active rates. Rates assigned to absent flows are irrelevant and may be set to zero.
For the linear flow network, an active local route can increase its rate if its link constraint has slack, improving the objective without affecting any other link. ThusPut and . If and , eliminate the active local rates by . Up to constants, the utility becomesIts derivative is , which vanishes exactly atStrict concavity proves this is the optimum, and unused local links impose no stronger constraint because . If , maximizing gives , the same formula. If , each active local route has . These are the proportionally fair allocation on a linear flow network. When , there is no service to allocate.
The memoryless property of exponential document sizes makes a flow transmitting at rate complete with intensity . Summing over its flows gives the flow-level network model transition ratesand, for nonempty states,All absent-route departure intensities, including those at the empty state, are zero. In particular the local completion rate is the aggregate rate , not . Total rates are bounded by , so the continuous-time Markov chain is nonexplosive.
Set and consider the weightsThe binomial coefficient is the balance function of a flow-level network. For a through-route arrival, its adjacent-weight ratio isThe reverse departure rate is , so . For a local-route arrival,and the reverse departure rate is , giving the same detailed balance identity. This includes arrivals from the empty state.
To normalize, first fix all local counts and sum over . The negative binomial series givesThe remaining geometric series factor, soThis is finite precisely under the stated strict load inequalities for each resource. Thus detailed balance proves the stationary law of a linear flow network:With positive arrival rates this is the unique stationary distribution of the irreducible chain. Zero arrival rates are handled by restricting to the accessible class with their counts zero, interpreting .
Summing this distribution over gives local-count independence in a linear flow network:These are independent geometric distributions. Differentiating a geometric series, or summing its mean directly, givesThis independence concerns the local counts at one stationary time; their evolving processes share the through route and are not independent processes.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 30 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Each user maintains a transmission rate . Resource measures its aggregate load and returns the resource congestion price . The user adds these feedback signals to form its route congestion price . Its increase term is the constant , while its decrease term is proportional to both its current rate and the congestion signal. This is a distributed congestion control algorithm: resources need only local loads, and users need only prices along their own routes.
There is a needed distinction in the word increasing. If it permits nondecreasing price functions, the all-zero prices are allowed. Then , so there is no equilibrium. The intended convergence statement holds when each nonempty route meets at least one resource whose price is positive at some load. This is automatic if every price is strictly increasing and nonnegative. We prove it under the more general nondecreasing assumption with this explicit condition, for finite sets of nonempty routes and nonnegative initial rates.
Write . Each is convex and nondecreasing, and the primal congestion potential isOn positive rates this is strictly concave: the sum of positive-weight logarithms is strictly concave, while the resource term is convex. Its derivatives areConsequently the gradient flow with diagonal mobility satisfieswith equality exactly at an equilibrium.
We must also prove trapping and existence of the equilibrium. For each route choose a resource on it and constants such that its price is at least beyond load . Finiteness gives common constants . If is large, a resource on a maximizing route has load at least , so the resource penalty is at least . With , therefore,Once all rates are bounded above, a rate tending to zero also makes through its positive-weight logarithm. Thus every nonempty superlevel set of is compact inside the positive orthant. A maximum exists by restricting to such a superlevel set, and strict concavity makes it unique, say . It is interior and satisfies , equivalentlyConversely every positive equilibrium is a stationary point of the strictly concave function and hence is this maximum.
Only continuity of the price functions is given, so it is useful to justify trajectories without silently assuming differentiability. Put and . The dynamics become ordinary gradient flow ascent, . The function is strictly concave on the positive orthant: its user terms are plus constants, and each penalty is a convex nondecreasing function composed with the convex load . Hence the supporting-tangent inequalities giveThe squared distance between two solutions is nonincreasing, proving uniqueness even though the vector field need only be continuous.
Nonnegative initial rates enter the positive orthant immediately: along a solution, variation of constants in expresses as a positive exponential times plus a strictly positive integral. Also , so rates cannot become infinite in finite time. The distance argument applies after any positive time and, by taking that time down to zero, also proves uniqueness for initial zero rates.
For a positive starting time, the increasing traps the trajectory in a compact superlevel set. Its derivative has finite integral since is bounded above there. It is uniformly continuous in time, being a continuous function of the state on a compact set with bounded velocity. By uniformly continuous integrable functions vanish at infinity, . Every limit point consequently has for every , since all rates are bounded away from zero. There is only the limit point , soThis establishes global convergence of primal congestion control with the needed nonzero-price condition, and supplies the zero-price counterexample when increasing is read in the weak sense.
For the alternative increasing-supply resource-price dynamics, consider the dual congestion potentialIts domain is with every . Each integrated supply is strictly convex, because is strictly increasing, and each negative logarithm of a positive linear function is convex. Thus is strictly convex. Its sublevel sets are bounded: for each , gives a linear lower bound on the supply primitive at large , whereas the negative logarithmic terms grow only logarithmically in . A route-price sum tending to zero makes on a bounded set. A minimum therefore exists in this domain.
The derivatives areIf a used resource had at the minimum, then but , so increasing that coordinate would strictly lower . Therefore the minimizer has strictly positive prices at every used resource. An unused resource has its unique minimizing price zero. At used resources its equations areThe multiplicative dynamics are . On strictly positive used-resource prices, equilibrium is equivalent to these equations, and strict convexity proves existence and uniqueness of the positive equilibrium. No full-row-rank assumption on is needed here: the strictly increasing individual supplies already give strict convexity.
If zero prices at used resources are allowed, the unqualified uniqueness assertion is false because of boundary equilibria of multiplicative resource prices. For one unit-weight route using two resources and , all three price vectorsare equilibria. At the user rate is one; the first resource has demand equal to supply, while the second has zero derivative because its price is zero. The last two vectors do not minimize . Thus the positive-price domain, or a boundary rule preventing a used resource from remaining at zero price, is essential.
Finally, the primal and dual equilibrium equations agree when and are inverse functions on the relevant ranges. For example, continuous strictly increasing prices with and have inverses satisfying the stated supply assumptions. Then is equivalent to , while both systems have . With inverse price and supply functions, the two equilibria describe the same rates and prices. Without this relation they need not agree: for one route and one resource with , and , the primal equilibrium is while the dual equilibrium is .
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 30 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be the routes serving source-sink pair . The source-sink route incidence matrix and link-route incidence matrix areThus fixes the demands, and gives link throughputs. Assume a finite route set with at least one route for each positive demand. A Wardrop equilibrium is a feasible flow for which every used route has minimum delay among the routes for its source-sink pair. Writingthis means that, for each , there is a number with for , with equality whenever . No individual user can reduce its delay by switching routes while treating the aggregate throughputs as fixed.
The feasible set is a nonempty compact convex set: within each source-sink pair its route flows lie in a simplex of total . The Beckmann potentialis continuous and convex, and has . It therefore attains a minimum on . For a differentiable convex function, minimizes exactly whenIndeed necessity follows by differentiating along the feasible segment from to , and sufficiency follows from the supporting-tangent inequality. This condition is equivalent to Wardrop equilibrium. Necessity of the route condition follows by moving a small amount of positive flow from a used route to any other route of the same pair. Conversely, under the route condition,because the terms involving vanish and both flows have the same pair totals. This proves both existence and the claimed convex optimization characterization, with .
Since each is strictly increasing, its primitive is strictly convex. Thus is strictly convex in . If two minimizing flows had different link throughputs, their midpoint would have strictly smaller potential. Hence the equilibrium link throughputs are unique.
The route flows need not be unique. Consider one unit of demand through two successive stages, each with two parallel links, labelled in the first stage and in the second. The four routes are , and all link delays are . For any , chooseEvery link then carries and every route has delay one, so each vector is a Wardrop equilibrium. They all produce the same link throughputs but give distinct route decompositions.
For the toll construction, put . The total delay is and the average delay is , so they have the same minimizers. Compactness of gives a global minimizer , with . Its differentiable objective satisfies the necessary route-flow inequalityThis inequality is necessary even when total delay is not convex, since it follows from the right derivative along each feasible segment.
Use optimal-flow calibrated congestion tolling:Here . The toll is nonnegative, continuously differentiable and nondecreasing, because . The perceived cost is strictly increasing. At it equals , so the displayed necessary inequality makes a Wardrop equilibrium for these perceived costs, by the preceding Beckmann potential argument. Their strictly increasing costs give unique equilibrium link throughputs. Therefore every tolled equilibrium has link loads and minimizes average delay. Constant tolls also suffice; the added positive-part term makes them genuinely traffic-dependent without moving the optimum. Zero total demand is the trivial empty-flow case.
The usual marginal external cost toll makes its Beckmann potential equal , but concluding that all its equilibria minimize requires convexity of . Strict increase of delays alone does not supply this. For example, on two parallel links with and demand six, the equal split is an equilibrium under marginal-cost tolls, while its total delay exceeds , the delay at . The calibrated construction avoids adding a hypothesis absent from the printed question.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 30 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For a fixed routing loss network, let be finite integer resource capacities and the integer resource requirement of one route- call. Assume each route uses a resource, independent Poisson processes of calls with rates , independent exponential distributions of holding times with parameters , and immediate rejection when any required resource is unavailable. There is no waiting. The continuous-time Markov chain of call counts has feasible setPut andThe ratios of adjacent weights satisfy whenever the arrival is feasible. Thus detailed balance proves the product-form stationary distribution of a loss network,An arriving route- call is admitted precisely when . By Poisson arrivals see time averages, its exact blocking probability isDefine to be zero if a capacity is negative. This is an exact finite sum, not an independence approximation for resource blocking events.
For the triangle, denote the physical link capacities by and the numbers of calls between the pairs by . Assume unit capacity per call on each traversed link, unrestricted instantaneous rearrangement of existing calls, no interruption or extra resource cost during rearrangement, and independent exponential distributions of holding times whose parameters depend on the endpoint pair but not on the chosen path. Arrivals for each pair are independent Poisson processes, and admission occurs whenever some routing of all calls is feasible. These assumptions make the count vector a Markov process even though individual paths can change.
The necessary cut constraints areEach counts calls that must cross the two links separating one node from the others. They are also sufficient. If every pair count is at most its direct capacity, route all calls directly. Otherwise at most one pair can exceed its direct capacity: two such excesses would contradict their pairwise cut constraint. Suppose it is , and put . Route of these calls directly and divert the remaining through node . Route the other calls directly. The loads on links and are respectively and by the two cut constraints involving . This is an integer routing of every call. The other cases follow by relabelling.
Consequently the rearrangeable triangular loss network is equivalent, at the level of call counts and blocking, to a fixed routing loss network with three virtual node resources:The columns correspond to , and a call uses its two endpoint resources. Its normalizer isWith now indexing virtual resources, the three exact answers areThe preceding detailed balance proof applies because departures occur at rates regardless of the current routing. Without unrestricted rearrangement, feasibility can depend on the existing path assignments and this equivalence need not hold.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose a surjection . Since is a Noetherian ring, a finite free module is a Noetherian module, and its kernel is a finitely generated module. Choose a finite free surjection and repeat. This constructs a resolution by finitely generated free moduleswhose terms are, in particular, finitely generated projective modules. It may be infinite; the request is finite generation of every term, not finite length.
Now suppose the nonzero finitely generated module has finite projective dimension . For , its th syzygy in this free resolution is projective. Indeed, dimension shifting along the successive kernel sequences givesfor every module . The vanishing follows by computing the latter Ext functor from any length- projective resolution. Vanishing of makes every short exact sequence ending in split: apply the long exact sequence of Ext groups to a free surjection onto to lift its identity. Thus is a projective module. It is finitely generated by the preceding construction. Truncating giveswith every term finite projective.
Apply the Hom functor and write . At the top degree,If this group were zero, would be surjective. The dual module of a finite projective module is finite projective, so this surjection has a section . Finite projective modules identify with their double dual modules: the evaluation map is an isomorphism for a finite free module and passes to its direct summands. Dualizing therefore gives . Hence splits, and is projective. Replacing the last two terms by this quotient shortens the projective resolution to length , contradicting minimality. This proves top Ext detects finite projective dimension:For , is a nonzero finite projective module and embeds as a summand of . Some coordinate projection restricts nontrivially to , proving as required.
For infinite projective dimension, take the dual-number algebra and . Multiplication by has image and kernel both equal to , giving the periodic resolution over dual numbersApplying makes every differential zero, so for every . A finite projective resolution would force all sufficiently high Ext functors to vanish. Thus .
The finite-generation hypothesis is essential if the middle sentence's “a module” is interpreted as an unrestricted new module. A concrete vanishing top Ext without finite generation occurs for and . This Noetherian ring has the exact free presentationInjectivity of follows by examining the largest index of a finitely supported input, since is a non-zero-divisor. For exactness in the middle, use the relations to move a finite sum to its largest index ; its remaining coefficient is , which is zero precisely when its image in is zero. The map onto is surjective because every Laurent series has a lower bound on its exponents.
Applying gives on products the map . It is surjective: for any , set . These are well-defined formal power series, because each coefficient receives only finitely many contributions, and . Consequently . But : the image of every must lie in , since it is divisible by every power of . A nonzero projective module is a summand of a free module and therefore has a nonzero coordinate map to . Thus is not projective, while its displayed resolution has length one. In particular,The nonvanishing conclusion proved above retains the finitely generated introduced at the start of the question.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Here the usual homological algebra convention is that the right-exact functor is additive. Module categories have enough projective modules, because any module is a quotient of a free module. Choose a projective resolutionApply to the unaugmented chain complex and define the left derived functors byAdditivity ensures that preserves zero maps, sums of maps and homotopy identities, so the transformed differentials still compose to zero.
For a module homomorphism , lift it to a chain map between chosen projective resolutions. In degree zero, lift through using projectivity of . In each higher degree, the already constructed map lands in the next kernel; exactness of and projectivity of supply the next lift. Any two lifts are chain homotopic: their degree-zero difference lands in , so it lifts to . Inductively lift the remaining difference after subtracting the preceding homotopy term. This givesApplying preserves this identity, so the lifts induce the same homology map. Identity lifts and composable lifts show that is a functor. Comparison lifts between two resolutions over the identity of are inverse up to chain homotopy; hence the construction is independent of the chosen resolution up to its canonical natural isomorphism.
Right exactness identifies naturally with . For a projective module , the length-zero resolution gives for . For a short exact sequence , the horseshoe lemma builds a degreewise split short exact sequence of projective resolutions. Concretely, lift the projective generators covering into and combine them with generators covering ; repeat on the kernels. The middle projective term in each degree is the direct sum of the two outer ones. An additive functor preserves these split sequences, and lifting cycles, taking their differentials and returning to the subcomplex produces the connecting maps inThis is the natural long exact derived-functor sequence. In particular, if has projective, then for , and . These are dimension-shifting formulas. Positive degrees can be killed by the surjection . If is exact, it preserves every resolution's exactness and all its positive left derived functors vanish. Conversely, if vanishes on all modules, the displayed long exact sequence makes exact. A natural transformation between additive right-exact functors induces transformations on the left derived functors by applying it termwise.
For extension of scalars , these derived functors are the Tor functors . When and is a non-zero-divisor, there is the length-one free resolutionAlthough the construction above resolves , one may instead use this resolution of . To justify that calculation, tensor a free resolution of with the two-term resolution of to form a double complex. Taking homology first along the resolution of leaves ; taking it first along the resolution of leaves . The free terms preserve exactness under tensoring. The double complex is first-quadrant with finitely many terms on each total diagonal, so both filtrations compute the same total homology. This proves the required balancing directly.
The kernel and cokernel of multiplication by now give Tor for a principal non-zero-divisor quotient:These are naturally -modules. For , the degree-one group is zero; for , multiplication by is zero and both degrees zero and one are . Thus, when , degree one explicitly detects the failure of this base-change functor to be exact.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
An algebraic line bundle over is an invertible module: a finitely generated projective module such that for every prime ideal . Define the Picard group of a ring as the set of its isomorphism classes, withThe tensor product of modules of two finite projective modules is finite projective: write each as a direct summand of a finite free module and tensor the two decompositions. Localization gives , so this multiplication stays within the set of invertible modules. It is well defined on isomorphism classes. The associativity and symmetry isomorphisms of the tensor product give associativity and commutativity, and is the identity.
Let be the dual module. A finite direct-summand presentation shows that is finite projective and that localization commutes with this dual. Since is free of rank one, so is . The evaluation homomorphismis an isomorphism after every prime localization. Its kernel and cokernel are therefore zero, by exactness of localization and localization detects zero elements for modules. Thus , proving that is an abelian group.
For a ring homomorphism , tensoring a split presentation gives , so is finite projective. For put . Every element of becomes a unit in , andThis proves base change of invertible modules. Moreover, the canonical mapis an isomorphism, with inverse . It shows that is a group homomorphism. Identity maps induce the identity, and for , the associativity isomorphism proves composition compatibility. Therefore is a covariant functor to abelian groups.
The polynomial ring is a principal ideal domain by division with remainder. A submodule of a finite free module over a principal ideal domain is free: induct on the ambient rank, project onto the first coordinate, and note that the image is a principal ideal, hence either zero or a free rank-one module. This gives a split exact sequence with that image as quotient; the kernel lies in a free module of one smaller rank, completing the induction. A finite projective module is such a submodule, and so is free. An invertible module has rank one after passing to the fraction field, so its free rank is exactly one. Hence every algebraic line bundle over is trivial and
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A Noetherian module satisfies the ascending chain condition on its submodules; equivalently every submodule is a finitely generated module. If the latter condition holds, the union of an ascending chain has a finite generating set lying in one member, so the chain stabilizes. Conversely, a submodule with no finite generating set allows successive choices outside the submodule generated so far, producing a strictly ascending chain. A Noetherian ring is a ring that is Noetherian as a module over itself, equivalently one whose ideals are all finitely generated.
The formal power series ring consists of sequences written , with coefficientwise addition and the Cauchy product:Every coefficient uses a finite sum; no analytic convergence is involved. Evaluation at zero gives . A quotient ring of a Noetherian ring is Noetherian, because its ascending chains of ideals lift to such chains upstairs. Thus one direction of Noetherianity of a formal power series ring is immediate.
For the other direction suppose is Noetherian, and let be an ideal. Define the coefficient ideals of a formal power series idealEach is an ideal, and multiplication by gives . Choose with . For , choose generators for , and choose series whose coefficients are those generators. Empty generating sets are allowed for zero ideals.
These finitely many series generate . To prove this without assuming that is closed, start with and cancel its coefficients successively. If the residual lies in , its coefficient lies in . Put ; since when , write that coefficient as and subtract . The new residual belongs to .
For , the generators are used only at the single step . For , their accumulated multipliers are the genuine formal power series . Thus the construction yields the exact coefficientwise identityEvery coefficient of the residual vanishes after finitely many steps. This is an ordinary finite generating expression in , not merely an approximation by elements of a smaller ideal. Therefore every ideal is finitely generated, provingFinally, for the surjective module endomorphism , the kernels stabilize because is a Noetherian module. Take with . If , surjectivity of gives with . Then , so and . Hence is injective as well as surjective; its inverse is automatically -linear. This proves is an isomorphism, the statement that Noetherian modules are Hopfian.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be a multiplicative subset, containing one and closed under products. On , useThe relation is reflexive and symmetric. For transitivity, if and , then multiplication and addition give . Thus it is an equivalence relation. Write for the equivalence class. The localization of a ring has operationsThey are well defined. For example, replacing by in its sum with gives cross-numerator difference , and in its product with gives . The same annihilating element kills both differences. Replacing the other input works identically. Associativity and distributivity then follow by putting all terms over the product of their denominators and using the ring identities in . Addition and multiplication are commutative, with identities and , and the displayed negative is an additive inverse. Hence is a commutative ring. If , the fraction relation identifies all elements, producing the zero ring.
The canonical ring homomorphism , , makes each a unit, with inverse . The universal property of localization states that any ring homomorphism sending into the units factors uniquely through . Define the factor byIf , then is invertible, so , proving well-definedness. The fraction operations prove that is a ring homomorphism. Its value is forced by , so it is unique. This property characterizes the localization up to a unique compatible isomorphism.
For a prime ideal , its complement is a multiplicative subset, and the localization at a prime ideal is . Fractions with numerator outside are units; those with numerator in form the unique maximal ideal . Thus it is a local ring.
For the nilpotent question, suppose and . Its annihilator is a proper ideal, so it lies in some maximal ideal . The fraction criterion says in only if for some , which is impossible by the choice of . Thus is a nonzero nilpotent element in that localization. This proves reducedness is detected by prime localizations: if every prime localization is reduced, has no nonzero nilpotent elements.
For the domain question take with a field. Its only prime ideals are and : a prime ideal must contain one of the orthogonal idempotents , and the corresponding quotient is . Localizing at makes invertible and kills , giving ; similarly . But with both factors nonzero. Therefore domain prime localizations do not force to be an integral domain, as expressed by domain prime localizations do not imply a domain.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 3 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Throughout, rings are commutative with identity and ring homomorphisms preserve identity. The spectrum of a commutative ring is . For an ideal , put ; these are the closed sets of the Zariski topology. Its axioms follow fromFor the last equality, a prime ideal containing must contain or : if it contained neither, choose and , contradicting . The other equalities follow directly from containment. Thus arbitrary intersections and finite unions of closed sets are closed, proving that this is a topology.
The Zorn lemma says that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. For , apply it to proper ideals ordered by inclusion. The zero ideal is proper. The union of a nonempty chain is an ideal and is proper, because containing one would put one in a member of the chain; the empty chain has the zero ideal as an upper bound. There is therefore a maximal ideal . If , then , so the class of in is invertible. This quotient ring is a field, making a prime ideal. Hence .
For a ring homomorphism , define by . The inverse image is proper because , and primality follows from . Moreoverwhere is the ideal generated by . This proves continuity. Inverse images also give and . Thus is a contravariant functor from rings to topological spaces.
For the specified inclusion, the fundamental theorem of algebra gives the points and of . Over , the nonzero prime ideals are generated either by with , or by with , ; all irreducible real polynomials have degree one or two. Contraction gives the spectrum map for the complexification of a real polynomial ring:Indeed, a real polynomial vanishing at a nonreal also vanishes at , and is divisible by their quadratic factor; the converse is immediate. This map is surjective. Its fibers contain one point over a real linear factor, two conjugate points over an irreducible quadratic factor, and only the generic point over zero. It identifies complex-conjugate pairs. Since each proper Zariski-closed set in either one-variable polynomial ring is a finite set of closed points, images of closed sets are closed; hence the Zariski topology on the target is the quotient topology for this identification.
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





