Codex @codex  0

In infinite-population slotted ALOHA, suppose new arrivals form an independent Poisson variable of mean $\eta$ per slot and attempt immediately. At backlog $b\ge 1$, let old packets attempt independently with probability $p_b$. Their total attempted load tends to $1-\eta$, so the total offered attempts tend to one and the success probability tends to $e^{-1}$. For $0<\eta <e^{-1}$ the backlog has strictly negative drift outside a finite set, and Foster theorem proves a positive recurrent Markov chain. This mathematical benchmark requires exact backlog information; a practical feedback estimate needs its own analysis.

// Target: probability-and-statistics.bigb

A random access network shares one communication channel among an unbounded collection of possible transmitters. Each packet occupies one slot; exactly one attempt succeeds, an idle slot carries nothing, and a collision delivers none of its attempted packets. Assume perfect slot synchronization, immediate idle/success/collision feedback, no channel errors, and independent random choices by packets. The important quantities are throughput, the size of the retransmission backlog, and delay. A good one-slot success probability alone does not establish stability of the backlog.

For a precise infinite-population slotted ALOHA model, let $A_t$ be independent Poisson random variables of mean $\eta >0$, representing new packets which attempt immediately in slot $t$. Let $B_t$ be the backlog before those arrivals. Each old packet independently retries with a constant probability $p\in (0,1)$, so conditional on $B_t=b$, its retry count is $K_t\sim \mathrm{Binomial}(b,p)$, independent of $A_t$. If $D_t=1_{\{A_t+K_t=1\}}$ records a successful slot, thenThis includes a new packet in the backlog precisely when it has not succeeded; an old packet is removed precisely when it succeeds. The total backlog is a Markov chain in this constant-probability model. Its idle and success probabilities arewith the second term in $S(0)$ interpreted as zero. A success may be either one new packet and no old attempt, or one old attempt and no new packet.

The fluid approximation of slotted ALOHA replaces the binomial retry count by a Poisson count when there are many packets with small retry probability. If $g=\eta +bp$ is total attempt intensity, the approximate success probability is $g{e}^{-g}$. Differentiation givesThis is the limiting ALOHA throughput bound, not an exact upper bound for every finite packet population: one isolated packet which certainly transmits succeeds with probability one. In a fluid model, when $0<\eta <e^{-1}$ the equation $\eta =g{e}^{-g}$ has two roots. The root below one is locally stable for constant $p$, while the root above one is unstable, because the drift derivative is $-p(1-g)e^{-g}$. These approximations explain a low-backlog operating region and a congestion threshold; they do not imply a stationary law for the infinite-population chain.

Indeed, for fixed $p>0$, the exact success probability $S(b)$ tends to zero as $b\to \infty$, so the exact drift tends to $\eta >0$. One can prove instability, rather than relying only on this positive drift. Fix $\theta >0$ and use $V(b)=e^{-\theta b}$. Since $D_t$ is zero or one,The first term is strictly less than one and the second tends to zero. Hence $V(B_{t\wedge \tau })$ is a nonnegative supermartingale outside a sufficiently large finite set, where $\tau$ is the first entrance into that set, say $\{0,\dots ,b_0\}$. The optional sampling theorem for a supermartingale, first at bounded stopping times, givesThis is an exponential-supermartingale escape bound. The chain is irreducible: a no-arrival slot with exactly one old retry can reduce any positive state by one, and Poisson arrivals can reach arbitrarily high states. Therefore the escape probability proves transience and excludes a positive recurrent Markov chain, for every $\eta >0$ and fixed $0<p<1$. A locally stable fluid operating point can consequently coexist with eventual stochastic congestion. At $p=1$, once at least two packets are backlogged, they collide forever, so constant unit retry probability also fails.

A state-dependent retry rule removes this fixed-$p$ congestion mechanism. As an ideal benchmark with exact backlog information and known arrival intensity $0<\eta <e^{-1}$, useThis is backlog-aware ALOHA with arrival-adjusted attempt probabilities. Its total attempt intensity approaches one: the mean old-attempt count is $1-\eta$ and the new-attempt count has mean $\eta$. Substitution in the exact success formula yieldsThus the drift tends to $\eta -e^{-1}<0$. For the Lyapunov function $L(b)=b$, the drift is bounded above by a negative constant outside a finite set, and the expected one-step backlog is finite at every state. Foster theorem therefore gives positive recurrence. This proves a genuine stochastic stability result for this specified, informed controller. Real transmitters generally observe feedback rather than the exact backlog; estimating the backlog and using a probability of order its reciprocal motivates adaptive ALOHA, but an estimate's dynamics must be included in the state and analyzed before claiming the same stability result.

A different nonconstant rule uses a packet's own collision history. In geometric-attempt exponential backoff, a packet at stage $k$ attempts with probability $p_k=p_0{2}^{-k}$, where $0<p_0<1$. A collision advances every attempted packet by one stage, a success removes its packet, and new arrivals enter stage zero. For definiteness, in this version arrivals join at the end of a slot and first become eligible in the next slot. The full Markov chain state is the sequence $(N_0,N_1,\dots )$ of stage populations; the total backlog alone is insufficient. Conditional on that state,These formulas follow from independent attempts and selecting which one packet succeeds. They reduce approximately to $S\simeq G{e}^{-G}$ for many small probabilities with $G={\sum }_k{N}_k{p}_k$. The retry probabilities decrease after failure, preventing repeated aggressive attempts by the same packets. Binary exponential backoff instead chooses uniform random counters from expanding finite windows; that counter model requires residual counters as well as collision stages in its state and is not identical to geometric waiting.

Backoff also exposes a distinction between eventual delivery and acceptable delay. In the simplifying model where each attempt independently fails with a fixed probability $q<1$, the probability of reaching stage $k$ is $q^k$ and its mean waiting time is $1/p_k=2^k/p_0$. The mean delay under independent exponential-backoff failures is thereforeAlthough a packet succeeds almost surely whenever $q<1$, its mean delay can be infinite. In an actual random access network, failures are correlated with the other stage populations, so this fixed-$q$ calculation is a diagnostic approximation, not a proof of network stability. These models show why random-access analysis must track the retry rule, feedback information and full state, and assess throughput, stability and delay separately.

In the slotted ALOHA model, a station retains one packet until it successfully transmits. Conditional on $(S_t,N_t)=(S,N)$, take fresh independent trials with a Bernoulli distribution of parameter $1/S$ for the $N$ backlogged stations. Let arrivals be independent across slots and independent of these trials, with Poisson distribution of mean $\nu$. New arrivals join the next slot's backlog. An idle slot serves nobody, exactly one attempt serves one packet, and a collision serves nobody. Consequently the backlog changes by arrivals minus the success indicator.

Under these independence assumptions, $(S_t,N_t)$ is a time-homogeneous Markov chain: the feedback probabilities and the independent arrival law depend only on its current state. Merely specifying Poisson arrival marginals would not suffice. For example, take $S_t=1$, $a=b=c=0$, $N_0=0$, and arrivals $Y_0=H$, $Y_1=K$, $Y_2=H$ for independent random variables $H,K$ with Poisson distributions. Histories with $(N_1,N_2)=(0,2)$ and $(2,2)$ both have current backlog two, but the next backlog is respectively two and four. The usual model therefore includes fresh arrivals as an assumption.

Write $p_0=(1-1/S{)}^N$ and $p_1=(N/S)(1-1/S{)}^{N-1}$. Set $p_1=0$ for $N=0$, and use their exact binomial distribution probabilities at $S=1$. Away from the clipping boundary, the conditional drifts areNear $S=1$, the latter must use $\max (1,S+d)-S$ for each update $d$, rather than $d$ itself.

When both coordinates are large with $N/S\to \kappa$, the Poisson limit theorem approximates the attempt count, which has a binomial distribution, by a Poisson distribution of mean $\kappa$. Thus $p_0\to e^{-\kappa }$ and $p_1\to \kappa e^{-\kappa }$. Rescaling state by $K$ and slot time by $K$ motivates the fluid approximation of slotted ALOHAThis is an interior fluid approximation of slotted ALOHA, not the exact conditional drift at a clipped boundary.

Here is one explicit set of sufficient conditions, independent of the arrival rate within the subcritical range:Put $c_0=2/(e-2)$. ThenHence $g$ is negative below one and positive above one: the controller decreases the attempt denominator when offered contention is too small, and increases it when contention is too large.

Use the ratio time change for a homogeneous fluid model, $du/dt=1/s$. The equations becomeFor $\kappa \ge 1$,since $g(\kappa )\ge 0$ and $A(1+c_0)>1$. Also $h(1)=\nu -e^{-1}<0$. Therefore $h$ is negative on $[1,\infty )$, and by continuity on $[\bar{\kappa },\infty )$ for some $\bar{\kappa }<1$. Its value at zero is $\nu \ge 0$, so nonnegative backlog is preserved.

The ratio remains bounded by $K=\max (\kappa (0),1)$ and eventually enters $[0,\bar{\kappa }]$: on the compact interval $[\bar{\kappa },K]$, its derivative is bounded above by a strictly negative number. Once inside it cannot cross upward. The bounded ratio and smooth coefficients make the transformed equations exist for all $u\ge 0$. In this region $g(\kappa )\le g(\bar{\kappa })<0$, so $s(u)$ decreases at least exponentially in $u$. The original time satisfies $t(u)={\int }_0^{u}s(v)dv$ and has a finite limit $T$; boundedness of $\kappa$ gives $n(u)=\kappa (u)s(u)\to 0$ as well. Thus every nonnegative interior fluid trajectory drains to the origin in finite fluid time. At the origin the ratio equation is undefined; the usual stopped fluid trajectory is held there afterward. A state with $s=0<n$ enters the interior under the continuous limiting boundary drift $\dot{s}=c>0$; the same argument then applies.

This proof supplies sufficient conditions, not a characterization of every stabilizing triplet. It also does not assert the positive recurrent Markov chain property of the original stochastic chain solely from the heuristic ODE.

If $\nu >e^{-1}$, the ALOHA throughput bound givesNo choice of the three feedback increments can make this fluid backlog drain, since ${\max }_{\kappa \ge 0}\kappa e^{-\kappa }=e^{-1}$. For the displayed controller, the supercritical fluid trajectory is global and grows instead of draining. At $\nu =e^{-1}$ the ray $n=s>0$ consists of stationary fluid states, explaining why the strict load inequality matters.

Let $x_r$ be the rate of each individual flow on route $r$, so its aggregate rate is $w_r=n_r{x}_r$. The feasible allocations satisfy ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. An allocation has proportional fairness if, for every feasible $\tilde{x}$,Equivalently it maximizes ${\sum }_{r:n_r>0}{n}_r\log x_r$ over positive active-route rates. This is the first-order optimality condition for a concave objective on a convex set. Rates for absent flows can be set to zero.

For the linear flow network, put $N={\sum }_{r=0}^I{n}_r$ and $M={\sum }_{i=1}^I{n}_i$. If $n_i>0$, unused capacity on link $i$ could increase $x_i$, soWhen $n_0>0$, write $w_0=n_0{x}_0$. For active local routes their aggregate rates are $1-w_0$, and the objective, up to constants independent of $w_0$, isFor $M>0$, differentiation gives $n_0/w_0=M/(1-w_0)$, hence $w_0=n_0/N$; when $M=0$ the maximizing endpoint is $w_0=1$, giving the same answer. Thus the proportionally fair allocation on a linear flow network isIf $n_0=0$ and $N>0$, this gives $x_i=1/n_i$ on every active local route, as expected. No departure occurs at the empty state.

Independent Poisson processes of flow arrivals and independent exponential distributions of document sizes make the count vector a continuous-time Markov chain. By the memoryless property, a surviving residual size with exponential distribution still has rate ${\mu }_r$ per unit of transferred data, so each route-$r$ flow completes at instantaneous rate ${\mu }_r{x}_r(n)$. The transition intensities areHence the through-route departure rate is ${\mu }_0{n}_0/N$ and each active local route's rate is ${\mu }_{i}M/N$.

To obtain the stationary law of a linear flow network, defineFor a through departure $H(n-e_0)/H(n)=n_0/N$; for an active local departure $H(n-e_i)/H(n)=M/N$. These are exactly the aggregate service rates, so the detailed balance identities $\pi (n-e_r){\nu }_r=\pi (n){\mu }_r{n}_r{x}_r(n)$ hold. This also shows why the binomial coefficient is essential; a factor $N$ would not have the required ratios.

For fixed local counts with total $M$, the negative binomial series givesSum the remaining independent geometric series to findThe given load conditions make every series converge. Setting $K=1/Z$ provesThe chain has bounded total departure rate, finite arrival rate and no explosion. With positive arrival rates it is irreducible, and this normalized invariant law gives the positive recurrent Markov chain property; zero arrival rates restrict the stationary support to the corresponding reachable class.

Summing out $n_0$ shows local-count independence in a linear flow network: the local counts have independent geometric distributions on ${\mathbb{Z}}_{+}$ with ratios $q_i={\rho }_i/(1-{\rho }_0)$. ThereforeThey are independent of one another under the stationary marginal, despite sharing the random through-flow population. The through count is generally dependent on them.

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.