Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 29 6 ii Solution Created 2026-10-03 Updated 2026-10-06
Construct a rate- Poisson process, for , from independent waiting times with exponential distribution . Put , , and . The strong law of large numbers gives , so there are only finitely many arrivals on each finite interval. Consequently the counting paths are càdlàg, and almost surely.
At any deterministic time , the memorylessness of the exponential distribution says that the residual waiting time has again exponential distribution and is independent of the observed history. Subsequent waiting times are fresh independent copies. Thus the Poisson process restarts independently at , proving independent increments and stationary increments. Integrating the joint waiting-time densities over givesso its time values have the expected Poisson distribution.
For ,Together with stationary increments, this gives stochastic continuity at every time, from either side where applicable. All the Lévy process requirements hold, andFor , the identically zero process gives the degenerate case.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 35 3 d Solution 2026-10-06
Assume individual incubation delays are independent of the Inhomogeneous Poisson process of infections and of one another. This marking assumption is needed in addition to specifying a marginal incubation density.
In the discrete cohort model let be the independent infection counts. Mark each infection by its eventual onset interval. For cohort , the categories have probabilities for observed intervals, with the remaining probability assigned to onsets outside the window. Poisson thinning makes the counts in these categories mutually independent Poisson random variables with means . One direct proof is their probability generating function:Different cohorts are independent. Summing their counts therefore gives independent Poisson onset counts in disjoint intervals:The same argument applies exactly in continuous time by the Independent marking theorem for Poisson point processes and mapping each marked infection to its onset time. The endpoint model approximates its means; its independent-Poisson conclusion is exact within that discrete model. A fixed cohort size would instead induce negatively correlated onset-bin counts, so the Poisson process infection assumption matters.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 39 1 Solution Created 2026-10-03 Updated 2026-10-06
First consider an M-M-K queue with servers, arrival rate , and service rate at each server. Assume so that a stationary distribution exists. Its population is a birth-death process with rates and . The equilibrium probabilities satisfy detailed balanceThus the population process is a reversible Markov chain. In its time reversal of a continuous-time Markov chain, forward departures become upward jumps whose rate is the constant , independent of the state. They can be generated by a rate- Poisson process independent of the initial reversed state. Reversing time preserves the Poisson process law, proving the equilibrium departure process is Poisson with rate , the Burke theorem for a multi-server queue.
The same argument gives the departure component of quasireversibility needed for the tandem calculation: the present upstream population is independent of its entire past departure process. Indeed, these departures become future arrivals in the reversed chain, independent of its initial population. First check this on finite time windows, then extend to the full past. A Poisson output alone, without this independence, would not justify multiplying queue-empty probabilities.
Now let , where denotes the mean service time at passport control, so the service rate at each of its two servers is . The stationary distribution of the M-M-s queue with has normalizing sumHence its empty probability is . Its output feeds a stable M-D-1 queue with rate and deterministic service time . In a stationary work-conserving single-server queue, the busy fraction is the rate of completed work, , so the empty probability is .
The downstream stationary workload is a causal function of past upstream departures. For example, it is the limit of workloads constructed from arrivals in increasingly long finite past intervals; stability makes this stationary construction well defined. The backward independence just proved therefore makes the two present queue populations independent. Consequently
With walking time , the downstream arrival stream is the upstream departure stream shifted by . Its present workload depends only on departures up to time . The number walking at time zero is the number of departures in , which has Poisson distribution of mean and is independent of the earlier departures. The upstream present population is independent of both parts of its past departure stream. Thus the three empty events factor, givingThe factor is the empty probability of the deterministic-travel infinite-server stage. Both printed stability inequalities ensure the stationary calculations apply.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 39 2 Solution Created 2026-10-03 Updated 2026-10-06
For the Erlang loss formula, assume a Poisson process of arrivals with rate , independent holding times with exponential distribution of mean , unit capacity usage per accepted call, and rejection without waiting when all units are occupied. Here is a positive integer and the offered load is . The call population on is a birth-death process; detailed balance givesBy Poisson arrivals see time averages, the fraction of arrivals rejected is the time probability of full occupancy. ThereforeThe paper's is the offered load, rather than necessarily an arrival rate. Exponential holding times suffice for this derivation; no unproved insensitivity of loss networks assumption is needed.
A loss network with fixed routing has capacities , call types , and a link-route incidence matrix with exactly when a type- call requires link . An accepted call holds one unit on every link of its route for its holding time; if any required link is full, the call is rejected everywhere. Take independent Poisson processes of calls, independent holding times, and route offered loads . For the finite-variable formulation below, take ; a zero-capacity link and all routes using it may be removed first.
The Erlang fixed point approximation treats blocking at different links as independent and thins the traffic offered to link by acceptance at the other links. Its reduced offered load isThe equality uses : only routes with contribute. Treating this reduced stream as Poisson leads to . Independence and Poisson thinning here are the approximation, not exact properties of a general loss network.
To construct the convex potential for the Erlang fixed point, write and , the carried load of an Erlang loss resource, equivalently the mean occupancy in the single-link stationary distribution. Differentiating its finite sums gives, for ,The variance is positive because the finite occupancy law is nondegenerate for . Furthermore maps increasingly onto , while increases from zero to . SetIn particular , is continuous and strictly increasing, and as .
Forthe first sum is convex, and each integrated strictly increasing function is strictly convex. Thus is a strictly convex function on . Since tends to a positive limit on every coordinate, is a coercive function there; it has a unique minimizer. Its coordinate derivative isThe Erlang fixed point equation is exactly . For an unused link, and the optimum is ; for a used link with positive offered load, the derivative at zero is negative and the optimum is positive. Hence every fixed point gives the unique minimizer, and the minimizer gives a fixed point. The Erlang fixed point is unique under these fixed-routing assumptions.
A convergent cyclic substitution for the Erlang fixed point updates one coordinate at a time, repeatedly cycling through all links:Always use the most recently available values of the other coordinates. Start, for example, with . In coordinates this is exact coordinate descent for : with other coordinates fixed, the displayed update is the unique coordinate minimizer.
Here is a convergence proof. All iterates stay in the initial compact sublevel set of the coercive function , and their potential values decrease to a limit. Each single-coordinate update is continuous, since its reduced load is continuous and finite and . Thus a whole-sweep map is continuous. If a full-sweep subsequence converges to , continuity gives , because both consecutive potential values converge to the same limit. Strict coordinate convexity means equality can occur only when no coordinate changes during that sweep. Thus minimizes every coordinate, satisfies the nonnegative-orthant first-order conditions, and is the unique global minimizer of . Every subsequential limit is therefore the same point, proving convergence of the full-sweep iterates and, by continuity of the updates, all intermediate iterates. This argument applies to sequential substitution; it does not assume simultaneous updates converge.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 39 5 Solution Created 2026-10-03 Updated 2026-10-06
A feasible per-flow allocation satisfies for each active route and . It has proportional fairness if every feasible competitor obeysBy the first-order inequality for the strictly concave logarithm, this is equivalent to maximizing weighted logarithmic utility over the feasible allocations. Inactive-route rates are immaterial; set them to zero as a convention.
Write , , , and . The capacity constraints are and . For , put . Each active local route uses its remaining capacity . Omitting constants, the utility isIts maximum has ; when , the maximum is the endpoint . Hence for active routesThese formulas also give and when . When there is no allocated service. Equivalently, the aggregate route rates for areThis is the proportionally fair allocation on a two-resource linear network for a two-resource linear flow network.
For independent Poisson processes of documents and independent document sizes with exponential distribution of rate , the memorylessness of the exponential distribution makes the population a continuous-time Markov chain. Its transition intensities areThe departure intensity sums the independent completion hazards . There is no departure on an inactive route. Set , with .
To prove the proposed stationary distribution, define the balance function of a flow-level networkFor an active local route, , while for the through route this ratio is . Thus . The weightssatisfy detailed balance on every arrival-departure pair:Each total jump rate is bounded by , so the chain is a nonexplosive Markov chain; normalized detailed-balance weights therefore give its stationary distribution, the stationary law of a two-resource linear flow network.
Use the negative binomial series to sum first over :The remaining two geometric series giveAll summands are nonnegative. Consequently the sum is finite exactly under the stability conditions for a two-resource linear flow networkThese say that the offered load on each unit-capacity resource is strictly below one. Equality is insufficient: at least one geometric series then diverges. If all arrival rates are positive, the chain is irreducible and the normalizable law is its unique equilibrium law.
Finally put , . Summing over yieldsThus the two local-route counts are independent, each with geometric distribution on the nonnegative integers. The conditional through-route count has negative binomial distributionFor positive traffic rates this depends on the local counts, so all three route counts are not independent. More quantitatively, , and likewise for . If zero arrival rates are allowed, the exceptional independent cases are , or , when the relevant counts are deterministic zero. This distinction is local-count independence with through-flow dependence.
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 2 24K i Solution Created 2026-09-24 Updated 2026-10-06
A rate- Poisson process is a counting process starting at zero, with right-continuous nondecreasing integer-valued paths, independent stationary increments, and for . Its jumps have size one almost surely.
For independent Poisson processes , increments of on disjoint intervals are independent, because all the corresponding increments of the two processes are jointly independent. On an interval of length , multiplying their probability generating functions givesThus the increment is Poisson with mean . The path requirements hold, and independent processes almost surely have no simultaneous jumps. Therefore is a Poisson process of rate .
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 3 23K i Solution Created 2026-09-24 Updated 2026-10-06
In an interval of length , condition on the Poisson process count . Independently marking its points gives . The joint probability generating function of kept and discarded counts isIt factors into the generating functions of independent Poisson variables of means and . The same calculation applies to any interval, and counts and marks in disjoint intervals are independent. Hence is a Poisson process of intensity , and and are independent. This is the Poisson thinning theorem.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 201 6 b Solution Created 2026-10-03 Updated 2026-10-06
Both Poisson processes start at zero and have càdlàg paths. On disjoint time intervals their increments are independent, and independence of the two processes makes the difference increments independent as well. Their increment laws depend only on interval length, so has stationary increments. For a time interval of length , the probability that either Poisson process has a jump is . This proves stochastic continuity. Consequently the difference is a Lévy process, equivalently a continuous-time symmetric simple random walk with total jump rate one and jumps and each chosen with probability .
The characteristic function of a Poisson variable of mean is . Independence therefore givesThus, in the negative-exponent convention of part (a),In the positive-exponent convention the answer is . The Compound Poisson process has mean zero and variance , consistent with the expansion .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 207 3 f Solution Created 2026-10-03 Updated 2026-10-06
For the stochastic SIR model, the state is a continuous-time Markov chain on nonnegative integer triples summing to , initially . Its only transitions areRates vanish when a proposed transition would leave the state space. Equivalently, with independent unit-rate Poisson processes , the Poisson time-change representation of a Markov chain isThe left limits describe the state immediately before each jump. In the Gillespie algorithm, wait an exponential distribution time with rate , then choose infection or recovery in proportion to these two rates.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 213 1 i Solution Created 2026-10-03 Updated 2026-10-06
An open migration process is a continuous-time Markov chain recording the populations of finitely many colonies. Independent external Poisson processes bring individuals to colony at rate . When that colony contains individuals, a departure opportunity occurs at total rate , with . The departing individual moves to colony with probability , or leaves the system with probability . Routing choices and the clocks are independent. A return to the same colony does not change the state.
The word open means that the routing matrix is transient: every individual eventually leaves, or equivalently the spectral radius of is less than one. The traffic equations of an open migration process, with row-vector convention, give the total arrival rates:These rates include migrations as well as external arrivals. On the active colonies assume and the usual irreducible Markov chain condition. PutThe product form and its normalization condition areTo establish the product-form stationary distribution of an open migration process, first use its unnormalized weight . Its ratios satisfy . The incoming external arrivals into , divided by , contribute . Incoming exits contribute . Incoming migrations from to contribute . Terms involving an empty destination are zero. Thus the full incoming rate divided by isHere the traffic equations of an open migration process give the second equality, including . The right side is precisely the total outgoing rate. This proves global balance for a continuous-time Markov chain; pairwise detailed balance is not required for general routing.
For finite rates at each finite population, the continuous-time Markov chain is nonexplosive Markov chain: its total population is bounded over a finite time interval by the initial population plus the finitely many external arrivals, so it visits a finite set on which all jump rates are bounded. Consequently finite normalize the invariant weight to a stationary distribution. Under the stated irreducible Markov chain assumptions, this is the unique stationary distribution, and it is a positive recurrent Markov chain. Conversely, the unique invariant measure of an irreducible recurrent chain is proportional to , so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ; the series criterion itself is the exact condition. Colonies with have zero stationary population and can be removed from the active class.
For the single-server M-M-1 queue specialization, for , each stationary colony has the geometric distribution of an M-M-1 queue:The traffic equations of an open migration process do not involve the service rates, so the remain fixed during this service-capacity allocation in an open migration process. Write , and . A stationary allocation requires , with and . The Cauchy-Schwarz inequality givesEquality holds exactly when is proportional to . Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf and some arrival rate is positive, no stable service allocation exists. Zero-arrival colonies need no service in their stationary empty class: allowing zero service there gives the same formula restricted to active colonies. If strictly positive service is demanded even at inactive colonies, the displayed minimum is an infimum approached as that unused allocation tends to zero. If all arrivals vanish, the stationary mean population is zero for every allocation that drains the initial population.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 213 2 Solution Created 2026-10-03 Updated 2026-10-06
In a loss network with fixed routing, calls of type arrive as independent Poisson processes with rates . Every accepted call occupies units of resource throughout its holding time. The link-route incidence matrix has nonnegative integer entries, is the resource-capacity vector, counts calls currently present, and is the th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing . With independent unit-rate exponential distributions for holding times, the memoryless property makes a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.
Let . For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make finite. Even zero-resource routes cause no normalization difficulty: the sum is at most . With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.
The vector records the free units of each resource. Its probability distribution sums over all occupancies with the same free resources. The map from to generally loses information: different call mixtures may consume exactly the same resources.
For , the conditional expectation can be computed by removing one call. The factorial identity givesIndeed, is a bijection from the occupancies in this sum with to occupancies using units. Conversely, adding one call to any such occupancy is feasible because its final resource use is . Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity and multiplying by now yieldsAlternatively, multiply the preceding unnormalized factorial identity by and sum over directly; this proves the same formula even when , without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 320 1 Solution Created 2026-10-03 Updated 2026-10-06
For one target galaxy, an encounter with relative speed sweeps a cylinder of volume in time . Multiplication by the number density gives the encounter rate . Thus the geometric galaxy-encounter rate givesThis is the expected number of mergers in the geometric model. For independent encounters, the Poisson process probability of at least one is , so the displayed linear probability is valid for rare encounters, . There is no factor of one-half for a single target; that factor would enter a count of distinct pairs across the whole population.
For an illustrative group environment, take , , and a Hubble time of order years, or . The path length is about , using the stated distance conversion. HenceThe estimate scales linearly with environment density and quadratically with the adopted merger radius. It is an order-of-magnitude model estimate, not a universal observed merger fraction; reducing the illustrative density by a factor of one hundred reduces the estimate by the same factor.
For the tidal calculation, use the relative potential convention in which acceleration is . Expand the point-mass potential about the target centre:The constant does not exert a force. The linear term accelerates the target centre and is subtracted in its freely falling frame. The remaining leading quadrupolar point-mass tidal potential isThe condition permits the convergent expansion; using only this term is the leading tidal approximation, accurate when the target radius is small compared with the closest separation.
The given impact and velocity directions imply . This trajectory is in the plane, correcting the incompatible printed plane. In the impulse approximation, hold the stellar position fixed while integrating the tidal tensor:For , the needed integrals arewith the mixed integral zero by oddness. Thus the integrated tidal tensor of a straight-line flyby is andThere is stretching along the impact direction, compression in the other transverse direction and no net kick along the path.
Write for the star's initial velocity, distinguishing it from the perturber speed . Its specific energy change is . The no-correlation assumption removes the first term on averaging; it is not an identity for every individual star. The mean specific heating at a given position is thereforeFor a spherical target, the mass-weighted averages satisfy . The tidal impulse heating of a spherical galaxy is consequentlyHere is assumed finite. Notice the change from specific energy to total energy after multiplying by .
For two equal targets, each gains the same internal energy, so . Their relative-motion reduced mass is . If denotes their relative speed at infinity, their initial orbital energy is . Internal tidal heating comes from this orbital energy. In the tidal capture of galaxies model, capture occurs if , which gives the equal-mass tidal-capture thresholdCapture allows further passages and eventual merger in this simplified picture.
The encounter lasts roughly . The impulse approximation needs , so that a star barely moves during the tide. When , stellar orbits respond during the perturbation and the kicks can cancel. Adiabatic invariance of an orbital action produces adiabatic shielding of tidal encounters, rather than the impulsive heating used above. The capture inequality cannot be extrapolated into that slow-encounter regime.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 2 25K a Solution Created 2026-09-24 Updated 2026-10-05
A rate- Poisson process has , right-continuous paths with upward jumps of size one, stationary independent increments, and for . Assume . Its successive waiting times are independent exponential variables of rate . For , the product of their densities and the probability of no further jump before isDivide by to obtain the conditional joint densityBoundary inequalities do not affect a density. Equivalently these are the ordered values of independent uniform points of . For , the conditional tuple is empty.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 213 1 iii Solution Created 2026-10-03 Updated 2026-10-05
Consider a triangle of three links, each with capacity . Calls for each pair of its three nodes arrive as independent Poisson processes at rate and have independent holding times with an exponential distribution of mean one. Try the direct link first; if it is full, try the two-link path through the third node; if either alternative link is full, reject the call. This is alternative routing in a loss network.
In the symmetric Erlang fixed point approximation, let be each link's blocking probability. A given link receives direct offered traffic . Each of the other two call types contributes overflow traffic , screened by the availability of the other link on its alternative path. ThusThe extra term expresses a feedback: blocking sends calls onto longer paths, which consume more total capacity and can create still more blocking.
Here is an explicit finite-capacity example, not just a limiting argument. Take and , and let . Evaluating the Erlang loss formula givesThe displayed decimals are rounded, but the four signs can be checked exactly using the rational recursion , . By the intermediate value theorem, there is a fixed point in each of , , and . Numerically these three areThus alternative routing can produce multiple Erlang fixed points. This does not imply multiple stationary distributions for the exact finite continuous-time Markov chain, which is irreducible and has a unique stationary distribution; the multiplicity belongs to the approximation. The symmetric alternative-routing model is also discussed in Kelly's review of fixed point models of loss networks.
