Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For a network with link-route incidence matrix , a per-flow rate vector is feasible when and for every resource. A proportionally fair allocation has strictly positive rates on active routes and satisfiesfor every feasible competing allocation . Equivalently it maximizes the weighted logarithmic utility subject to the capacity constraints. The equivalence follows from the first-order condition for this concave objective; strict concavity gives uniqueness on active routes. Rates on absent routes have no operational effect and may be set to zero.
Use labels for the routes , and put , , , , . The two-resource linear flow network has constraintsWhen and , write for aggregate through service. Every active local route uses the remainder of its resource, since increasing its rate increases utility. Up to additive constants, the objective becomes . Its derivative is , so its unique maximum is . This argument remains valid if only one local route is active: the unused local resource adds only the constraint . The resulting proportionally fair allocation on a two-resource linear network isIf , each active local route receives its resource equally, or , as the same formulas prescribe. If , only the through route is active and . At all rates may be set to zero. In particular no displayed expression is applied to an absent route with a zero denominator.
For independent Poisson processes of flow arrivals and independent exponential document sizes of parameters , the memoryless property makes a continuous-time Markov chain. Each active flow completes with instantaneous rate , so the flow-level network model has transitionsThus for the aggregate service rates areThey vanish at the empty state. The total transition rate is bounded by , so the process is nonexplosive.
Put and define the balance function of a flow-level networkThe elementary binomial coefficient ratios areHence whenever that departure is possible. Weights satisfy detailed balance for a continuous-time Markov chain, sinceWhen summable they therefore give the stationary law of a two-resource linear flow network,
It remains to determine exactly when these weights normalize. First, summing only the terms requires . For such , the negative binomial series, or the supplied identity with parameter , givesAll weights are nonnegative, so the Tonelli theorem permits this order of summation. The normalizing sum is thenThe two geometric series converge precisely under the stability conditions for a two-resource linear flow network, and evaluating them yieldsThese are exactly the strict offered-load constraints on the two unit-capacity resources; equality already makes a geometric sum diverge. For positive arrival rates the chain is irreducible, so the normalized law is its unique stationary probability and the chain is positive recurrent. Nonnegative arrival rates are also allowed with in the weights: a zero-arrival route is absent in the closed stationary class, and the same normalization conditions and formula remain valid there.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For every , the pointwise inequality holds: on the event the exponential is at least one, and off it the indicator is zero. Taking expected values and then the infimum proves the Chernoff boundAn infinite exponential moment merely gives a vacuous bound at that ; no existence assumption on moments is needed for this extended-value inequality.
For a positive at which the relevant moment-generating functions are finite, apply the Chernoff bound to . Independence of the sources givesThusClasses with make no contribution, so no moment assumption on those inactive classes is necessary. The effective bandwidth is the exponential-moment capacity demand of one class- source over this observation interval. Independent sources have additive effective bandwidths; reserving the margin below capacity certifies the desired overflow bound. If describes traffic during one unit of time, this is a bandwidth in traffic per unit time; for a window of length , divide by instead.
To establish monotonicity and bounds of effective bandwidth, write for a representative source. The Holder inequality gives, for in its moment domain,Equivalently, the cumulant-generating function is convex with , so its secant slope from zero is nondecreasing. Hence is nondecreasing, rather than necessarily strictly increasing: if is deterministic its effective bandwidth is constant.
Assuming the mean is defined and finite, the Jensen inequality gives , hence . LetFor finite , almost surely, so and . Combining these provesThe upper bound is vacuous if the essential supremum is infinite. For nonnegative traffic these comparisons also make sense with extended values; for an arbitrary real-valued source with undefined mean, the printed mean comparison itself requires an integrability qualification. The positive parameter domain is essential: is defined only by a limit when the appropriate moment assumptions hold, and the stated monotonicity comparisons concern .
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A random access network shares one communication channel among an unbounded collection of possible transmitters. Each packet occupies one slot; exactly one attempt succeeds, an idle slot carries nothing, and a collision delivers none of its attempted packets. Assume perfect slot synchronization, immediate idle/success/collision feedback, no channel errors, and independent random choices by packets. The important quantities are throughput, the size of the retransmission backlog, and delay. A good one-slot success probability alone does not establish stability of the backlog.
For a precise infinite-population slotted ALOHA model, let be independent Poisson random variables of mean , representing new packets which attempt immediately in slot . Let be the backlog before those arrivals. Each old packet independently retries with a constant probability , so conditional on , its retry count is , independent of . If records a successful slot, thenThis includes a new packet in the backlog precisely when it has not succeeded; an old packet is removed precisely when it succeeds. The total backlog is a Markov chain in this constant-probability model. Its idle and success probabilities arewith the second term in interpreted as zero. A success may be either one new packet and no old attempt, or one old attempt and no new packet.
The fluid approximation of slotted ALOHA replaces the binomial retry count by a Poisson count when there are many packets with small retry probability. If is total attempt intensity, the approximate success probability is . Differentiation givesThis is the limiting ALOHA throughput bound, not an exact upper bound for every finite packet population: one isolated packet which certainly transmits succeeds with probability one. In a fluid model, when the equation has two roots. The root below one is locally stable for constant , while the root above one is unstable, because the drift derivative is . These approximations explain a low-backlog operating region and a congestion threshold; they do not imply a stationary law for the infinite-population chain.
Indeed, for fixed , the exact success probability tends to zero as , so the exact drift tends to . One can prove instability, rather than relying only on this positive drift. Fix and use . Since is zero or one,The first term is strictly less than one and the second tends to zero. Hence is a nonnegative supermartingale outside a sufficiently large finite set, where is the first entrance into that set, say . The optional sampling theorem for a supermartingale, first at bounded stopping times, givesThis is an exponential-supermartingale escape bound. The chain is irreducible: a no-arrival slot with exactly one old retry can reduce any positive state by one, and Poisson arrivals can reach arbitrarily high states. Therefore the escape probability proves transience and excludes a positive recurrent Markov chain, for every and fixed . A locally stable fluid operating point can consequently coexist with eventual stochastic congestion. At , once at least two packets are backlogged, they collide forever, so constant unit retry probability also fails.
A state-dependent retry rule removes this fixed- congestion mechanism. As an ideal benchmark with exact backlog information and known arrival intensity , useThis is backlog-aware ALOHA with arrival-adjusted attempt probabilities. Its total attempt intensity approaches one: the mean old-attempt count is and the new-attempt count has mean . Substitution in the exact success formula yieldsThus the drift tends to . For the Lyapunov function , the drift is bounded above by a negative constant outside a finite set, and the expected one-step backlog is finite at every state. Foster theorem therefore gives positive recurrence. This proves a genuine stochastic stability result for this specified, informed controller. Real transmitters generally observe feedback rather than the exact backlog; estimating the backlog and using a probability of order its reciprocal motivates adaptive ALOHA, but an estimate's dynamics must be included in the state and analyzed before claiming the same stability result.
A different nonconstant rule uses a packet's own collision history. In geometric-attempt exponential backoff, a packet at stage attempts with probability , where . A collision advances every attempted packet by one stage, a success removes its packet, and new arrivals enter stage zero. For definiteness, in this version arrivals join at the end of a slot and first become eligible in the next slot. The full Markov chain state is the sequence of stage populations; the total backlog alone is insufficient. Conditional on that state,These formulas follow from independent attempts and selecting which one packet succeeds. They reduce approximately to for many small probabilities with . The retry probabilities decrease after failure, preventing repeated aggressive attempts by the same packets. Binary exponential backoff instead chooses uniform random counters from expanding finite windows; that counter model requires residual counters as well as collision stages in its state and is not identical to geometric waiting.
Backoff also exposes a distinction between eventual delivery and acceptable delay. In the simplifying model where each attempt independently fails with a fixed probability , the probability of reaching stage is and its mean waiting time is . The mean delay under independent exponential-backoff failures is thereforeAlthough a packet succeeds almost surely whenever , its mean delay can be infinite. In an actual random access network, failures are correlated with the other stage populations, so this fixed- calculation is a diagnostic approximation, not a proof of network stability. These models show why random-access analysis must track the retry rule, feedback information and full state, and assess throughput, stability and delay separately.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Take Poisson process arrivals of rate , independent holding times with the exponential distribution of parameter , unit resource requirement per call, no waiting room, and integer capacity . The occupancy is a birth-death process on with birth rate below and death rate at occupancy . Writing for offered traffic, detailed balance for a continuous-time Markov chain givesAn arrival is lost exactly in state , so Poisson arrivals see time averages proves the Erlang loss formulaThis derivation assumes exponential holding times; the insensitivity of loss networks extends the same formula to independent general holding times with the same mean. For completeness, ; for , set .
A loss network with fixed routing has finitely many resources, capacities , and call types indexed by nonempty subsets of resources. A call of type uses one unit of every resource in for its entire holding time and is accepted only if all are available. Let be the link-route incidence matrix and the type's offered traffic, arrival rate times mean holding time. Different types have independent Poisson processes and independent holding times.
In the reduced-load approximation, availability at distinct resources is treated as independent, and screening at the resources other than is modeled as independent Poisson thinning. The load offered to after that screening isApplying the Erlang loss formula to this isolated-resource load gives the Erlang fixed point approximation, . These equations are an approximation because simultaneous admission induces dependence between resource occupancies, and the screened arrival process need not actually be Poisson.
Here is a proof of existence and uniqueness for positive capacities. Write . Its truncated-Poisson mean is the carried load of an Erlang loss resource,For , differentiating its stationary probabilities givesThe variance is positive and because every state has positive probability. Moreover increases continuously from zero to one, and increases from zero to . Thus has a continuous inverse on .
Use acceptance coordinates and defineHere is strictly increasing, continuous, and tends to as . The convex potential for the Erlang fixed point isEach exponential term is convex, and each integral is a strictly convex function of its coordinate because its derivative is strictly increasing. Hence is strictly convex on the nonnegative orthant. It is also a coercive function: for sufficiently large , , so each integral tends at least linearly to infinity. Therefore attains a unique minimum .
Its partial derivative isAt an interior minimum this derivative is zero. Since , this is exactly . At a boundary coordinate , the one-sided minimizing condition is , whereas the displayed derivative is . Thus and there as well. Conversely every solution of the Erlang fixed point approximation has these derivative conditions and hence minimizes the convex potential. No solution has at positive capacity, since every is finite and for finite . The coordinates therefore give a bijection between solutions and minima, provingIf a capacity is zero, its blocking probability is forced to one. Routes using it contribute zero reduced load to every other resource. Delete those routes and the zero-capacity resources and apply the proof to the remaining network; unused positive-capacity resources have blocking probability zero. This establishes existence and uniqueness also with zero capacities, allowing precisely at those resources.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Assume and regard each line as an individual circulating through three colonies. Then is a closed migration process on . With the coordinate vectors, its nonzero transition intensities areThe memoryless property of the exponential distributions and the independent Poisson process make these counts a continuous-time Markov chain. In particular, the accepted-arrival rate is , not : free lines are availability tokens, not independent callers. An attempted arrival when is lost and causes no state change, so it does not enter the off-diagonal generator.
For the cyclic routing , take equal traffic weights at all colonies. The product-form stationary distribution of a closed migration process gives weightsHere is a direct global balance for a continuous-time Markov chain verification. Set , , , with cyclic subscripts. The predecessor for a transition is , allowed when . The product weights obeySumming these incoming weights over the three edges gives , precisely the outgoing weight. Thus is stationary. The finite state space is irreducible, so this stationary distribution is unique.
Let be the occupied-line count. Summing over its automated-service count givesso . The external Poisson process sees the stationary state probabilities by Poisson arrivals see time averages. A call is lost exactly when , equivalently . Therefore
For two independent identical operators, the middle transition rate becomes : one call receives one operator's service, while two or more calls keep both operators busy. Define and for . The same global balance for a continuous-time Markov chain calculation applies toConsequently the blocking probability in a finite-line sequential-service network isThe subtraction corrects the term, for which rather than . In particular , and when replacing one operator by two does not change blocking.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 34 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A standard Brownian motion is a real stochastic process with almost surely, continuous sample paths almost surely, and independent increments such that has normal distribution whenever . With its completed, right-continuous natural filtration , its Strong Markov property is the following: for every almost-surely finite stopping time , the processis a standard Brownian motion independent of . Here the stopping-time sigma-algebra isIn particular, for every bounded -measurable random variable and bounded Borel functional on the continuous path space,Thus the independence is from the entire stopped past, not only from , and is a statement about the whole future path, not just a single increment.
To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix , , and set and . Continuity of the sample paths makes a stopping time and gives whenever . The stopping time is bounded. Reflect the path after :By the Strong Markov property, the future increments after are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process has the same path law as .
If , reflection changes nothing on and . If , both paths first hit at the same time and . Therefore, for , the following events agree path by path:Indeed, the right-hand endpoint is at least , so the reflected path must have hit before or at ; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to . Equality cases at satisfy the same relation. Since and have the same probability distribution,For , both sides are zero, because and .
For , set in this identity. Continuity implies , and the normal distribution of has no atom at . Splitting according to whether givesBoth random variables are nonnegative. Their tails agree for all , which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies
For and , continuity again gives . Since is a standard normal random variable, the distribution function of the Brownian first-passage time isIt tends to one as and to zero as , proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable ,The value of this ratio on the zero-probability event may be defined arbitrarily. Matching the distribution functions provesFinally, differentiate the distribution function on , using and . The first-passage-time density isand is zero for . Its integral is one by the endpoint limits of , so no missing mass at an infinite hitting time is present.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





