Past exam of the mathematics course of the University of Cambridge 2014 ib Paper 1 20H ii Solution Created 2026-09-24 Updated 2026-10-06
The convergence theorem for an irreducible aperiodic positive recurrent Markov chain says for every pair of states. Apply it to and take the complement:Although , the chain is aperiodic because its possible return lengths have greatest common divisor one; a self-loop is sufficient but not necessary for aperiodicity.
Past exam of the mathematics course of the University of Cambridge 2014 ib Paper 1 20H i Solution Created 2026-09-24 Updated 2026-10-06
For a state , its period is ; the condition defines aperiodicity. It is a positive recurrent state if return occurs almost surely and its first strictly positive return time has finite expectation. An ergodic state of a Markov chain is positive recurrent and aperiodic.
The PDF specifies for ; the TeX aid drops the essential value one. Consequently every positive state reaches zero deterministically. From zero, every positive state is reached in one step with probability . Paths through zero connect any pair of states, proving irreducibility.
Let be the jump out of zero. It has for , after which exactly downward steps return to zero. Therefore , givingThese probabilities sum to one andReturns of lengths two and three both have positive probability, so the period is one. Hence state zero is ergodic, and by irreducibility all states are positive recurrent and have the same period.
For this geometric-jump countdown Markov chain, the invariant equations give and for . Summing the tail, or counting visits in a regeneration cycle, yields . Normalization givesThis is the stationary distribution of a regenerative countdown chain. The standard recurrence identity for an irreducible positive recurrent Markov chain is , so
Past exam of the mathematics course of the University of Cambridge 2014 ib Paper 4 9H a Solution Created 2026-09-24 Updated 2026-10-06
The Markov property and the Chapman-Kolmogorov equation giveFor each intermediate state, one first uses the next-step transition probability and then the following one; the sampled history adds no information once is known. Thus is a homogeneous Markov chain with transition matrix and initial law . In particular,If zero is not a state of , this probability is zero.
Past exam of the mathematics course of the University of Cambridge 2014 ib Paper 4 9H b ii Solution Created 2026-09-24 Updated 2026-10-06
Starting from forces . The first nonzero value is consequently . Remaining nonzero at the next step forces , because . Hence, on an event of positive probability,The two values are unequal by assumption. They expose memory of the hidden sign: immediately after leaving zero the sign is negative, whereas after two consecutive nonzero observations it is positive. Whenever the relevant observed histories coexist with positive probability, the Markov property for fails, since its next-step law is not determined by its present value alone. In particular, the absolute-value projection does not preserve the Markov property for all initial laws; the strong lumpability condition would require .
There is a small qualification to a blanket conclusion about an unspecified initial law. The printed assumptions do not ensure that either conditioning event is possible, and a degenerate initial law may never reach the hidden states that cause the failure. For example, in the order , takeAll printed constraints hold, yet always and is a Markov chain. Thus the correct general conclusion is the transformed process is not necessarily Markov; the two computed probabilities give the intended failure when their histories are available.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 5 a Solution Created 2026-10-03 Updated 2026-10-06
Let be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure such that, for every measurable and every starting state ,Equivalently, there is positive probability of eventually reaching every set of positive reference measure. For a finite state space with counting measure, this becomes ordinary irreducible Markov chain accessibility. On a continuous space, requiring access to each individual point would usually be inappropriate; positive-measure sets play that role. Irreducibility requires positive probability, rather than probability one, and does not itself assert recurrence or a finite mean return time.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 5 d 3 ii Solution Created 2026-10-03 Updated 2026-10-06
Let be the normalized target and its marginal distribution. A coordinate- kernel leaves and has the joint old-new measureThis is symmetric in the old and new state: the common remaining coordinates are fixed and the two conditional factors exchange places. Thus each coordinate kernel satisfies detailed balance. Averaging them with the fixed weights provesIntegrating out the old state proves invariance of . The common normalization cancels, so detailed balance can also be written with the unnormalized target. This establishes detailed balance of a random-scan Gibbs sampler and a reversible Markov chain. Fresh independent random choices make the update a Markov chain, as explained above; invariance is not an assertion that an arbitrarily initialized chain starts in stationarity.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 37 6 i d Solution Created 2026-10-03 Updated 2026-10-06
Apply the Monte Carlo estimator to the observable :The theoretical justification is the ergodic theorem for a positive Harris recurrent Markov chain, not an independent-sample law of large numbers. The Markov chain has finite state space, is irreducible, and has the strictly positive posterior distribution as invariant law, so it is positive recurrent and Harris recurrent with counting measure. The observable is bounded: . Thus the estimator converges almost surely to the posterior expected value from any initial configuration.
Each state also has positive self-transition probability, so the chain is an aperiodic Markov chain. Finiteness then gives geometric convergence and the relevant central limit theorem; serial dependence determines the Markov chain Monte Carlo asymptotic variance if error bars are required. A fixed finite burn-in can be discarded without changing consistency, but independence of the retained states should not be assumed.
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 2 24K ii Solution Created 2026-09-24 Updated 2026-10-06
The random clock is understood to be independent of the discrete-time Markov chain; without this hypothesis its law need not be determined by alone. Conditional on , the transition matrix is , soHence for and . If , then by the series, proving that the invariant distribution is unchanged.
Let be the independent exponential interarrival times of the Poisson process. The absorption time is . By independence of the chain and clock and Tonelli theorem,This includes infinite expectations and absorption at time zero. The same argument proves the hinted random-sum identity for an independent nonnegative integer-valued count .
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 4 23K i Solution Created 2026-09-24 Updated 2026-10-06
Assume , so the conditioning event has positive probability. For a continuous-time Markov chain, write . At each time , the Markov property gives . Using Tonelli theorem for the nonnegative occupation integral,Division by yields . The discrete-time proof replaces the integral by a sum. Infinite expectations are allowed in the nonnegative sense; if , the numerator is zero directly, avoiding an ambiguous product of zero and infinity.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 1 20H a Solution Created 2026-09-24 Updated 2026-10-06
A Markov chain is irreducible if every state can reach every other state in finitely many steps with positive probability. It is a recurrent Markov chain if, starting at any state, it returns to that state with probability one; for an irreducible chain this property is shared by all states.
For the simple symmetric random walk on , taking steps all in the appropriate direction reaches from with probability . Thus the chain is irreducible. Its return probabilities areBy Stirling formula, , so their sum diverges. The standard recurrence criterion therefore proves the walk is recurrent.
The printed hint's constant is erroneous: the actual limit of is . Its positivity is what the recurrence argument requires, but the reciprocal is necessary for the correct numerical value.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 1 20H b Solution Created 2026-09-24 Updated 2026-10-06
An irreducible Markov chain has positive recurrent states if the expected first return time to a state is finite; this then holds for every state. A recurrent chain with infinite mean return time has null recurrent states.
An irreducible positive recurrent chain admits a stationary distribution. If such a distribution existed for this walk, its stationarity equations would giveThus , so . Nonnegativity for all positive and negative integers forces . A constant sequence cannot sum to one over , so no stationary probability distribution exists. Hence the walk is null recurrent, not positive recurrent: all its states are null recurrent states. The first-return generating function in part (c) also verifies directly that its mean return time is infinite.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 3 a Solution Created 2026-10-03 Updated 2026-10-06
Use the shape-rate convention for every gamma distribution, with . Let and . The Poisson distribution likelihood and the Gamma–Poisson hierarchical model giveAll factors involving the coordinate being updated must be retained, including from the conditional gamma distributions. The full conditional distributions areFor a blocked Gibbs sampler, draw from the second full conditional distribution, then redraw all the independently from the first ones. Repeating these two steps preserves the joint posterior distribution; observing after each complete sweep gives the Markov chain used in the next part. Standard gamma distribution sampling works for noninteger as well as integer shapes. The positive observation-period convention is used for the subsequent geometric drift condition.
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 2018 ib Paper 1 20H Solution Created 2026-09-24 Updated 2026-10-03
Let the Markov chain state after each toss be , where is player 's net winnings and is the next player to toss. From it moves to with probability and to with probability . The initial state is , and a return means hitting any state with at positive time.
From , the probability of hitting zero isIndeed, in the positive-drift case the bounded harmonic solution ofuses the decaying root and boundary value , yielding ; with nonpositive drift the walk hits zero surely. By the reflected argument, from the probability isConditioning on the first toss, the required return probability isBoth formulas equal one at the boundary .
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 2 20H i Solution Created 2026-09-24 Updated 2026-10-03
For a finite irreducible Markov chain with invariant distribution , the mean recurrence time of state isThe simple random walk on the hypercube has the uniform invariant distribution because the hypercube graph is regular, so every vertex has mass . Therefore the expected first positive return time to the initial vertex is
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 213 3 Solution Created 2026-10-03 Updated 2026-10-05
Use the slotted ALOHA model with one outstanding packet per active station and a collision channel: a slot with exactly one attempt succeeds, whereas an idle slot or a slot with two or more attempts delivers nothing. Let be independent Poisson random variables of mean , independent also of the transmission choices. Arrivals join after the current slot's attempts. Given , the attempt count has a binomial distribution with parameters and . Consequently, for ,For , set and . The equation adds arrivals and removes precisely one packet following a successful slot. The estimate controls the common transmission probability and updates using the idle, success, or collision feedback. The conditional distribution of the next state depends only on , so this pair is a Markov chain.
Away from the reflecting floor in , its one-step conditional expectations areWhen and are large with , the Poisson limit theorem gives and . Treating these approximate drifts as derivatives motivates the fluid approximation of slotted ALOHA:The floor at is negligible in this interior scaling. This calculation motivates the ordinary differential equations; it is not a proof of a stochastic fluid limit.
The function is strictly increasing from zero to infinity, and . To check the monotonicity explicitly,Indeed, with ,because its discriminant is ; and . Thus the scalar ordinary differential equation for points toward the unique value satisfying . Every trajectory with , has bounded and . Positivity of follows from .
If , then and . Thus decays exponentially for large , andThis is finite-time draining of a fluid model. The unmodified equations have undefined at the origin, so the statement that trajectories converge to the origin needs this endpoint interpretation; continuing with an absorbing zero trajectory is an additional fluid-model convention, not a solution of the displayed equations at the origin.
If , then and . Now grows exponentially, physical time tends to infinity, andIn particular the trajectory escapes to infinity. Even without the ratio analysis, , since .
For the actual Markov chain, it is essential not to replace the finite- success probability by : a single backlogged packet can succeed with probability one. Instead, for , maximizing over gives the ALOHA throughput boundIf , choose and so that for all , uniformly in . For sufficiently small ,because its derivative at zero is . Independence of arrivals and attempts giveswhenever . For any integer , stop at the stopping time . The stopped process is a nonnegative supermartingale. The optional stopping theorem, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundFrom every state with , a Poisson distribution arrival burst has a uniformly positive probability of sending the next backlog to at least , for any fixed . From there the probability of never revisiting is at least . By the Markov property at successive visits, the probability of infinitely many visits to this strip is zero: each visit has a uniform positive chance of being the last. This holds for every integer , soTherefore the Markov chain is transient for every finite choice of . The proof is uniform in and does not infer stochastic transience merely from the approximate ordinary differential equations.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 213 4 Solution Created 2026-10-03 Updated 2026-10-05
For a fixed occupancy , let be the per-flow rate on every active route, so feasibility means . A proportionally fair allocation is a feasible allocation satisfying, for every other feasible ,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with have no per-flow rate to determine.
Index the four routes by , , , , and let be each route's total service. WriteThe four capacity constraints say , , , and . Equivalently,For fixed maxima , every active route in the first group optimally takes total service , and every active route in the second takes , because its logarithmic objective is increasing. Up to the constant , the objective therefore becomes with . Its maximizer is , when , with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet on inactive routes. If , all service totals are zero. In particular, for , , as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.
With independent document arrivals given by Poisson processes of rates and independent unit-mean exponential distributions for document sizes, each of the active documents has completion rate . The flow-level network model is consequently a continuous-time Markov chain withAt all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.
The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse . For and ,so . For the corresponding ratio is . Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever .
For completeness, its existence condition can be made explicit. Put and . At fixed ,Therefore the sum over states with is at most , using the binomial theorem. This is summable if . Conversely, restricting to the single maximizing route in each group leaves the series , which diverges if . HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.
Past exam of the mathematics course of the University of Cambridge 2020 ib Paper 1 20H a Solution Created 2026-09-24 Updated 2026-09-29
A random time is a stopping time for the natural filtration of a Markov chain when for every . The Strong Markov property says that, conditionally on and , the process after is a fresh copy of the chain started from , independent of the pre- history.
Before capture define the half-separationFor , independence of the two moves gives the transition probabilitiesIgnore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability and right with probability . Its expected number of moves needed to descend one level is ; this follows either from first-step analysis or from its drift . A non-holding move occurs with probability at each time, so its mean waiting time is two. Hence, for every , the expected time to go from separation to is
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 2 18H a i Solution Created 2026-09-24 Updated 2026-09-25
A distribution is an invariant distribution whenfor every state . The pair satisfies detailed balance whenfor every . Summing this identity over givesso detailed balance implies invariance.
For an irreducible positive recurrent Markov chain, Kac's lemma relates the invariant mass to the mean recurrence time:
Past exam of the mathematics course of the University of Cambridge 2023 ib Paper 2 18H a Solution Created 2026-09-24 Updated 2026-10-03
True. If the Markov chain with transition matrix is irreducible, then for every pair of states there is a pathwith at every step. The support assumption gives for every edge of the same path. Thus every state can reach every other state under , so the second chain is also an irreducible Markov chain.