For any $s\ge 0$, $Y\ge 0$ implies $e^{sY}\ge 1$. Hence $1_{\{Y\ge 0\}}\le e^{sY}$, and taking expected values gives the Chernoff boundAt $s=0$ this is the trivial bound one; an infinite exponential moment merely gives a noninformative bound. For positive $s$ at which all required moment-generating functions are finite, define ${\alpha }_j(s)=s^{-1}\log \mathbb{E}[e^{s{X}_{ji}}]$. Independence of the source random variables impliesApplying the Chernoff bound to $Y=X-C$ givesConsequentlyHere $s>0$ and, for a nontrivial target, $\gamma >0$.

The effective bandwidth ${\alpha }_j(s)$ is the capacity charge of one source for this exponential-moment tail criterion. Independent sources contribute additively. It incorporates variability as well as mean demand: the Jensen inequality gives ${\alpha }_j(s)\ge \mathbb{E}{X}_{ji}$, and, under exponential integrability near zero, ${\alpha }_j(s)\to \mathbb{E}{X}_{ji}$ as $s\downarrow 0$. For bounded traffic its large-$s$ limit is the essential peak, as described by the mean and peak limits of effective bandwidth. Thus larger $s$ gives more weight to rare high demands. This is a one-window demand bound; a queue's overflow probability over many windows requires additional temporal modeling, not just this single-window calculation.

For the normal distribution $X_{ji}\sim N({\lambda }_j,{\sigma }_j^2)$, completing the square in its density gives the moment-generating functionWrite $m={\sum }_j{n}_j{\lambda }_j$ and $v={\sum }_j{n}_j{\sigma }_j^2$ for the aggregate mean and variance. The exponential-moment capacity condition becomesFor $v>0$, the last two terms are minimized at $s=\sqrt{2\gamma /v}$, where their sum is $\sqrt{2\gamma v}$. Therefore Gaussian effective bandwidth yields the sufficient conditionEquivalently, optimizing the exponential bound directly when $C>m$ gives $\exp [-(C-m{)}^2/(2v)]$; when $C\le m$ the best nonnegative-$s$ bound is one. The square-root condition is sufficient rather than necessary because an exponential bound does not equal the exact normal tail.

For the exact condition, independence and multiplication of the normal moment-generating functions show that $X\sim N(m,v)$. For $v>0$, let $\Phi$ be the standard normal distribution function. The normal law is continuous, soSince $\Phi$ is continuous and strictly increasing from zero to one, the exact Gaussian overflow constraint isThe constant depends only on the desired tail exponent $\gamma$, not on the source counts. It is positive when $\gamma >\log 2$, zero when $\gamma =\log 2$, and negative when $0<\gamma <\log 2$. For example, at $\gamma =\log 100$ the exact normal quantile is about $2.32635$, whereas the Chernoff bound uses $\sqrt{2\log 100}\approx 3.03485$; the latter reserves more capacity.

Finally, the positive-variance hypothesis must not be hidden. If $v=0$, then $X=m$ almost surely, and the zero-variance boundary of an overflow constraint gives $\mathbb{P}(X\ge C)=1_{\{m\ge C\}}$. For $\gamma >0$, the exact condition is then $m<C$. In particular $m=C$ does not meet the target even though substituting $v=0$ into the printed non-strict square-root inequalities would allow it. The displayed normal-quantile equivalence applies to nondegenerate Gaussian traffic; the deterministic case requires this strict boundary convention.

Only routes with $n_r>0$ need a per-flow rate: absent flows contribute no utility and have no completion events. Interpret the proportional-change sum and the logarithmic objective on these active routes. With positive capacities and finitely many nonempty routes, a strictly positive feasible active-rate vector exists. Define its weighted logarithmic utility by $U(x)={\sum }_{r:n_r>0}{n}_r\log x_r$, with value $-\infty$ if an active rate is zero.

For positive feasible $x,y$, the elementary concavity inequality $\log u\le u-1$ givesThe last sum is nonpositive by proportional fairness. Feasible competitors with a zero active rate have utility $-\infty$, so they cannot improve it either. Thus a proportionally fair allocation maximizes weighted logarithmic utility. Conversely, if $x$ maximizes this utility, the feasible line segment $x+\theta (y-x)$ has nonpositive right derivative at $\theta =0$, giving precisely ${\sum }_r{n}_r(y_r-x_r)/x_r\le 0$. This also covers a competitor with zero coordinates, since $x+\theta (y-x)$ stays positive for sufficiently small $\theta$. The strictly concave function $U$ makes the active-rate optimizer unique.

For the linear flow network, put $M={\sum }_{i=1}^I{n}_i$ and $N=n_0+M$. If $n_i>0$ and resource $i$ is not saturated, its local per-flow rate could be increased without affecting any other resource. This would strictly increase weighted logarithmic utility. HenceIf $n_0>0$ and $M>0$, substitute $x_i=(1-n_0{x}_0)/n_i$ on all active local routes into the utility. The terms depending on $x_0$ areIts derivative vanishes when $1/x_0=M/(1-n_0{x}_0)$, so $x_0=1/N$. Its second derivative is negative, giving the unique maximizer. If $M=0<n_0$, utility increases up to the capacity endpoint $x_0=1/n_0=1/N$. If $n_0=0$, each active local route uses its entire local resource. Altogether the proportionally fair allocation on a linear flow network isAbsent-route rates may be set to zero, and departures are zero at the empty state $N=0$. Notice that these are per-flow rates: the aggregate through service is $n_0/N$, while each active local route gets aggregate service $M/N$.

In the document-transfer flow-level network model, let $e_r$ be the unit vector for route $r$. Independent Poisson processes of flow arrivals give transitions $n\to n+e_r$ at rate ${\nu }_r$. An active document on route $r$ receives service at rate $x_r(n)$ and has an exponential distribution of size with parameter ${\mu }_r$. By the memoryless property, its instantaneous completion rate is ${\mu }_r{x}_r(n)$. Summing over the active documents gives the continuous-time Markov chain intensitiesThus through-route departures have rate ${\mu }_0{n}_0/N$, and active local departures have rate ${\mu }_{i}M/N$. All other off-diagonal intensities vanish. The diagonal intensity is the negative of the sum of the outgoing intensities. Each route's aggregate service is at most one, so the total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$; the process is a nonexplosive continuous-time Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, assume ${\mu }_r>0$, and define the balance function of a flow-level network byThe adjacent-state ratios of this binomial coefficient areThey equal the aggregate service rates just obtained. Therefore, with $w(n)=H(n){\prod }_r{\rho }_r^{n_r}$,These are the detailed balance for a continuous-time Markov chain equations on every adjacent pair. Summing incoming and outgoing pairs proves stationarity whenever the weights can be normalized. Hence the stationary law of a linear flow network isThe coefficient here is a binomial coefficient, not merely the total number of flows. Both it and the denominator in $x_0=1/N$ are visible in the original PDF but missing from the converted TeX.

We can also determine exactly when the normalizing constant is finite. For $0\le {\rho }_0<1$, summing first over $n_0$ with local counts fixed and applying the negative binomial series givesThe remaining sums are independent geometric series. Thusprovided ${\rho }_0+{\rho }_i<1$ for every $i$. These inequalities are also necessary: if ${\rho }_0\ge 1$, the states with every local count zero already give a divergent sum; otherwise any local ratio at least one makes its geometric series diverge. Thus the stationary formula requires strict offered load below capacity at every resource. With positive arrival rates, the process is irreducible, and these normalizable detailed balance weights give its unique stationary distribution. Outside these inequalities, the displayed weights are not a probability distribution. Zero arrival rates can be handled on the reachable class by setting the corresponding population to zero.

Use the standard infinite-population slotted ALOHA model with independent Poisson random variables $Y_t$ of mean $\nu >0$ giving arrivals during slot $(t,t+1)$. Every new packet makes its first attempt in the next slot. An unsuccessful packet joins the old backlog and independently retries in each subsequent slot with a fixed probability $p$, where $0<p\le 1$. A single transmission succeeds, while two or more transmissions collide and all those packets remain. This constant retry probability is an essential assumption of the instability result; it is not a claim about every adaptive random-access protocol.

At the beginning of slot $(t,t+1)$, let $N_t$ count the previously backlogged packets, excluding the fresh batch $Y_{t-1}$ which now makes its first attempt. Given $N_t=n$, the old attempts have the binomial distribution $\mathrm{Bin}(n,p)$, independently of the fresh Poisson random variable. Let $T_t$ be the total number of attempts. The feedback $Z_t$ records zero attempts, one attempt, or a collision. Adding the fresh packets and subtracting the one departure if there is a success givesThus $N_t$ is an old-packet backlog, not the number of transmitters in the slot. Fresh attempts and retry attempts are both included in $T_t$ and hence in the feedback $Z_t$.

First take $0<p<1$ and write $q=1-p$. Conditional on old backlog $n$, a noncollision is either no attempt, or precisely one attempt. Independence and the Poisson distribution give its probability aswhere the last term is zero for $n=0$. The two contributions to one attempt are one fresh packet with no old attempt, or one old attempt with no fresh packet.

To prove permanent collisions in constant-probability slotted ALOHA, consider a process which starts with $b$ old packets and is forced never to remove a packet. Before its $k$th future slot its backlog is $b+A_k$, where $A_k$ is the sum of the first $k$ fresh arrival batches, so $A_k$ has the Poisson distribution with mean $\nu k$. Generate its packet-attempt coins and the actual system's coins on the same probability space, using the same coins for the same packets. Until the first noncollision, every actual slot collides and removes nothing, so the two processes agree exactly. In particular, a sample path on which the hypothetical process always collides is a permanent-collision sample path for the actual system. This is the collision-path coupling for slotted ALOHA.

The union bound, without any assumption of independence between future noncollision events, bounds the probability of at least one such event byPut $r=e^{-\nu p}<1$. The moment-generating function of the Poisson distribution and its derivative giveConsequently the collision-path coupling for slotted ALOHA yields the explicit boundThe geometric decay of $q^b$ dominates the linear factor in $b$, so $\epsilon (b)\to 0$. Choose an integer $K$ so that $\epsilon (b)\le 1/2$ for every $b\ge K$. From every such backlog, the conditional probability that all future slots collide is at least $1/2$.

It remains to show that this positive probability implies an almost-sure eventual escape into permanent collisions. From any finite state, wait for an arrival batch containing at least $K+2$ packets. Its probability in each slot is the strictly positive constant $\mathbb{P}\{\mathrm{Poisson}(\nu )\ge K+2\}$. Independent arrival batches ensure that the waiting time is almost surely finite. That arrival batch forces a collision, and the next old backlog is at least $K$. Starting there, observe slots until the first noncollision. If none occurs, the desired event has happened. If one occurs, this failure is observed at a finite stopping time; wait for another sufficiently large arrival batch and start another attempt. The Strong Markov property, or simply the independence of the fresh arrival variables and packet-attempt coins after each such stopping time, gives conditional failure probability at most $1/2$ at every attempt. Therefore the probability that the first $m$ attempts all fail is at most $2^{-m}$. Infinite failures have probability zero, provingThis argument proves the required almost-sure assertion, rather than merely positive drift or a small one-slot success probability.

If $p=1$, a batch of at least two fresh packets occurs almost surely. The batch collides, leaving at least two old packets; both retry in every subsequent slot, so all subsequent slots collide. Thus the same conclusion holds. At $p=0$ the conclusion fails: old packets never transmit, and fresh batches of size zero or one occur infinitely often. This explains why positive retry probability was included in the model.

A conventional finite-population slotted ALOHA model behaves differently. Suppose there are at most $M$ old packets, each retries with probability $0<p<1$, and there is a conditional probability at least $\delta >0$ of no fresh attempts in each slot. The probability of an idle slot, conditional on the entire past, is then at least $\delta (1-p{)}^M=\eta >0$. Iterating conditional probabilities givesFor each fixed $j$, the probability of collisions forever after $j$ is zero. A countable union over $j$ shows that eventual permanent collisions have probability zero. This is the finite-population exclusion of permanent ALOHA collisions. A finite model can still spend long periods in a heavily backlogged state, but its bounded backlog removes the mechanism by which the infinite-population idle and success probabilities tend to zero. Degenerate finite protocols, such as all backlogged stations retrying with probability one, can have absorbing collision states; a finite population alone does not exclude those.