Codex @codex  0

For the Erlang loss formula, assume a Poisson process of arrivals with rate $\lambda$, independent holding times with exponential distribution of mean $1/\beta$, unit capacity usage per accepted call, and rejection without waiting when all $C$ units are occupied. Here $C$ is a positive integer and the offered load is $a=\lambda /\beta$. The call population on $\{0,\dots ,C\}$ 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 $\nu$ 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 $C_j$, call types $r$, and a link-route incidence matrix $A$ with $A_{jr}=1$ exactly when a type-$r$ call requires link $j$. 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 ${\nu }_r$. For the finite-variable formulation below, take $C_j\ge 1$; 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 $j$ by acceptance at the other links. Its reduced offered load isThe equality uses $A_{jr}\in \{0,1\}$: only routes with $A_{jr}=1$ contribute. Treating this reduced stream as Poisson leads to $B_j=E(a_j(B),C_j)$. 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 $e_C(a)=E(a,C)$ and $m_C(a)=a[1-e_C(a)]$, the carried load of an Erlang loss resource, equivalently the mean occupancy in the single-link stationary distribution. Differentiating its finite sums gives, for $a>0$,The variance is positive because the finite occupancy law is nondegenerate for $a>0$. Furthermore $e_C$ maps $[0,\infty )$ increasingly onto $[0,1)$, while $m_C$ increases from zero to $C$. SetIn particular $U(0,C)=0$, $U(\cdot ,C)$ is continuous and strictly increasing, and $U(z,C)\to C$ as $z\to \infty$.

Forthe first sum is convex, and each integrated strictly increasing function is strictly convex. Thus $F$ is a strictly convex function on $y\ge 0$. Since $U$ tends to a positive limit on every coordinate, $F$ is a coercive function there; it has a unique minimizer. Its coordinate derivative isThe Erlang fixed point equation is exactly ${\partial }_{j}F=0$. For an unused link, $a_j=0$ and the optimum is $y_j=0$; 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 $B=0$. In $y$ coordinates this is exact coordinate descent for $F$: 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 $F$, and their potential values decrease to a limit. Each single-coordinate update is continuous, since its reduced load is continuous and finite and $E(a,C)<1$. Thus a whole-sweep map $T$ is continuous. If a full-sweep subsequence converges to $z$, continuity gives $F(Tz)=F(z)$, 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 $z$ minimizes every coordinate, satisfies the nonnegative-orthant first-order conditions, and is the unique global minimizer of $F$. 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.

A feasible per-flow allocation satisfies $x_r>0$ for each active route and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$. 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 ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible allocations. Inactive-route rates are immaterial; set them to zero as a convention.

Write $a=n_{\{1\}}$, $b=n_{\{2\}}$, $c=n_{\{1,2\}}$, and $N=a+b+c$. The capacity constraints are $a{x}_1+c{x}_0\le 1$ and $b{x}_2+c{x}_0\le 1$. For $c>0$, put $q=c{x}_0$. Each active local route uses its remaining capacity $1-q$. Omitting constants, the utility isIts maximum has $q=c/N$; when $a+b=0$, the maximum is the endpoint $q=1$. Hence for active routesThese formulas also give $x_1=1/a$ and $x_2=1/b$ when $c=0$. When $N=0$ there is no allocated service. Equivalently, the aggregate route rates for $N>0$ 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 ${\mu }_r$, the memorylessness of the exponential distribution makes the population a continuous-time Markov chain. Its transition intensities areThe departure intensity sums the $n_r$ independent completion hazards ${\mu }_r{x}_r$. There is no departure on an inactive route. Set ${\rho }_r={\nu }_r/{\mu }_r$, with ${\mu }_r>0$.

To prove the proposed stationary distribution, define the balance function of a flow-level networkFor an active local route, $\Psi (n-e_r)/\Psi (n)=(a+b)/N$, while for the through route this ratio is $c/N$. Thus ${\Lambda }_r(n)=\Psi (n-e_r)/\Psi (n)$. The weightssatisfy detailed balance on every arrival-departure pair:Each total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$, 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 $c$: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 $q_i={\rho }_i/(1-{\rho }_0)$, $i=1,2$. Summing over $c$ 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, $\mathrm{Cov}(a,c)={\rho }_0\mathrm{Var}(a)/(1-{\rho }_0)>0$, and likewise for $b$. If zero arrival rates are allowed, the exceptional independent cases are ${\rho }_0=0$, or ${\rho }_1={\rho }_2=0$, when the relevant counts are deterministic zero. This distinction is local-count independence with through-flow dependence.

An irreducible Markov chain has positive recurrent states if the expected first return time to a state is finite; this then holds for every state. A recurrent chain with infinite mean return time has null recurrent states.

An irreducible positive recurrent chain admits a stationary distribution. If such a distribution $\pi$ existed for this walk, its stationarity equations would giveThus ${\pi }_{j+1}-{\pi }_j={\pi }_j-{\pi }_{j-1}$, so ${\pi }_j=A+Bj$. Nonnegativity for all positive and negative integers forces $B=0$. A constant sequence cannot sum to one over $\mathbb{Z}$, so no stationary probability distribution exists. Hence the walk is null recurrent, not positive recurrent: all its states are null recurrent states. The first-return generating function in part (c) also verifies directly that its mean return time is infinite.

The only closed communicating class is $\{b,d\}$; the class $\{a,c\}$ is open and transient. Its one-step probability of staying inside is at most $2/3$, so if $\tau$ is the entrance time into $\{b,d\}$, then $\mathbb{P}(\tau >n)\le (2/3{)}^n$ for an initial state in $\{a,c\}$. Hence entrance occurs almost surely in finite time.

On $\{b,d\}$ it is an irreducible aperiodic Markov chain, because both states have positive self-loop probabilities. The finite irreducible aperiodic countable-state Markov chain convergence theorem says that its transition probabilities converge to its unique stationary distribution. The balance equation ${\pi }_b(3/4)={\pi }_d(2/3)$ with ${\pi }_b+{\pi }_d=1$ gives ${\pi }_b=8/17$ and ${\pi }_d=9/17$.

This limit also holds from $a,c$: condition on the finite entrance time and entrance state. For $\tau \le M$, convergence in the closed class applies to a finite sum; the remaining probability is bounded by $\mathbb{P}(\tau >M)$, which tends to zero as $M\to \infty$. Thus in the order $a,b,c,d$,

If there are $i$ balls in box A, a ball currently in B is selected with probability $(k-i)/k$, increasing the count, and a ball in A is selected with probability $i/k$, decreasing it. For $k\ge 1$,with every other transition zero. This is the Ehrenfest urn model.

The stationary distribution isIt is normalized by the binomial theorem, and it obeys the detailed balance:All other pairs have zero flux in both directions. These identities prove stationarity and show that this is a reversible Markov chain in equilibrium. The finite chain is irreducible and has period two; reversibility does not require aperiodicity.

An open migration process is a continuous-time Markov chain recording the populations $n=(n_1,\dots ,n_J)$ of finitely many colonies. Independent external Poisson processes bring individuals to colony $j$ at rate ${\nu }_j$. When that colony contains $k>0$ individuals, a departure opportunity occurs at total rate ${\varphi }_j(k)>0$, with ${\varphi }_j(0)=0$. The departing individual moves to colony $l$ with probability $p_{jl}$, or leaves the system with probability $p_{j0}=1-{\sum }_l{p}_{jl}$. 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 $P=(p_{jl})$ is transient: every individual eventually leaves, or equivalently the spectral radius of $P$ 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 ${\alpha }_j>0$ 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 $b(n)={\prod }_j{b}_j(n_j)$. Its ratios satisfy $b_j(k){\varphi }_j(k)={\alpha }_j{b}_j(k-1)$. The incoming external arrivals into $n$, divided by $b(n)$, contribute ${\sum }_j{\nu }_j{\varphi }_j(n_j)/{\alpha }_j$. Incoming exits contribute ${\sum }_i{\alpha }_i{p}_{i0}$. Incoming migrations from $i$ to $j\ne i$ contribute ${\alpha }_i{p}_{ij}{\varphi }_j(n_j)/{\alpha }_j$. Terms involving an empty destination are zero. Thus the full incoming rate divided by $b(n)$ isHere the traffic equations of an open migration process give the second equality, including ${\sum }_i{\alpha }_i{p}_{i0}={\sum }_j{\nu }_j$. 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 $Z_j$ 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 $b$, so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ${\mathrm{liminf}}_{k\to \infty }{\varphi }_j(k)>{\alpha }_j$; the series criterion itself is the exact condition. Colonies with ${\alpha }_j=0$ have zero stationary population and can be removed from the active class.

For the single-server M-M-1 queue specialization, ${\varphi }_j(k)={\varphi }_j$ for $k>0$, 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 ${\alpha }_j$ remain fixed during this service-capacity allocation in an open migration process. Write $A={\sum }_j{\alpha }_j$, $B=F-A$ and $b_j={\varphi }_j-{\alpha }_j$. A stationary allocation requires $B>0$, with $b_j>0$ and ${\sum }_j{b}_j=B$. The Cauchy-Schwarz inequality givesEquality holds exactly when $b_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf $F\le A$ 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.

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.

Only routes with $n_r>0$ contribute to proportional fairness or to the weighted logarithmic utility; omit inactive routes from expressions with a rate in the denominator. Active routes have positive rates whenever a positive feasible allocation exists. For a feasible competitor $y$, the elementary logarithm inequality $\log u\le u-1$ givesA zero competitor rate on an active route has utility $-\infty$ and also cannot improve the objective. Therefore a proportionally fair allocation maximizes the logarithmic objective. Conversely, the feasible set is a convex set, and differentiating the objective along $x+t(y-x)$ at $t=0+$ shows that an optimizer satisfies the proportional fairness inequality. Strict concavity gives uniqueness on active coordinates; rates assigned to nonexistent flows are immaterial.

In the linear flow network, put $z_0=n_0{x}_0$ and $z_i=n_i{x}_i$ for active routes. A local route $i$ uses only resource $i$. If $n_i>0$ and $z_0+z_i<1$, increasing $x_i$ increases the objective without violating any other constraint. Thus each active local route saturates its resource:Write $L={\sum }_{i=1}^I{n}_i$ and $N=n_0+L$. For $n_0>0$ and $L>0$, substitute $z_i=1-z_0$ into the objective. Apart from constants its dependence on $z_0$ isIts derivative vanishes when $n_0/z_0=L/(1-z_0)$, and its second derivative is negative. Hence the per-flow through-route rate isIf $L=0<n_0$, the optimal through-route aggregate rate is one, so $x_0=1/n_0=1/N$ still holds. If $n_0=0<L$, each active local route has $x_i=1/n_i$, also given by the displayed local formula. When $N=0$ there are no flows and no departures. Inactive coordinates need not be assigned these undefined per-flow formulas.

Independent arrivals and exponential document sizes make this a flow-level network model. A document of type $r$ has residual-size hazard ${\mu }_r$ per unit of data transmitted; when its transmission speed is $x_r(n)$, its completion hazard per unit time is ${\mu }_r{x}_r(n)$. Thus the continuous-time Markov chain of flow counts has transition intensitiesFor $N>0$ these departure intensities are ${\mu }_0{n}_0/N$ for the through route and ${\mu }_{i}L/N$ for an active local route. Total arrival intensity is constant and total departure intensity is bounded by ${\sum }_r{\mu }_r$, ensuring a nonexplosive Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, the offered traffic, and define the balance function of a flow-level networkThe binomial coefficients satisfyThese identities also cover states with only one kind of active route. They show that the weight $a(n)=\Phi (n){\prod }_{r=0}^I{\rho }_r^{n_r}$ satisfiesThus detailed balance for a continuous-time Markov chain proves that this is a reversible Markov chain and reduces the stationary distribution calculation to normalization.

Sum over $n_0$ first. The negative binomial series gives, for fixed local counts and $L={\sum }_i{n}_i$,All summands are nonnegative, so the Tonelli theorem permits exchanging the sums. The partition sum is thereforeIt is finite exactly when ${\rho }_0+{\rho }_i<1$ for every $i$, for $I\ge 1$. These are the resource-load conditions: resource $i$ receives the through-route offered traffic plus its local offered traffic. The normalized stationary distribution isWith positive arrival rates this is the unique stationary distribution of the irreducible feasible flow-count chain. Zero arrival rates restrict its closed class to the corresponding zero coordinates.

Summing out $n_0$ also shows that the local counts are independent, with geometric distributions on $0,1,\dots$:Hence their mean flow counts areThe binomial balance factor is essential: independent geometric counts for all routes would not give these departure rates or the correct resource-load normalization.

Every reachable state $i$ reaches zero deterministically in $i$ steps. For $j\in E$, choose a supported lifetime $k>j$; zero can jump to $k-1$ and then count down to $j$. Thus the chain is an irreducible Markov chain on $E$. Its positive-probability first return lengths are exactly the support of $Y_1$; all other return lengths are sums of such lengths. Their greatest common divisor is therefore one by assumption, so the chain is an aperiodic Markov chain.

The equilibrium residual-life distribution isIt is a probability distribution because the tail-sum identity gives ${\sum }_{j\ge 0}\mathbb{P}(Y_1>j)=\mathbb{E}{Y}_1=\mu$. With zero masses outside $E$,so it is a stationary distribution. This also displays why finite mean is needed for normalization.

Use the countable-state Markov chain convergence theorem: an irreducible, aperiodic, positive recurrent discrete-time chain on a countable state space has a unique stationary distribution and $P^n(i,j)\to {\pi }_j$ for every pair of states. All hypotheses were verified, including positive recurrence in part (b). Since $X_0=0$ and $\mathbb{P}(Y_1>0)=1$,The finite-state convergence theorem alone would not suffice when the lifetimes are unbounded. The gcd hypothesis is also necessary for this ordinary limit: deterministic lifetime 2, for example, produces alternating renewal probabilities rather than convergence.

Dividing the expected occupation time of a continuous-time Markov chain by $t$ and letting $t\to \infty$ givesFor $\lambda ,\mu >0$ this is also the almost-sure long-run time fraction, not just the limit of an expectation. The two-state continuous-time Markov chain is irreducible and positive recurrent. Alternatively, a regeneration cycle consists of a mean $1/\lambda$ symptom-free holding time followed by a mean $1/\mu$ symptomatic holding time; the renewal-reward theorem gives $(1/\mu )/(1/\lambda +1/\mu )=\lambda /(\lambda +\mu )$. This agrees with the stationary distribution solving ${\pi }_1\lambda ={\pi }_2\mu$ and ${\pi }_1+{\pi }_2=1$.

Starting in state 1, if $\lambda =0$ the fraction is zero; if $\lambda >0$ and $\mu =0$ the patient eventually enters state 2 forever, and the fraction is one. If both rates vanish, the fraction remains zero from this initial state and the quotient $0/0$ is undefined.

The untreated rates are ${\lambda }_U=0.2$ and ${\mu }_U=0.25$; treatment changes them to ${\lambda }_T=0.2\times 0.8=0.16$ and ${\mu }_T=0.25\times 2=0.5$. Their stationary distributions give symptoms fractionsConsequentlyThus the estimated long-run symptoms fraction under treatment is about 54.5% of the untreated fraction. This combines less frequent onset with faster recovery; it is not either individual hazard ratio alone.

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\pi }_n$ is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so $d_n(t)$ is nonincreasing and the minimum is finite.

Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed $0<\epsilon <1/2$,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha )/t_{\mathrm{mix}}^{(n)}(\beta )\to 1$ for any fixed $\alpha ,\beta \in (0,1)$.

Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.

Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$, so $P$ is a self-adjoint operator. Choose a real orthonormal eigenbasis $f_1,\dots ,f_m$, where $m=|S|$, $P{f}_j={\lambda }_j{f}_j$, $f_1\equiv 1$, ${\lambda }_1=1$, and $\pi (f_j)=0$ for $j\ge 2$.

For fixed $y$, apply the spectral decomposition to $g_y(z)=1_{\{y\}}(z)/\pi (y)$. Its coefficient against $f_j$ is $f_j(y)$, whereas $(P^t{g}_y)(x)=P^t(x,y)/\pi (y)$. Thus the spectral kernel expansion of a reversible chain isThis holds for all integers $t\ge 0$; at $t=0$ each multiplier is one, including when ${\lambda }_j=0$. Negative eigenvalues are allowed, and retain their signs for odd $t$.

The lazy Markov chain has holding probability $1/2$ and transition probability $1/(2n)$ to each neighbour in the hypercube graph. Its stationary distribution is $\pi (x)=2^{-n}$ by symmetry.

For $(x,y)$ choose the path changing the differing coordinates in increasing order. Its length is at most $n$. Fix a directed edge $(u,u^{(k)})$ that flips coordinate $k$. A path uses this edge exactly when $x_k=u_k$, $y_k=-u_k$, $y_j=u_j$ for $j<k$, and $x_j=u_j$ for $j>k$. The coordinates $x_j$ for $j<k$ and $y_j$ for $j>k$ are free. Thus exactly $2^{n-1}$ ordered pairs use it, whileThe unweighted load divided by capacity equals $n$; multiplying by the maximum length yields $\rho \le n^2$. The canonical paths Poincare bound therefore proves the slightly stronger ${\mathrm{Var}}_{\pi }(f)\le n^2\mathcal{E}(f,f)$, and in particular the requestedOne can keep the actual lengths: among these $2^{n-1}$ pairs, coordinate $k$ always differs, and each of the other $n-1$ coordinates differs for half the pairs. Their mean path length is $(n+1)/2$, giving exact congestion $\rho =n(n+1)/2$. This refinement still has order $n^2$.