Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 34 (Stochastic Networks)

Use finitely many colonies and let $n_i$ be the population of colony $i$. An open migration process has independent external Poisson processes of rates ${\nu }_i$, local total departure rates ${\varphi }_i(n_i)$, and fixed routing probabilities $p_{ij}$ to other colonies and $p_{i0}$ out of the system. Here ${\varphi }_i(0)=0$, $0<{\varphi }_i(k)<\infty$ for $k\ge 1$, $p_{ii}=0$ and $p_{i0}+{\sum }_j{p}_{ij}=1$. The continuous-time Markov chain has intensitiesRequire the routing matrix $P$ to be transient: every individual eventually exits. For finitely many colonies this is equivalent to every colony having a directed path to an exit. Restrict to colonies reachable from external arrivals, so their traffic rates are positive and the relevant chain is irreducible. The total population cannot exceed its initial value plus the number of external arrivals, so on any finite time interval it is bounded by a finite random number. There are only finitely many states below that bound and finite rates in each, proving nonexplosion even when the departure functions grow rapidly.

The traffic equations of an open migration process, in row-vector form, areTransience makes the inverse ${\sum }_{k\ge 0}{P}^k$ finite. DefineProvided every $Z_i$ is finite, the candidate product-form stationary distribution of an open migration process isThe normalizability condition is exactly $Z_i<\infty$ for every active colony. For example, constant total service ${\varphi }_i(k)={\mu }_i$ for $k>0$ requires ${\alpha }_i<{\mu }_i$ and gives a geometric distribution; independent individual departures ${\varphi }_i(k)=k{\mu }_i$ give a Poisson distribution of mean ${\alpha }_i/{\mu }_i$. In the irreducible case the normalizable invariant law is the unique equilibrium. If the weights cannot be normalized, no stationary probability law exists, by uniqueness up to scale of invariant measures for an irreducible recurrent chain.

We establish both stationarity and the time reversal of an open migration process assertion by adjacent-weight calculations. DefineThe identity $b_i(k){\varphi }_i(k)={\alpha }_i{b}_i(k-1)$ givesThus the proposed time reversal of an open migration process retains the local service functions and hasThe traffic equation for colony $i$ implies $p_{i0}^{\ast }+{\sum }_j{p}_{ij}^{\ast }=1$. Summing all traffic equations also gives ${\sum }_i{\nu }_i^{\ast }={\sum }_i{\nu }_i$. Therefore the total outgoing rate from every state is the same for $q^{\ast }$ and $q$:Consequently ${\sum }_{m\ne n}\pi (m)q(m,n)=\pi (n){\sum }_{m\ne n}q(n,m)$, proving global balance for a continuous-time Markov chain. The same weight recurrence gives ${\mathbb{E}}_{\pi }{\varphi }_i(n_i)={\alpha }_i$, so the stationary mean total jump rate is finite. The candidate is a stationary distribution, and the displayed intensities are indeed its stationary time reversal of a continuous-time Markov chain. Reverse routing is also open: reverse an original arrival-to-colony path to obtain a path to a colony with $p_{i0}^{\ast }>0$.

For the last request, let $S$ be all colonies reachable by routing from $k$, including $k$ itself. The no-return-path hypothesis gives $j\notin S$. By construction no routing edge leads from $S$ to its complement $C$. The populations in $C$ therefore evolve autonomously as an open migration process, with moves into $S$ treated as exits. Its stationary marginal is the corresponding product of the factors above. Retain the original destination as a mark on each such exit.

In this autonomous process, a marked exit $j\to k$ has intensity ${\varphi }_j(n_j)p_{jk}$. The same reversed-weight calculation makes its reverse a marked external immigration channel of constant rate ${\alpha }_j{p}_{jk}$. External immigration channels can be constructed as independent Poisson processes. Stationary reversal of a two-sided Poisson process preserves its law, so reversing this immigration channel givesThis Poisson migration stream without a return path argument is needed because a general internal migration stream in a network with feedback is not automatically Poisson. A zero routing probability gives the empty Poisson stream of rate zero.

For a standard loss network, let type-$r$ calls arrive as independent external Poisson processes of rates ${\nu }_r$. Each accepted call holds $A_{jr}$ units of resource $j$ for a holding time with an independent exponential distribution of parameter ${\mu }_r$, then releases them. Capacities $C_j$ 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 ${\nu }_r{1}_{\{n+e_r\in \mathcal{F}(C)\}}$ and death rate ${\mu }_r{n}_r$. Put ${\rho }_r={\nu }_r/{\mu }_r$ andOn every admitted edge, $w(n+e_r)/w(n)={\rho }_r/(n_r+1)$, so $w(n){\nu }_r=w(n+e_r){\mu }_r(n_r+1)$. 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 ${\nu }_r$ times the time spent there. A type-$r$ arrival is accepted exactly in $\mathcal{F}(C-A_r)$, where $A_r$ is its resource column. Thus the blocking partition ratio for a loss network isSet $Z$ 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 $C_{12},C_{23},C_{31}$. 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 ${\mu }_{12},{\mu }_{23},{\mu }_{31}$ 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, $n_{12}>C_{12}$, route $C_{12}$ such calls directly and the excess $d=n_{12}-C_{12}$ through node three. The other link usages are $n_{31}+d$ and $n_{23}+d$, and the first two cut inequalities bound them by $C_{31}$ and $C_{23}$. 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 $Z$. The three arriving-call blocking probabilities are thereforeEquivalently, a type-$12$ call is blocked on the union of the events $n_{12}+n_{31}=K_1$ and $n_{12}+n_{23}=K_2$, 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.

Use finite sets of links $J$, source-sink pairs $S$, and admissible routes $R$, with at least one route for each pair. Route $r$ carries aggregate flow $x_r$. The link-route incidence matrix has $A_{jr}=1$ if route $r$ uses link $j$ and zero otherwise; repeated traversals, if allowed, are counted with their multiplicity. The source-sink route incidence matrix has $H_{sr}=1$ if $r$ serves pair $s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives source-sink demands. Write $R_s$ for the routes serving $s$ andA Wardrop equilibrium routes positive flow only on minimum-delay routes:This is a nonatomic equilibrium: an individual infinitesimal user's route change does not alter the aggregate link delays.

For fixed nonnegative demand $f$, the feasible route-flow set $\{x\ge 0:Hx=f\}$ is a nonempty product of finite-dimensional simplexes and hence a compact set. The Beckmann potentialis continuous, so it attains a minimum over this feasible set. Each primitive is a strictly convex function, since its derivative $D_j$ is continuous and strictly increasing. Its route-flow derivative is exactly the corresponding route delay:If a minimizer had positive flow on $r$ and a lower-delay alternative $q\in R_s$, transferring a small amount from $r$ to $q$ would give directional derivative $L_q-L_r<0$, contradicting minimality. Hence every minimizer is a Wardrop equilibrium.

Conversely, let $x$ be a Wardrop equilibrium and $z$ any feasible competitor. Convexity givesFor each $s$, subtract ${\lambda }_s$ inside this sum. The demand constraint makes ${\sum }_{r\in R_s}{\lambda }_s(z_r-x_r)=0$, and the remaining terms are nonnegative: used routes have $L_r-{\lambda }_s=0$, while unused routes have $x_r=0$, $z_r\ge 0$ and $L_r-{\lambda }_s\ge 0$. Thus $V(Az)\ge V(Ax)$. We have proved both existence and the optimization characterization.

Strict convexity in the link vector makes $y$ unique: two different minimizing link vectors would have a feasible midpoint of strictly smaller potential. Thus link delays and the minimum route delays at the Wardrop equilibrium are also unique. The route vector need not be unique, because different route decompositions may have the same $Ax$ and $Hx$. For example, two successive stages with two parallel links at each stage have four routes. With unit demand and link delay $D(u)=u$, the vectorsall give throughput $1/2$ on each of the four links and delay one on every route. This exhibits route-flow nonuniqueness at a Wardrop equilibrium. The equilibrium link throughputs are unique; the individual route flows need not be.

For elastic demand, make the usual physical assumptions explicit: delays are nonnegative on $[0,\infty )$, every route is nonempty, and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous and strictly decreasing. PutThe limit exists by monotonicity; it need not be zero. The inverse demand function $P_s$ is continuous, strictly decreasing, satisfies $P_s(M_s)=0$, and tends to infinity as $v\downarrow {\ell }_s$.

Choose any reference $b_s\in ({\ell }_s,M_s)$ and use elastic-demand utility with an interior reference:Each utility is strictly concave, with derivative $P_s$. A reference inside the range avoids a potentially divergent integral from zero. For instance, $B(\lambda )=(1+\lambda {)}^{-1/2}$ has inverse $v^{-2}-1$, whose integral from zero is infinite, although the displayed reference-point primitive is finite at every interior demand.

Give $G_s$ its limiting value at ${\ell }_s$, which may be $-\infty$, and extend it by $-\infty$ outside $[{\ell }_s,M_s]$. This encodes the physical demand range in the objective. After substituting $y=Ax$, $f=Hx$, minimizeIts effective feasible set is contained in $\{x\ge 0:{\ell }_s\le (Hx{)}_s\le M_s\}$, a nonempty compact set. The objective is lower semicontinuous, including a possible value $+\infty$ at a lower endpoint, and is finite when all demands equal their interior reference values. It therefore has a finite-valued minimizer.

The boundary exclusion for elastic Wardrop demand shows that every minimizing demand is interior. If $f_s={\ell }_s$ and the utility there is finite, adding a small flow $h$ on any route serving $s$ costs at most a bounded constant times $h$, while the utility gain is at least $h{P}_s({\ell }_s+h)$, whose ratio to $h$ tends to infinity. This decreases the objective. If that endpoint utility is $-\infty$, a finite minimizer cannot occur there in the first place. At $f_s=M_s>0$, choose a used route. Its delay is strictly positive, since its nonempty links have positive throughput and strictly increasing nonnegative delays. Removing a small amount of its flow saves a positive first-order cost, whereas the utility loss is $o(h)$ because $P_s(M_s)=0$. This also decreases the objective. Hence ${\ell }_s<f_s<M_s$ for every pair.

The interior-demand route derivatives are nowAt a minimizer they are zero on positive route flows and nonnegative on zero route flows, by increasing or decreasing a single route flow. Since $f_s>0$, some route is used, soThese are precisely the elastic-demand Wardrop equilibrium conditions. Conversely, those conditions give the same nonnegative directional derivative for every competitor; convexity then proves global minimality. The equivalent constrained form is the requested minimization of $V(y)-G(f)$ with $Hx=f$, $Ax=y$, $x\ge 0$. Strict convexity determines both $y$ and $f$ uniquely, while their route decomposition can still be nonunique.

Only active routes, those with $n_r>0$, enter the proportional fairness inequality and the weighted logarithmic utility. Their rates must be positive; inactive routes have no per-flow rate to determine and may be assigned zero. This convention removes otherwise meaningless terms $0\log 0$ and $0/0$.

For positive active rates, concavity of the logarithm gives, for any positive feasible competitor $y$,Thus the proportional fairness inequality proves that $x$ maximizes the log-utility objective. A competitor with an active zero rate has utility $-\infty$ and cannot improve it. Conversely, if $x$ maximizes utility, the right directional derivative along $x+\epsilon (y-x)$ at $\epsilon =0$ is nonpositive, giving exactly that inequality. Positive resource capacities and finitely many active routes allow a feasible allocation with every active rate positive, so an optimizer cannot have an active zero rate. Strict concavity gives uniqueness of the active rates. Hence proportional fairness is equivalent to the stated log-utility maximization.

Index the four adjacent-pair routes in cyclic order and put $z_i=n_i{x}_i$, the aggregate service on route $i$. The resource constraints areThey involve every odd-even route pair, so they are equivalent toFor given maxima, increasing each active odd service to $p$ and each active even service to $q$ remains feasible and improves utility. Apart from the constant $-{\sum }_i{n}_i\log n_i$, the objective therefore reduces toWhen both groups are present the constraint is tight, and differentiation gives $P/p=Q/(1-p)$. If one group is empty, the other receives unit aggregate service on each of its active routes. Thus the opposite-route reduction for a proportionally fair four-cycle yields, with $T=P+Q>0$,Inactive rates can be set to zero, including every rate in the empty state. In particular $n_{\{1,2\}}{x}_{\{1,2\}}=(n_{\{1,2\}}+n_{\{3,4\}})/{\sum }_r{n}_r$ whenever that route is active. This proves the required formula even when other routes are empty.

For the flow-level network model, an active document's residual size retains an exponential distribution with parameter ${\mu }_i$. Receiving service at rate $x_i(n)$ gives completion intensity ${\mu }_i{x}_i(n)$, so $n_i$ independent active documents give total completion intensity ${\mu }_i{n}_i{x}_i(n)$. Consequently the population continuous-time Markov chain hasAll death intensities are zero at $T=0$. Their total is bounded by ${\sum }_i{\mu }_i$, and the total arrival rate is constant, proving nonexplosion.

Put ${\rho }_i={\nu }_i/{\mu }_i$. The required stationary weight uses a binomial coefficient, as printed in the PDF; the converted TeX incorrectly rendered it as an ordinary fraction. DefineFor an odd route, the neighboring binomial coefficient ratio iswhile its death intensity at the neighboring state is ${\mu }_i(P+1)/(T+1)$. Their product is ${\nu }_i$, so $w(n)q(n,n+e_i)=w(n+e_i)q(n+e_i,n)$. For an even route, replace $P$ by $Q$ in the same calculation. This proves detailed balance and the stationary law of a proportionally fair four-cycle:A finite $B$ is essential for this expression to be a probability distribution. We determine its exact convergence condition rather than asserting stationarity for arbitrary arrival rates. LetGrouping the states by odd and even population givesWith $A=\max (a,c)$ and $E=\max (b,d)$, the bounds $A^p\le h_p(a,c)\le (p+1)A^p$ and $E^q\le h_q(b,d)\le (q+1)E^q$ show that convergence holds exactly when $A+E<1$. For necessity, the lower bound sums to ${\sum }_{k\ge 0}(A+E{)}^k$, which diverges at or above one. For sufficiency, choose slightly larger $A^{\prime },E^{\prime }$ with $A^{\prime }+E^{\prime }<1$; the polynomial factors are absorbed into constants times $(A^{\prime }{)}^p(E^{\prime }{)}^q$, giving a convergent geometric generating series. Thus the stability region for the reversible four-cycle flow network isEquivalently, the offered load on each resource, ${\rho }_1+{\rho }_4$, ${\rho }_1+{\rho }_2$, ${\rho }_2+{\rho }_3$, or ${\rho }_3+{\rho }_4$, is strictly below its unit capacity. For positive arrival rates this finite normalizing constant gives the unique stationary distribution of the irreducible process. At or beyond the boundary, the displayed invariant weights are not summable and do not define a stationary probability law.

If an explicit normalizing constant is desired, $h_p(a,c)=(a^{p+1}-c^{p+1})/(a-c)$ for $a\ne c$, and ${\sum }_{p,q}\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)u^p{v}^q=(1-u-v{)}^{-1}$. Hence for $a\ne c$, $b\ne d$ in the stable region,Equal-parameter cases are obtained by continuity or directly from the positive series. In particular the empty-traffic limit is $B=1$.