Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 213 / 2 / Solution

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$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 $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ 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 $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. 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 $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. 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 $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.