Blocking partition ratio for a loss network 2026-10-14
Let sum the unnormalized occupancy weights over feasible counts. The states admitting another type- call are exactly those feasible under capacities . Poisson arrivals see time averages therefore gives the displayed blocking probability. Take to be zero when the reduced capacities make its feasible set empty.
Represent telephone lines by a closed migration process with free-line, operator and automated-service colonies. Accepted arrivals have rate when a free line exists, operators complete at rate , and automated calls complete at rate . Define andThe product-form stationary distribution of a closed migration process and Poisson arrivals see time averages give the displayed blocking probability. This extends a single-operator model without treating the independent operators as a server with rate when fewer than calls are present.
// Target: probability-and-statistics.bigb
Assume independent stationary Compound Poisson process inputs, preemptive-resume priority for voice, first come first served within each class, capacity , a shared buffer of units of work, packet sizes bounded by , and voice delay gate . Write and . For flows with per-flow effective bandwidths , the continuous-time exponential workload bound givesprovided and . To prove this, couple with the unthinned infinite-buffer aggregate and voice queues driven by the same offered packets. Dropping work reduces both the total and voice workloads under this service discipline. A buffer-fit failure implies total workload greater than , and a voice-gate failure implies voice workload at least . Apply the two bounds and a union bound; Poisson arrivals see time averages converts stationary prearrival probabilities to offered-packet loss fractions. For target losses , choose and , then setThe two effective bandwidth constraints, together with strict aggregate mean-load stability, define a sufficient integer admission region. Voice loss includes the shared-buffer term, even though data packets have lower service priority.
Erlang loss formula Created 2026-10-05 Updated 2026-11-05
The Erlang loss formula gives the blocking probability for a single resource with identical circuits, no waiting room, independent Poisson arrivals of rate and independent exponential holding times of mean . Each admitted call occupies one circuit. Write offered traffic .
The occupied-circuit count is a birth-death process on , with upward rate below capacity and downward rate . Detailed balance gives , hence . By Poisson arrivals see time averages, the arrival blocking probability isThe resource has a finite state space even when ; excess calls are rejected rather than accumulating.[ref]
For , , the weights are , giving blocking and carried load of an Erlang loss resource . A useful recursion avoids large factorials:The insensitivity of loss networks extends the occupancy formula to independent general holding times with the same mean under the standard loss-model assumptions.
Finite-buffer server utilization 2026-10-07
For a work-conserving single-server queue with independent Poisson arrivals, finite buffer and independent identically distributed admitted service times of mean , Poisson arrivals see time averages give admitted rate . Little law for the server alone then gives the displayed busy fraction. The time parameter is the mean service duration, and need not be exponentially distributed.
Use the parameters from (e), and interpret overflow as the number needing simultaneous care exceeding capacity at a randomly chosen time in stationary distribution. The occupancy of the immigration--death process is not fixed at its mean. Detailed balance givesNormalizing yields , so stationary occupancy has a Poisson distribution with mean 25. Thus integer capacity must satisfyThe adjacent tails areSince the tail decreases with , the minimum capacity is . The small excess above at 31 matters; a normal approximation rounded too early can choose the wrong integer.
This is a stationary occupancy criterion. If the event is instead an offered arrival finding at least animals already present in this unrestricted process, Poisson arrivals see time averages gives , whose minimum qualifying capacity is 33. That uses a different event definition. From an initially empty centre, occupancy at a finite time is Poisson distributed with mean , so the stationary criterion also bounds the fixed-time overflow probability during initial filling. A probability of ever exceeding capacity over an unlimited future is a different question: this irreducible recurrent process will eventually exceed every finite capacity with probability one. If instead arrivals are refused when all places are occupied, that changes the model to an loss network, whose blocking probability is not the unrestricted occupancy tail calculated here.
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 73 1 Solution Created 2026-10-03 Updated 2026-10-14
A closed migration process is a continuous-time Markov chain with state , conserved population , and transition ratesHere , for , and is a fixed stochastic routing matrix. Take for convenience; self-routing can instead be omitted from the actual jumps. Assume irreducible routing. Let positive traffic weights satisfy . Define , . The product-form stationary distribution of a closed migration process isTo prove it, an incoming transition to comes from , and is possible only if . The weight ratio givesSumming over and using the traffic equations gives . Summing then over equals , the outgoing probability flux, proving global balance for a continuous-time Markov chain. The state space is finite and irreducible, so this normalized stationary distribution is unique. Detailed balance is not required; a directed routing cycle, for example, is not reversible.
For the switchboard, make each of the lines one circulating individual. Use colonies for free lines, calls waiting for or receiving the operator's connection service, and already connected calls. The transitions form the cycle , with departure ratesThe first rate is , not : incoming calls form one external Poisson process, not one per free line. An arrival when changes no state and is counted as lost. Exponential connection and conversation times make this the required continuous-time Markov chain; only one call receives the operator's service at a time, whereas every connected call independently completes at rate .
The cyclic traffic weights can all be chosen equal to one. Multiplying all unnormalized weights by the same gives, for ,If is the number of occupied lines, sum over the possibilities for the connected-call count:Thus the normalizer is and the full-state probability is . By Poisson arrivals see time averages, this is also the long-run fraction of attempted calls rejected:One can also see the arrival-rate argument directly: the lost-call counting process has conditional intensity , so its equilibrium rate is ; dividing by the total attempted-call rate gives the same fraction. As an independent check, stationary flow conservation in a finite-line switchboard gives .
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 34 1 Solution Created 2026-10-03 Updated 2026-10-14
Use one particle for each telephone line, including unused lines. Let be the number of free lines, the number of callers waiting for or being checked by an operator, and the number using automated service. Then . These are the three colonies of a closed migration process, with directed cycle and departure ratesRejected attempted calls leave the state unchanged. They must not be represented as extra customers in the waiting stage.
Equivalently the state is with . Its transitions areThe directed cycle has equal traffic weights; choosing each weight to be gives the unnormalized product-form stationary distribution of a closed migration processWe can verify global balance for a continuous-time Markov chain directly. Weighted incoming transitions from , and contribute, respectively,Their sum equals the weight times the outgoing rate. This proves stationarity after normalization, without falsely asserting reversibility of the directed migration cycle.
For occupied lines, summing over the automated population givesThe normalizing constant is . The attempted calls form an independent Poisson process, so Poisson arrivals see time averages: the rate of attempted arrivals seeing a full state is times its stationary probability, and division by the total attempted-arrival rate gives the loss proportion. ConsequentlyThe numerator is essential; the PDF contains it even though the converted TeX loses it.
With two independent operators, the total check-completion rate is . In particular it is only when one caller is present. DefineThe human-stage weight becomes , while the free and automated weights are unchanged. The same global-balance calculation applies using these departure rates. ThusThis is the blocking probability in a finite-line sequential-service network with two operators. It remains valid for , when every attempted call is lost; for it coincides with the single-operator answer.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 34 2 i Solution Created 2026-10-03 Updated 2026-10-14
A loss network admits a call only when all the resources it requires have available capacity. Calls which fail admission disappear rather than waiting. Under fixed routing, class has a fixed nonzero integer resource-requirement vector , Poisson process rate , and independent exponential distributions with parameter . Let have columns and let be the resource-capacity vector. The feasible call counts areWrite for the offered load. On , the Markov transition rates are if the new state is feasible, and .
The product-form stationary distribution of a loss network isIndeed, whenever is feasible,These pairwise equalities give detailed balance, including the truncated boundary: there is no transition to an infeasible state in either direction. The finite reachable chain is irreducible under positive arrival and holding rates, so this is its unique stationary distribution. It can also be viewed as independent Poisson offered populations conditioned on all capacity constraints. Conditioning usually makes the actual resource occupancies dependent.
An arriving call of class sees this stationary distribution by Poisson arrivals see time averages. Its acceptance probability iswhere a partition function with a negative capacity is zero. This is the blocking partition ratio for a loss network. Thus its blocking probability is , admitted arrival rate is , and mean number present is , by balancing admitted births with departures. With a single unit-demand resource, the formula reduces to the Erlang loss formulaThe stationary count law is also insensitive to the shape of independent holding-time distributions in the standard fixed-routing model when their means are unchanged. With nonexponential holding times, counts alone need not be Markov; residual holding times are included in the state for this insensitivity assertion. State-dependent admission controls and alternative routing do not automatically preserve the same simple product form.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 36 4 b Solution 2026-10-14
The capacity and quality targets alone do not determine flow counts: the per-flow traffic statistics must also be supplied. The following explicit model gives a computable sufficient region, with genuine upper bounds on both loss fractions.
Measure queue workload and buffer size in bits. Denote capacity by , shared buffer size by , voice delay limit by , target voice loss by , and target data loss by , with . Let there be voice flows and data flows. Model each class- flow, , by a stationary Compound Poisson process with packet rate and positive independent packet sizes , and assume independence across flows and marks. Use a work-conserving preemptive-resume priority queue with a shared buffer, with voice priority and first come first served within each class. This preemptive or fluid approximation makes the predicted voice waiting time exactly , where is the remaining voice queue workload just before arrival. Assume packet sizes are bounded by a known and interpret the buffer gate as a packet-fit test; rejecting packets which do not fit is the packet version of the full-buffer rule.
For one flow the Compound Poisson process formula givesFor fixed-size packets of size , substitute . Estimate the packet rate and size law from measurements or a declared traffic contract. Also require the strict stability inequalityDefine and . Couple the switch with an unthinned infinite-buffer aggregate queue and an unthinned infinite-buffer voice-only queue, both driven by the same offered packets and both served at rate . Under the preemptive service discipline, dropping arrivals can only decrease both the total queue workload and the voice queue workload. Thus total switch queue workload and voice queue workload satisfy and in the stationary coupling. A packet-fit loss implies , and a voice-delay rejection implies .
Apply the continuous-time exponential workload bound to the two comparison queues. For any positive satisfyingthe stationary loss-event probabilities obeyThe second inequality is a union bound: voice can be lost either at the shared buffer or at its delay gate. Data congestion therefore contributes to voice loss despite its lower service priority. Poisson arrivals see time averages applies to each offered packet stream, whose future arrivals are independent of the prearrival state; the stationary event bounds are consequently bounds on the offered-packet loss fractions. Voice packets that are admitted have queueing delay below , because later voice packets join behind them and data work cannot delay them in this model.
To turn the bounds into flow counts, allocate loss budgetsFor example, and also work; equality with is harmless. The required sufficient effective-bandwidth admission region with a voice delay gate isIt ensures and . A simple enumeration isdiscarding negative bounds and pairs failing strict mean-load stability. The formulas assume positive-rate nonzero-size flows. Optimize a chosen revenue or flow-count objective over these integer pairs. Searching over the budget split can enlarge the sufficient region. For a bit-fluid buffer gate with no packet-fit issue, can be replaced by .
Real nonpreemptive packet service needs an additional residual-service allowance or an explicit priority queue workload analysis: a voice packet may have to wait for the data packet already in service. Burst-correlated voice sources also require richer descriptors, such as measured finite-time effective bandwidths or a Markov-modulated source model. For such inputs, additivity still holds for independent flows, but the independent-increment supermartingale bound is not automatic; use a valid sample-path large deviation principle or a model-specific overflow bound, with prefactors or a safety margin when using asymptotics. If packet arrivals do not form a Poisson process, loss fractions must be assessed at arrival epochs rather than inferred solely from time-average queue workload probabilities. These qualifications explain both how to calculate an admission region from specified traffic statistics and why the five switch/QoS parameters by themselves cannot supply a numerical answer.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 34 2 Solution Created 2026-10-03 Updated 2026-10-14
For a standard loss network, let type- calls arrive as independent external Poisson processes of rates . Each accepted call holds units of resource for a holding time with an independent exponential distribution of parameter , then releases them. Capacities and requirements are nonnegative integers. Rejected calls leave immediately and do not queue. With fixed routes, the feasible count set isFor a call of each type using at least one finite-capacity resource, this set is finite. The count continuous-time Markov chain has accepted birth rate and death rate . Put andOn every admitted edge, , so . This proves detailed balance and the product-form stationary distribution of a loss network:It is unique when all relevant arrival rates are positive, since departures lead to zero and every feasible state can be built from zero through feasible births.
An external Poisson process arrival sees this stationary prearrival law by Poisson arrivals see time averages. Indeed its constant conditional arrival rate makes the expected count of arrivals in any state set equal to times the time spent there. A type- arrival is accepted exactly in , where is its resource column. Thus the blocking partition ratio for a loss network isSet to zero when reduced capacities have an empty feasible set.
For the triangle, index call types by their endpoint pairs and give physical links integer capacities . We assume each call needs one circuit on every traversed link; arrivals of the three types are independent Poisson processes, and holding times have independent exponential distributions with parameters determined by endpoints alone. Calls may be rearranged instantaneously and without cost among their direct and two-link paths, without restarting or changing their holding times. Admit a call if any simultaneous arrangement of all calls is feasible. These assumptions make the three type counts Markovian even though the physical route assignments may change.
The cut feasibility for a rearrangeable triangle gives the exact feasible count set. Define virtual endpoint capacitiesEvery endpoint call must use at least one of the two links incident to that endpoint, so feasibility requiresThese cut inequalities are also sufficient. If each count fits its direct-link capacity, route every call directly. Otherwise at most one count exceeds its own direct capacity: two excesses would violate the cut inequality at their shared endpoint. If, for example, , route such calls directly and the excess through node three. The other link usages are and , and the first two cut inequalities bound them by and . The other cases are cyclic permutations. Thus the count process is exactly a virtual fixed routing loss network in which a pair call consumes one unit of each endpoint resource.
WriteThe exact stationary distribution count probabilities are these weights divided by . The three arriving-call blocking probabilities are thereforeEquivalently, a type- call is blocked on the union of the events and , with the other pairs treated cyclically. The partition ratios count their union without double-counting intersections. These expressions are exact for the stated rearrangeable triangular loss network; a restricted rearrangement policy would require a different admission model.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 35 1 Solution 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 35 2 Solution 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 2009 iii Paper 30 2 Solution Created 2026-10-03 Updated 2026-10-14
For a fixed routing loss network, let be finite integer resource capacities and the integer resource requirement of one route- call. Assume each route uses a resource, independent Poisson processes of calls with rates , independent exponential distributions of holding times with parameters , and immediate rejection when any required resource is unavailable. There is no waiting. The continuous-time Markov chain of call counts has feasible setPut andThe ratios of adjacent weights satisfy whenever the arrival is feasible. Thus detailed balance proves the product-form stationary distribution of a loss network,An arriving route- call is admitted precisely when . By Poisson arrivals see time averages, its exact blocking probability isDefine to be zero if a capacity is negative. This is an exact finite sum, not an independence approximation for resource blocking events.
For the triangle, denote the physical link capacities by and the numbers of calls between the pairs by . Assume unit capacity per call on each traversed link, unrestricted instantaneous rearrangement of existing calls, no interruption or extra resource cost during rearrangement, and independent exponential distributions of holding times whose parameters depend on the endpoint pair but not on the chosen path. Arrivals for each pair are independent Poisson processes, and admission occurs whenever some routing of all calls is feasible. These assumptions make the count vector a Markov process even though individual paths can change.
The necessary cut constraints areEach counts calls that must cross the two links separating one node from the others. They are also sufficient. If every pair count is at most its direct capacity, route all calls directly. Otherwise at most one pair can exceed its direct capacity: two such excesses would contradict their pairwise cut constraint. Suppose it is , and put . Route of these calls directly and divert the remaining through node . Route the other calls directly. The loads on links and are respectively and by the two cut constraints involving . This is an integer routing of every call. The other cases follow by relabelling.
Consequently the rearrangeable triangular loss network is equivalent, at the level of call counts and blocking, to a fixed routing loss network with three virtual node resources:The columns correspond to , and a call uses its two endpoint resources. Its normalizer isWith now indexing virtual resources, the three exact answers areThe preceding detailed balance proof applies because departures occur at rates regardless of the current routing. Without unrestricted rearrangement, feasibility can depend on the existing path assignments and this equivalence need not hold.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 32 1 Solution Created 2026-10-03 Updated 2026-10-14
For a stable system in which entering customers eventually leave, Little's law isHere is the long-run mean number of customers in the chosen system, is its actual entry rate, and is the mean customer sojourn time. The arrival rate counts admitted customers, not rejected attempts. One way to see the identity is to integrate the customer count over time: each customer's time in the system contributes exactly that much area. Dividing by elapsed time gives entry rate times mean customer sojourn time, with negligible endpoint terms under the usual stability and integrability assumptions.
For the server alone in a stationary M/M/1 queue, the customer count is the busy indicator. Customers enter this subsystem when their service begins; in a stable, loss-free queue its entry rate equals . Their mean time in this subsystem is the mean service time . Thus , with stability requiring . In this paper denotes a mean duration, so the exponential service rate is .
For finite-buffer server utilization, assume the server is work conserving and admitted customers are eventually served, with finite mean service time. Poisson arrivals see time averages, so an offered arrival is rejected with probability . Hence the admitted arrival rate, and therefore the service-entry rate, or queue throughput, is . Apply Little's law to the server alone again. Its mean population, or server utilization, is , and its mean customer sojourn time is , giving . Neither argument requires exponential service times in the finite-buffer system: Poisson arrivals are used for the blocking probability, while the service calculation needs only the mean and the stated independence. Applying the offered rate directly to this lossy system would miss the admission factor.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 32 2 Solution Created 2026-10-03 Updated 2026-10-07
For a single resource, assume unit-capacity calls arrive as a Poisson process of rate , holding times have independent exponential distributions with mean , and a call is rejected when all units are occupied. Let . Its occupancy is a birth-death process on , with birth rate below capacity and death rate in state . Detailed balance for a birth-death process givesBy Poisson arrivals see time averages, the Erlang loss formula isThis derivation assumes exponential holding times; the standard insensitivity result extends the same formula to independent holding times of the same mean, but is not needed here.
A loss network with fixed routing has finitely many resources , capacities , and call types with a fixed nonempty set of resources. Type has Poisson arrivals of rate , independent holding times of mean , and offered load . It is accepted only if every resource on its route has a free unit, and otherwise is lost. In the displayed equations use the unit-incidence matrix for and zero otherwise. The equations concern this unit-demand model, rather than arbitrary multi-unit requirements.
The Erlang fixed point approximation replaces the correlated resource availabilities by independent ones. A type- call survives blocking at resources other than with approximate probability . Treating this filtering as Poisson thinning gives the reduced offered loadApply the single-resource formula to obtain . Independence and Poisson thinning here are approximations; no such approximation is claimed for the exact network's joint stationary distribution.
Assume first . The right side is a continuous map from into itself, so the Brouwer fixed-point theorem gives existence. To prove uniqueness, let be the carried load of an Erlang loss resource, also the mean of the truncated Poisson occupancy. Differentiation yieldsThus increases continuously from zero to one and increases from zero to .
Write , and define and , with . Each is continuous and strictly increasing. A fixed point satisfiesThese are precisely the stationary equations for the convex potential for the Erlang fixed pointThe first term is convex; the second is strictly convex because each strictly increases. Hence is strictly convex. Its gradient cannot vanish at two distinct points: the difference of gradients dotted with the difference of points is strictly positive, with a positive contribution from every changed coordinate in the integral term. This also covers boundary coordinates , using the right derivative there. Every fixed point has , since its offered load is finite, so the change of variables is valid. There is exactly one fixed point. If a capacity is zero, its blocking probability is one; delete it and all routes using it before applying the argument to the remaining positive capacities. Unused resources have blocking probability zero.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 37 1 i Solution Created 2026-10-03 Updated 2026-10-07
A loss network models calls that need several resources simultaneously and are rejected, rather than queued, when insufficient capacity remains. Take finite resource and route sets. Let be the integer amount of resource required by a route- call, its capacity, andUnder fixed routing, each arriving call has a predetermined resource requirement. Take independent Poisson processes of rates and independent holding times with exponential distribution of rates . A feasible arrival changes to at rate ; a departure changes it to at rate . Put and assume each route uses a finite positive-capacity resource, so the state space is finite.
The product-form stationary distribution of a loss network isFor any feasible adjacent pair,These detailed balance equations prove stationarity and make the process a reversible Markov chain. Equivalently, Independent random variables with Poisson distributions of means are conditioned on satisfying the joint capacity constraints. The conditioning makes resource occupancies dependent even though the unconstrained counts are independent.
By Poisson arrivals see time averages, a route- arrival sees acceptance probability , interpreting the numerator as zero for a negative capacity. Hence its blocking probability is and the expected value of its number in service is . This connects a stationary occupancy law to observable rejection and carried traffic.
The insensitivity of loss networks extends this occupancy formula to independent general holding-time distributions with the same expected values, under the usual fixed resource requirements and admission rule. Counts alone then need not be a Markov chain; residual holding times belong in a Markov description. The invariant occupancy formula survives. This is useful because detailed call-duration distributions can be difficult to estimate, while their means are much easier to measure.
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 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 ii Paper 3 27J Solution Created 2026-09-24 Updated 2026-10-03
Immediately after departure , either and one of those customers starts the next service, or and the next arrival both initiates service and is not counted among those waiting after it. During that service further customers arrive. Thus the embedded departure chain of an M-G-1 queue obeys
Conditional on the next service time , the Poisson process property givesThe law of total expectation and law of total variance therefore giveand
In equilibrium let have the common distribution of and put . The fresh pair is independent of . Taking expectations in the recursion givesBecause and , stationarity of the second moment givesSolving,
In stationarity, level crossing together with Poisson arrivals see time averages identifies this as the mean number in the shop. The Little law gives , where is waiting time before service. Since ,This is the Pollaczek-Khinchine mean formula.