Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 4 b Solution Created 2026-10-03 Updated 2026-10-06
The symmetric group has elements, not the printed order . For the identity and the adjacent transpositions have probabilities , so the specified transition matrix is normalized. Its stationary distribution is uniform and it satisfies detailed balance, since each transposition is its own inverse. Adjacent transpositions generate the symmetric group, making this an irreducible Markov chain; the positive holding probability makes it an aperiodic Markov chain.
For a fixed label , right multiplication swaps positions, so is the label's position. Under the uniform distribution on a finite set it is uniform on . ThereforeFor each generator , the squared change is one if the label occupies either of the two positions, and zero otherwise. Its stationary expected value is , givingThus the tagged-label Rayleigh quotient for adjacent transpositions gives the corrected bound
The printed factor six cannot be obtained: the hint's variance of a uniform distribution is wrong. Directly, . Bounded convergence in distribution of does imply convergence of its first two moments, hence convergence of its variance, but the limit is .
More strongly, the claimed asymptotic bound itself is false for this kernel. The Aldous spectral gap theorem states that the interchange process on a finite connected weighted graph has the same spectral gap as the single-label random walk with identical edge rates; see Theorem 1.1 and its proof. Here is that interchange process generator on a path graph with edge rates . For the tagged-label generator, direct substitution of gives eigenvalues , , including the reflecting endpoint equations. These distinct eigenvalues exhaust the tagged-label function space. Consequently the theorem yieldswhich exceeds asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 4 b Solution Created 2026-10-03 Updated 2026-10-06
A counterexample can use an irreducible, aperiodic reversible Markov chain, so failure is not caused by a pathological transition structure. Take two binary coordinates, enumerate the four states as , and let be their uniform distribution. Use the Markov kernelIts rows sum to one and it is symmetric, proving detailed balance with . Every entry is positive. Let the univariate parametric family be .
For a product initial probability distribution with parameters , additivity of the Kullback-Leibler divergence givesEach summand has derivative on , so the unique optimum at has . ThusOn the other hand the allowed initial probability distribution , obtained with , is sent by one step to . Its Kullback-Leibler divergence is zero, the smallest possible value. ConsequentlyThe transition reduces Kullback-Leibler divergence for each input, but may reduce it by different amounts for different inputs. It therefore need not preserve the ordering of competing initial probability distributions, which is exactly why Markov chain variational inference must optimize the initial parameters for its chosen number of steps.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 4 c Solution Created 2026-10-03 Updated 2026-10-06
Parameterize the initial product normal distribution by , usingRun the given recursion with independent random variables with uniform distributions to obtain . Because the noise laws do not depend on , the chain rule and automatic differentiation give reparameterization gradients through the entire simulated trajectory. The variational objective is , where and .
One must account for the output differential entropy, not just optimize . Simulation and differentiability of do not themselves supply an evaluable . If retains the reversible Markov chain assumption from part (b), a concrete algorithm avoids a transition-density oracle using reversible density-ratio propagation. Write , with an evaluable unnormalized posterior density, and defineDetailed balance impliesFor example, integrate and replace by to obtain the first identity. This also proves absolute continuity of measures of with respect to when . An everywhere finite differentiable log-posterior has positive density, so an ordinary product normal distribution has this domination.
For each outer sample , independently run trajectories of length starting at , with endpoints . These are reverse trajectories because of detailed balance; the same recursion simulates them. Estimate byAverage over an outer batch. Compute it stably by a logarithmic sum of exponentials. Differentiate through both outer and reverse trajectories and through the explicit product-normal probability density function . Only the given state gradients of and , together with elementary normal-density derivatives, are needed. Apply stochastic gradient descent to and , refreshing the independent noise batches. The logarithmic scale parameters keep all variances positive.
This is nested Monte Carlo optimization of the exact objective in the limit of adequately increasing inner and outer sample sizes. For fixed , is generally biased, even though is an unbiased estimator. Finite logarithmic moments, suitable uniform integrability, and justified differentiation under the integral sign are needed for consistency and gradient interchange. Under those conditions increasing and controlling the optimization error yields a justified numerical approximation; nonconvexity prevents a generic guarantee of a global optimum.
There is a real assumption issue: part (c) redefines without explicitly restating reversibility. The algorithm above uses the reversible interpretation inherited from part (b). For an arbitrary differentiable recursion, one additionally needs access to output densities or a simulatable reverse kernel and regularity of the objective. Differentiability alone is insufficient: is differentiable and, with a standard-normal target, makes a point mass for , so every candidate has infinite Kullback-Leibler divergence. Thus a universal finite-objective algorithm cannot be justified solely from the literal differentiability assumptions. An invertible recursion with computable density transformations offers a different sufficient route, but invertibility is not stated here.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 5 b Solution Created 2026-10-03 Updated 2026-10-06
Let and . With conditional independence of the binary observations given the latent function, defineThe prior distribution is specified on the precision , not on . Its Jacobian determinant givesand the marginal posterior density is proportional to . Working instead with precision or logarithmic coordinates is possible, provided all corresponding Jacobian determinants are included.
Choose an importance sampling density covering the support of , draw independently from it, and use the nonnegative unbiased likelihood estimatorEach summand integrates to , proving unbiasedness. A simple always-valid choice is the latent Gaussian prior distribution, , when the covariance matrix is nonsingular. Then the estimator is just the average of the bounded values . For duplicate inputs, sample only the distinct latent values and multiply all likelihood contributions at each common input. A Gaussian approximation to the latent posterior distribution, or its mixture with the Gaussian prior distribution, can reduce relative variance while keeping complete support. Its approximation does not replace the exact weights.
The pseudo-marginal Metropolis–Hastings algorithm stores both the current and its estimator randomness ; write their sampling law as . Propose , independently generate , compute , and accept the pair withHere denotes the proposal probability density function from to . On rejection retain both the old parameter and the old likelihood estimate. Initialize with a positive estimate. One must not independently refresh the denominator after rejection.
Correctness follows from the extended posterior densityThe pair proposal is . Its Metropolis–Hastings acceptance probability simplifies to the displayed ratio, since the auxiliary densities cancel. Hence detailed balance holds for . Integrating over gives by unbiasedness, so the parameter marginal distribution is exactly the intended posterior distribution for any fixed positive . This is exactness of the stationary target, not independent exact samples or a guarantee of rapid convergence. Large relative variance of the likelihood estimates can produce long holding times, so marginalizing does not by itself guarantee an improvement in mixing time.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 6 Solution Created 2026-10-03 Updated 2026-10-06
Use the extended target probability density functionThe desired stationary distribution for positions is ; the full position-momentum joint probability distribution is , not alone. Gaussian momentum refreshment preserves , since it redraws its momentum marginal distribution independently while keeping the position fixed.
Let and be the surrogate leapfrog integration map. The proposal in the paper is : its notation includes the final momentum flip. Reversibility gives , so . Both and preserve volume. Thus is an involutive Metropolis proposal, and the required acceptance probability isEquivalently, in terms of the surrogate Hamiltonian ,Only evaluations of the true target probability density function are needed at endpoints; the trajectory uses the surrogate gradient. Target and surrogate normalizing constants cancel.
For , the accepted flux satisfiesChanging variables has unit absolute Jacobian determinant, so this identity proves detailed balance for accepted moves. The rejection mass stays at the same point and is also reversible. The accept/reject step therefore preserves . Since momentum refreshment also preserves , their composition and either phase of the alternating process preserve . Projecting onto positions proves the position stationary distribution is exactly the original target. Stationarity alone does not establish uniqueness or convergence from every start; those require additional irreducible Markov chain and aperiodic Markov chain hypotheses.
There is a genuine defect in the printed smoothing claim. For the positive, nondifferentiable Laplace distribution on the real line, direct minimization gives, for every ,For the minimizer is ; for it is ; at zero both signs minimize. Hence normalization leaves , still nondifferentiable at zero. The displayed construction does not in general produce the asserted smooth surrogate. For example, the also nondifferentiable target makes that infimum for every , since the negative quartic term dominates the quadratic penalty. The invariance proof above is valid conditional on actually having a usable smooth surrogate, as the subsequent algorithm assumes.
A corrected sufficient construction is Moreau smoothing of a negative log-density. For a proper convex function with sequential lower semicontinuity , setThe Moreau envelope is differentiable, with ; require to be integrable to normalize it. The signs differ from the printed formula. For the Laplace distribution, this givesa genuinely differentiable potential with integrable exponential tails. Using that surrogate with the boxed acceptance probability still targets the original Laplace distribution.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 344 1 a Solution Created 2026-10-03 Updated 2026-10-06
Let be a coarse-grained configuration, with restricted partition function and free energy . Its Boltzmann distribution is . Microscopic reversibility pairs every equilibrium microscopic history with a history read backwards, including reversal of all time-odd variables. Summing this identity over the microscopic histories representing a given coarse-grained path preserves it; a Markov assumption is not needed for this argument.
Write for the probability density of a specified history conditional on its starting configuration , and for its physically reversed history conditional on starting at , where reverses time-odd variables. Equilibrium time-reversal symmetry givesSince , the desired conditional path relation isFor a reversible Markov chain, this also follows by multiplying detailed balance ratios along the history: the intermediate equilibrium weights telescope.
The conditioning is essential. If the starting equilibrium weights are included in the path probabilities, the forward and reversed probabilities are equal, rather than differing by the displayed exponential. For example, a two-state continuous-time Markov chain with , , rates and has equal equilibrium-weighted probabilities for the two reversed single-jump histories. Their conditional rate ratio is instead . Normalized bridges conditioned on both endpoints also have a different normalization from the path weights used above. The PDF prints in the denominator while its explanatory text defines ; the latter is the intended notation. For the scalar order parameter used subsequently, .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 344 1 b Solution Created 2026-10-03 Updated 2026-10-06
Here is a kinetic coefficient, and the additive Gaussian white noise must be centered. A rigorous starting point is a finite spatial discretization or finite set of modes of the coarse-grained field. For each field coordinate, the Fokker-Planck probability current has the continuum notationThe equilibrium Boltzmann distribution has . Detailed balance for this time-even field requires zero configuration-space current. ThereforeThis is the Model A fluctuation-dissipation relation. Conversely, that noise strength makes the equilibrium current vanish and gives reversible relaxational dynamics when the equilibrium measure is normalizable.
Alternatively, the Onsager--Machlup path probability for Model A dynamics compares the squared required noise histories and . Their difference gives , using the functional chain rule. The midpoint convention and time-reversal invariance of a path Jacobian justify cancellation of the common Jacobian. Comparing with the conditional path ratio gives the same result. The spatial white-noise continuum is a coarse-grained idealization: retain a microscopic cutoff when pointwise fluctuations or ultraviolet divergences matter.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 26K a Solution Created 2026-09-24 Updated 2026-10-05
An M-M-1 queue has a Poisson arrival process of rate , independent exponential service times of rate , and one server, with an unlimited waiting room and the usual first-come-first-served discipline. Its number-in-system process is a continuous-time birth-death chain with and for . For , detailed balance givesThis sums to one and satisfies . The nonexplosive irreducible chain therefore has an invariant probability and is positive recurrent. Equivalently its negative drift above zero gives finite mean return cycles. Here queue length includes the customer in service.
In equilibrium, PASTA gives an arriving customer's number of predecessors the distribution . Conditional on predecessors, memoryless property makes its total waiting-plus-service time a sum of independent variables. Its Laplace transform isThereforeThis is the sojourn time including service, not just the time until service begins.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 26K b Solution Created 2026-09-24 Updated 2026-10-05
For the M-M-1 queue with Bernoulli feedback, assume . The number of service visits before departure is geometric on , with probabilities , independent of the independent exponential visit lengths. The transform of the total time actually being served isThusThis excludes the waiting between visits. A feedback completion changes the customer's position but not the number in the system. By exponential memoryless property, the latter process has births of rate and true deaths of rate while nonempty; unsuccessful completions are self-events. It is therefore an M/M/1 number process with effective service rate , givingFor positive equality is null recurrent, larger arrival rate is unstable, and admits no departure-based equilibrium.
To prove the output claim, state the relevant time reversal of a continuous-time Markov chain theorem: an equilibrium continuous-time chain satisfying detailed balance has the same reversed path law. In this reversible birth-death process, final departures are precisely downward jumps; time reversal turns them into upward jumps. Upward jumps are supplied by a state-independent Poisson clock of rate , so their process is Poisson. Hence the stationary final-departure process is Poisson of rate . This is the output conclusion of Burke theorem for the effective number process; it does not say the process of all service completions has that rate.
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 4 9H b Solution Created 2026-09-24 Updated 2026-10-03
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 213 1 i Solution Created 2026-10-03 Updated 2026-10-05
A loss network models calls that require several resources simultaneously and are rejected if any required capacity is unavailable; rejected calls do not queue. For fixed routing, let be the number of units of resource used by a call of type , and let be its capacity. Independent Poisson processes supply type- calls at rate , with independent holding times having an exponential distribution of mean . Write for the offered traffic, andAssume finitely many resources and call types, with every call using a resource, so this set is finite. The occupancy continuous-time Markov chain has ratesIts stationary distribution isIndeed, for each feasible upward transition,which is detailed balance for a continuous-time Markov chain. Thus this is a reversible Markov chain. With positive arrival rates it is irreducible on : departures reach the empty state, and any feasible state can be assembled by arrivals. Its stationary distribution is consequently unique.
The formula is a product-form stationary distribution of a loss network: equivalently, independent Poisson random variables of means conditioned on . The conditioning couples the occupancies, so the resources are generally not independent. By Poisson arrivals see time averages, the acceptance probability for a type- arrival isbecause the prearrival state must leave free units at each resource. Set the numerator to zero if its capacity vector has a negative entry. This exact formula is often expensive to evaluate, which motivates the Erlang fixed point approximation.
The same occupancy stationary distribution extends to independent general holding-time distributions with these means by insensitivity of loss networks; the exponential assumption above makes the occupancy process itself a continuous-time Markov chain and permits the direct detailed balance proof.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 216 2 b Solution Created 2026-10-03 Updated 2026-10-05
Write and letThis is the accepted fraction of directions when zero-length chords are redrawn; it equals one in the interior. The Markov kernel integrates a test function asThe signed polar representation has Jacobian determinant . Each point is represented twice, once with positive and once with negative and the opposite direction. Since the chord is the same in either representation, the hit-and-run kernel density isfor almost every , and it is zero outside the body. Thus the transition is absolutely continuous with respect to planar Lebesgue measure. Redrawing removes the only potential zero-chord atoms.
Let . For distinct , the chord contains their segment, so it has positive length, andHence . Values on the diagonal, and on other null sets where a density is only specified almost everywhere, can be assigned this same lower bound. This gives a version satisfyingFor interior , and the chord length is unchanged on interchanging its endpoints, so . A convex body's boundary has area zero; for example contractions about an interior point fill the interior and their areas tend to the body's area. Thus this symmetry holds almost everywhere for two uniform points, proving detailed balance and stationarity of the uniform distribution. Without positive area or the boundary convention in part (a), the literal assertion need not hold.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 216 5 Solution Created 2026-10-03 Updated 2026-10-05
Let be the standard multivariate normal density. Independence gives the proposal distribution densityFor an orthogonal matrix ,The isotropic Gaussian density is unchanged by this transformation. Since has the same distribution as ,Thus this is an orthogonal-mixture Metropolis proposal with a symmetric density; inversion invariance, rather than any assumption of a uniform distribution on orthogonal matrices, is what is needed.
With , the accepted off-diagonal transitions satisfyThe rejection part is supported on the diagonal and satisfies detailed balance automatically. Values of the acceptance rule at starting points where can be specified separately; they do not affect stationarity under . Therefore the Metropolis–Hastings algorithm kernel is reversible with invariant density , proving
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 219 2 v Solution Created 2026-10-03 Updated 2026-10-05
Let be the normalized density in the transformed coordinates of (iv). Its fixed Gaussian increment gives a symmetric proposal distribution: . For distinct states, the accepted transition density is , where . ThenThe rejection probability gives a mass on the diagonal, which trivially satisfies the same balance identity. Thus , the detailed balance condition, and integrating it proves invariance of the target.
The transformed density includes its Jacobian, so mapping back preserves the desired posterior law. Warmup adaptation is excluded from this fixed-kernel proof. Independent augmentation with is itself a reversible conditional update; alternatively the original joint augmented space can be sampled directly. This is the Metropolis–Hastings algorithm balance argument.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 219 4 iii c Solution Created 2026-10-03 Updated 2026-10-05
Keeping the powers and exponentials of and in the joint kernel gives the two inverse-gamma distributions, using the printed shape–scale convention:Indeed their kernels are and . With positive measurement variances and generic continuously drawn latent values, the two scale parameters are positive almost surely. Together with (a),(b), these are all formal full conditional updates.
There is, however, no joint posterior probability distribution to sample under the stated priors. Integrate out the intrinsic first. For fixed , the observational marginal density iswhere is the centred normal density of variance . Substitute . Dominated convergence givesThe convergence is uniform on any compact interval and any compact positive interval, since the normal densities are uniformly bounded and continuous there. Hence some such region has for all sufficiently small , andIntegrating over those positive-measure intervals proves that the full normalizing constant is infinite. If all , the boundary also gives a positive marginal likelihood and a divergent integral at fixed . Thus , even though its generic full conditionals are proper. Apparent stability of a simulated chain cannot establish a nonexistent stationary probability law.
A valid repair that preserves direct sampling is to replace the two log-flat priors by independent proper and , with all four constants positive. The normal and truncated-normal updates remain as above, whileWith positive , the flat prior is then harmless: after integrating it out, the Gaussian measurement likelihood is bounded uniformly over the latent shifts and the scales, and the remaining proper priors integrate to one. A proper prior on is also possible.
For this repaired model, initialize , and finite . Repeatedly choose one of the coordinates with fixed positive probabilities and redraw from its full conditional using the latest values. This Random-scan Gibbs sampler preserves the proper target and satisfies detailed balance: for each coordinate, both forward and reverse flows equal the marginal density of the remaining coordinates times the product of the two conditional densities. A systematic full sweep is another invariant scheme, though it need not itself be reversible.
Run several dispersed chains; inspect traces of both scales, , representative latent values and the log posterior. Assess rank-normalized split , autocorrelation, and the effective sample size of a Markov chain, and extend runs until relevant Monte Carlo errors are sufficiently small. Scale–latent dependence can cause slow mixing, so diagnostics must include boundary exploration and alternative initializations. Keep post-warmup draws without automatic thinning. These are convergence checks for the repaired posterior; the printed model admits only the formal update algorithm, not a valid posterior-sampling interpretation.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 344 1 c Solution Created 2026-10-03 Updated 2026-10-05
At thermal equilibrium, microscopic reversibility equates the probabilities of a path and its reversed path when both include their Boltzmann distribution initial weights. Denote their endpoint states by , including velocity if needed. Since the Hamiltonian is even under time reversal in classical mechanics,This detailed balance condition and the energy balance for an autonomous Lagrangian yieldThis is the fluctuation-dissipation relation for a Langevin particle: the strength of Gaussian white noise is fixed by the damping and temperature, with the Boltzmann constant.
For an equilibrium coarse-grained variable, the unresolved microscopic states contribute entropy; their statistical weight is encoded in the Helmholtz free energy, rather than in a single microscopic energy. Relative to the same reference measure, , so microscopic reversibility becomesThis extension assumes an equilibrium coarse-grained description with reversible path statistics; externally driven dynamics need not obey this relation.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 3 13C d Solution Created 2026-09-24 Updated 2026-10-03
With and constant , the Fokker-Planck probability current becomesIn the stationary state we impose the stronger zero-current condition , corresponding to detailed balance.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 219 3 d Solution 2026-10-03
Write the target posterior density as and the proposal distribution density as . The Metropolis–Hastings algorithm accepts a proposed move withFor distinct states,which is symmetric in and . The rejection probability supplies the diagonal part, so the entire transition kernel satisfies detailed balance. Integrating the detailed-balance identity over the starting state proves . Hence the posterior is a stationary distribution; an irreducible Markov chain that is also an aperiodic Markov chain converges uniquely to it.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 2 27K b Solution Created 2026-09-24 Updated 2026-10-03
A reversible Markov chain must satisfy detailed balance. For every , the rate from to is positive, while the reverse rate from to is zero. No positive measure can satisfy , so the irreducible chain is not reversible.