Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 34 4 Solution Created 2026-10-03 Updated 2026-10-14
Only active routes, those with , enter the proportional fairness inequality and the weighted logarithmic utility. Their rates must be positive; inactive routes have no per-flow rate to determine and may be assigned zero. This convention removes otherwise meaningless terms and .
For positive active rates, concavity of the logarithm gives, for any positive feasible competitor ,Thus the proportional fairness inequality proves that maximizes the log-utility objective. A competitor with an active zero rate has utility and cannot improve it. Conversely, if maximizes utility, the right directional derivative along at is nonpositive, giving exactly that inequality. Positive resource capacities and finitely many active routes allow a feasible allocation with every active rate positive, so an optimizer cannot have an active zero rate. Strict concavity gives uniqueness of the active rates. Hence proportional fairness is equivalent to the stated log-utility maximization.
Index the four adjacent-pair routes in cyclic order and put , the aggregate service on route . The resource constraints areThey involve every odd-even route pair, so they are equivalent toFor given maxima, increasing each active odd service to and each active even service to remains feasible and improves utility. Apart from the constant , the objective therefore reduces toWhen both groups are present the constraint is tight, and differentiation gives . If one group is empty, the other receives unit aggregate service on each of its active routes. Thus the opposite-route reduction for a proportionally fair four-cycle yields, with ,Inactive rates can be set to zero, including every rate in the empty state. In particular whenever that route is active. This proves the required formula even when other routes are empty.
For the flow-level network model, an active document's residual size retains an exponential distribution with parameter . Receiving service at rate gives completion intensity , so independent active documents give total completion intensity . Consequently the population continuous-time Markov chain hasAll death intensities are zero at . Their total is bounded by , and the total arrival rate is constant, proving nonexplosion.
Put . The required stationary weight uses a binomial coefficient, as printed in the PDF; the converted TeX incorrectly rendered it as an ordinary fraction. DefineFor an odd route, the neighboring binomial coefficient ratio iswhile its death intensity at the neighboring state is . Their product is , so . For an even route, replace by in the same calculation. This proves detailed balance and the stationary law of a proportionally fair four-cycle:A finite is essential for this expression to be a probability distribution. We determine its exact convergence condition rather than asserting stationarity for arbitrary arrival rates. LetGrouping the states by odd and even population givesWith and , the bounds and show that convergence holds exactly when . For necessity, the lower bound sums to , which diverges at or above one. For sufficiency, choose slightly larger with ; the polynomial factors are absorbed into constants times , giving a convergent geometric generating series. Thus the stability region for the reversible four-cycle flow network isEquivalently, the offered load on each resource, , , , or , is strictly below its unit capacity. For positive arrival rates this finite normalizing constant gives the unique stationary distribution of the irreducible process. At or beyond the boundary, the displayed invariant weights are not summable and do not define a stationary probability law.
If an explicit normalizing constant is desired, for , and . Hence for , in the stable region,Equal-parameter cases are obtained by continuity or directly from the positive series. In particular the empty-traffic limit is .
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 34 3 Solution Created 2026-10-03 Updated 2026-10-14
Use finite sets of links , source-sink pairs , and admissible routes , with at least one route for each pair. Route carries aggregate flow . The link-route incidence matrix has if route uses link and zero otherwise; repeated traversals, if allowed, are counted with their multiplicity. The source-sink route incidence matrix has if serves pair . Thus gives link throughputs and gives source-sink demands. Write for the routes serving andA Wardrop equilibrium routes positive flow only on minimum-delay routes:This is a nonatomic equilibrium: an individual infinitesimal user's route change does not alter the aggregate link delays.
For fixed nonnegative demand , the feasible route-flow set is a nonempty product of finite-dimensional simplexes and hence a compact set. The Beckmann potentialis continuous, so it attains a minimum over this feasible set. Each primitive is a strictly convex function, since its derivative is continuous and strictly increasing. Its route-flow derivative is exactly the corresponding route delay:If a minimizer had positive flow on and a lower-delay alternative , transferring a small amount from to would give directional derivative , contradicting minimality. Hence every minimizer is a Wardrop equilibrium.
Conversely, let be a Wardrop equilibrium and any feasible competitor. Convexity givesFor each , subtract inside this sum. The demand constraint makes , and the remaining terms are nonnegative: used routes have , while unused routes have , and . Thus . We have proved both existence and the optimization characterization.
Strict convexity in the link vector makes unique: two different minimizing link vectors would have a feasible midpoint of strictly smaller potential. Thus link delays and the minimum route delays at the Wardrop equilibrium are also unique. The route vector need not be unique, because different route decompositions may have the same and . For example, two successive stages with two parallel links at each stage have four routes. With unit demand and link delay , the vectorsall give throughput on each of the four links and delay one on every route. This exhibits route-flow nonuniqueness at a Wardrop equilibrium. The equilibrium link throughputs are unique; the individual route flows need not be.
For elastic demand, make the usual physical assumptions explicit: delays are nonnegative on , every route is nonempty, and is finite, continuous and strictly decreasing. PutThe limit exists by monotonicity; it need not be zero. The inverse demand function is continuous, strictly decreasing, satisfies , and tends to infinity as .
Choose any reference and use elastic-demand utility with an interior reference:Each utility is strictly concave, with derivative . A reference inside the range avoids a potentially divergent integral from zero. For instance, has inverse , whose integral from zero is infinite, although the displayed reference-point primitive is finite at every interior demand.
Give its limiting value at , which may be , and extend it by outside . This encodes the physical demand range in the objective. After substituting , , minimizeIts effective feasible set is contained in , a nonempty compact set. The objective is lower semicontinuous, including a possible value at a lower endpoint, and is finite when all demands equal their interior reference values. It therefore has a finite-valued minimizer.
The boundary exclusion for elastic Wardrop demand shows that every minimizing demand is interior. If and the utility there is finite, adding a small flow on any route serving costs at most a bounded constant times , while the utility gain is at least , whose ratio to tends to infinity. This decreases the objective. If that endpoint utility is , a finite minimizer cannot occur there in the first place. At , choose a used route. Its delay is strictly positive, since its nonempty links have positive throughput and strictly increasing nonnegative delays. Removing a small amount of its flow saves a positive first-order cost, whereas the utility loss is because . This also decreases the objective. Hence for every pair.
The interior-demand route derivatives are nowAt a minimizer they are zero on positive route flows and nonnegative on zero route flows, by increasing or decreasing a single route flow. Since , some route is used, soThese are precisely the elastic-demand Wardrop equilibrium conditions. Conversely, those conditions give the same nonnegative directional derivative for every competitor; convexity then proves global minimality. The equivalent constrained form is the requested minimization of with , , . Strict convexity determines both and uniquely, while their route decomposition can still be nonunique.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 34 2 Solution Created 2026-10-03 Updated 2026-10-14
For a standard loss network, let type- calls arrive as independent external Poisson processes of rates . Each accepted call holds units of resource for a holding time with an independent exponential distribution of parameter , then releases them. Capacities and requirements are nonnegative integers. Rejected calls leave immediately and do not queue. With fixed routes, the feasible count set isFor a call of each type using at least one finite-capacity resource, this set is finite. The count continuous-time Markov chain has accepted birth rate and death rate . Put andOn every admitted edge, , so . This proves detailed balance and the product-form stationary distribution of a loss network:It is unique when all relevant arrival rates are positive, since departures lead to zero and every feasible state can be built from zero through feasible births.
An external Poisson process arrival sees this stationary prearrival law by Poisson arrivals see time averages. Indeed its constant conditional arrival rate makes the expected count of arrivals in any state set equal to times the time spent there. A type- arrival is accepted exactly in , where is its resource column. Thus the blocking partition ratio for a loss network isSet to zero when reduced capacities have an empty feasible set.
For the triangle, index call types by their endpoint pairs and give physical links integer capacities . We assume each call needs one circuit on every traversed link; arrivals of the three types are independent Poisson processes, and holding times have independent exponential distributions with parameters determined by endpoints alone. Calls may be rearranged instantaneously and without cost among their direct and two-link paths, without restarting or changing their holding times. Admit a call if any simultaneous arrangement of all calls is feasible. These assumptions make the three type counts Markovian even though the physical route assignments may change.
The cut feasibility for a rearrangeable triangle gives the exact feasible count set. Define virtual endpoint capacitiesEvery endpoint call must use at least one of the two links incident to that endpoint, so feasibility requiresThese cut inequalities are also sufficient. If each count fits its direct-link capacity, route every call directly. Otherwise at most one count exceeds its own direct capacity: two excesses would violate the cut inequality at their shared endpoint. If, for example, , route such calls directly and the excess through node three. The other link usages are and , and the first two cut inequalities bound them by and . The other cases are cyclic permutations. Thus the count process is exactly a virtual fixed routing loss network in which a pair call consumes one unit of each endpoint resource.
WriteThe exact stationary distribution count probabilities are these weights divided by . The three arriving-call blocking probabilities are thereforeEquivalently, a type- call is blocked on the union of the events and , with the other pairs treated cyclically. The partition ratios count their union without double-counting intersections. These expressions are exact for the stated rearrangeable triangular loss network; a restricted rearrangement policy would require a different admission model.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 34 1 Solution Created 2026-10-03 Updated 2026-10-14
Use finitely many colonies and let be the population of colony . An open migration process has independent external Poisson processes of rates , local total departure rates , and fixed routing probabilities to other colonies and out of the system. Here , for , and . The continuous-time Markov chain has intensitiesRequire the routing matrix to be transient: every individual eventually exits. For finitely many colonies this is equivalent to every colony having a directed path to an exit. Restrict to colonies reachable from external arrivals, so their traffic rates are positive and the relevant chain is irreducible. The total population cannot exceed its initial value plus the number of external arrivals, so on any finite time interval it is bounded by a finite random number. There are only finitely many states below that bound and finite rates in each, proving nonexplosion even when the departure functions grow rapidly.
The traffic equations of an open migration process, in row-vector form, areTransience makes the inverse finite. DefineProvided every is finite, the candidate product-form stationary distribution of an open migration process isThe normalizability condition is exactly for every active colony. For example, constant total service for requires and gives a geometric distribution; independent individual departures give a Poisson distribution of mean . In the irreducible case the normalizable invariant law is the unique equilibrium. If the weights cannot be normalized, no stationary probability law exists, by uniqueness up to scale of invariant measures for an irreducible recurrent chain.
We establish both stationarity and the time reversal of an open migration process assertion by adjacent-weight calculations. DefineThe identity givesThus the proposed time reversal of an open migration process retains the local service functions and hasThe traffic equation for colony implies . Summing all traffic equations also gives . Therefore the total outgoing rate from every state is the same for and :Consequently , proving global balance for a continuous-time Markov chain. The same weight recurrence gives , so the stationary mean total jump rate is finite. The candidate is a stationary distribution, and the displayed intensities are indeed its stationary time reversal of a continuous-time Markov chain. Reverse routing is also open: reverse an original arrival-to-colony path to obtain a path to a colony with .
For the last request, let be all colonies reachable by routing from , including itself. The no-return-path hypothesis gives . By construction no routing edge leads from to its complement . The populations in therefore evolve autonomously as an open migration process, with moves into treated as exits. Its stationary marginal is the corresponding product of the factors above. Retain the original destination as a mark on each such exit.
In this autonomous process, a marked exit has intensity . The same reversed-weight calculation makes its reverse a marked external immigration channel of constant rate . External immigration channels can be constructed as independent Poisson processes. Stationary reversal of a two-sided Poisson process preserves its law, so reversing this immigration channel givesThis Poisson migration stream without a return path argument is needed because a general internal migration stream in a network with feedback is not automatically Poisson. A zero routing probability gives the empty Poisson stream of rate zero.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 33 4 Solution Created 2026-10-03 Updated 2026-10-14
Let be the bit string with one in position and zero elsewhere, and use the standard convention . On the computational basis, the single-site Pauli operators act asThe identity leaves the basis state unchanged. A tensor-product Pauli operator applies these actions at each occupied site; operators at different sites commute. Their linear span is the full operator algebra, so correcting their span handles coherent combinations as well as random Pauli errors.
Let project onto the code , with orthonormal logical basis . A set is correctable exactly when the Knill--Laflamme condition holds:for a matrix independent of the logical indices. A set is detectable whenThese conditions extend by linearity to the corresponding operator spans. Detection allows an error to act as a harmless scalar on the code; it need not assign a distinct syndrome to such an error.
For distinct Pauli representatives modulo phase, a nondegenerate quantum error-correcting code has orthogonal error-image subspaces, giving because each Pauli is unitary. In the usual nondegenerate, or pure, detection convention, every nonidentity detectable Pauli has , while . More generally a nonsingular error-overlap matrix can be diagonalized and the resulting error operators rescaled to obtain orthogonal syndrome spaces; a singular overlap matrix expresses degeneracy of the specified independent error family.
For an code, the quantum code distance is the smallest Pauli weight for which scalar compression fails. Hence every Pauli of weight at most is detectable. If each have weight at most , their product has weight at most . When , its compression is scalar, so the Knill--Laflamme condition proves simultaneous correction of all such errors. ThereforeThe integer part is understood when the printed half-distance is not an integer. Arbitrary operators on such subsets are covered by their Pauli expansion.
For errors confined to a known set of positions, every pairwise product is still supported on that same set and has weight at most , rather than . Thus supplies quantum erasure correction, with maximum guaranteed numberThis guarantee cannot hold for every set of positions: a minimum-weight undetectable Pauli has support in such a set, and the pair consisting of it and the identity violates the Knill--Laflamme condition. Particular larger location sets can sometimes be correctable; is the maximum uniform guarantee over all possible known sets.
For the Shor code, write . The logical codewords are and . A phase flip in one block interchanges and in that block, independently of its position within the block. Let , , . Measure the two commuting stabilizer generators and . Both are on the entire logical code space. The Shor-code phase-flip syndrome isThese parity measurements reveal the erroneous block without revealing the logical amplitudes, so they preserve arbitrary superpositions of the two codewords. Applying the listed representative phase flip restores the state.
For any two physical positions in the same block, acts as on both and , and hence on the code. Therefore and even when . Their error spaces coincide, and the error-overlap matrix has a nonzero off-diagonal entry. The correction is degenerate because different within-block phase errors have exactly the same action on every logical state.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 33 2 Solution Created 2026-10-03 Updated 2026-10-14
A linear map is a completely positive map if sends every positive operator to a positive operator for every finite-dimensional auxiliary system . Positivity of alone tests only inputs without an auxiliary system and is weaker.
For the Kraus representation, let be any operator on the auxiliary system and the input system. ThenFor any vector , its expectation is . Every amplification is therefore positive, proving the Kraus-form map is completely positive. No normalization condition on the is needed for this positivity proof. To make it a deterministic quantum channel, one additionally requires ; a physical outcome branch instead obeys .
Transposition is positive on one system: for any positive and any , is the complex conjugate of , hence is real and nonnegative. It fails complete positivity already for a qubit. Apply partial transposition to the second subsystem of the Bell state . The resulting operator isOn the antisymmetric vector , its eigenvalue is . Thus the partial transpose is not positive on this entangled input, andThe same witness embeds into any larger input dimension; in the exceptional one-dimensional case transposition is simply the identity.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 33 1 Solution Created 2026-10-03 Updated 2026-10-14
The Bloch vector representation of a qubit density matrix is , where and . Pure states have , while the origin represents the maximally mixed state , not a pure state.
For the two preparations, direct evaluation of the Pauli matrices givesTheir dot product is , so their Bloch vectors meet at angle , or degrees. This is the angle between Bloch vectors; the angle determined by the modulus of the Hilbert-space overlap is different.
Completeness of the POVM requires . In the computational basis, subtraction givesAn overall phase of is immaterial. The matrix has eigenvalues and zero, so it is positive; together with it is a valid trine qubit POVM.
The Born rule gives . The conditional probabilities areOutcome one identifies , since is orthogonal to ; outcome two identifies , since is orthogonal to . Outcome three is inconclusive. If Alice's prior probability for is , the unconditional outcome probabilities are , , and respectively. Because outcome three has the same likelihood for both preparations, it leaves the prior odds unchanged. Bob's conclusive identification succeeds with probability one half and is never wrong; he does not identify the state on the inconclusive trials. This is unambiguous quantum state discrimination.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 32 5 Solution Created 2026-10-03 Updated 2026-10-14
The exit time is finite almost surely. Indeed, if the Brownian motion is still in at an integer time, its next unit increment exceeds with a fixed probability independent of the past; on this event it must exit before the next integer time. Consequently . Path continuity gives , and the two exit events partition the probability space up to null sets.
For each real , the exponential Brownian martingale has expectation one. This follows directly from the moment-generating function of a normal distribution and independent increments. At its value is bounded by . Bounded-time optional stopping and then dominated convergence therefore giveWrite and . Applying the identity to and yieldsFor , multiply the first equation by , the second by , and subtract. Solving the resulting system givesAdding and using the sum formula for the hyperbolic sine gives the asymmetric Brownian interval-exit transform:At , the printed sine ratio is and needs its removable extension. Dominated convergence as givesThus the formulas hold for every real parameter with this endpoint convention. The expectation on the left of the first formula is legible in the original PDF; the converted TeX's nested exponential is an OCR error.
There are unlisted articles, also show them or only show them.