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

After $k$ collisions a packet chooses an independent counter uniformly from $\{0,\dots ,2^k-1\}$ and retries when it expires. The window doubles after a further collision. This is an example of exponential backoff with a nonconstant retry rule, contrasting with constant-probability slotted ALOHA.

In slotted ALOHA, let old packets retry independently with fixed probability $0<p<1$, and let independent Poisson random variables of mean $\nu >0$ transmit once on arrival. Write $q=1-p$ and $r=e^{-\nu p}$. A hypothetical process which never removes a packet has backlog $b+A_t$, where $A_t$ is the cumulative arrival count over $t$ slots. Couple its attempts to those of the actual process until the first noncollision. Its one-slot noncollision probability at backlog $n$ is $h(n)=e^{-\nu }[(1+\nu )q^n+np{q}^{n-1}]$. The union bound and the Poisson distribution giveIndeed $\mathbb{E}[q^{A_t}]=r^t$ and $\mathbb{E}[A_t{q}^{A_t}]=\nu tq{r}^t$. Thus $\epsilon (b)\to 0$. From every sufficiently large backlog, permanent collisions have probability at least $1/2$. Independent arrival batches reach that threshold almost surely; after each failed attempt the Strong Markov property permits another attempt. The probability of $k$ consecutive failures is at most $2^{-k}$, proving almost-sure eventual permanent collisions without assuming in advance that the backlog escapes.

If a finite-population slotted ALOHA system has at most $M$ packets eligible to retry, uses independent retry probability $0<p<1$, and has conditional probability at least $\delta >0$ of no fresh attempts in any slot, then its conditional idle probability is at least $\delta (1-p{)}^M$. The probability that the next $k$ slots all collide is therefore at most $[1-\delta (1-p{)}^M{]}^k$. Letting $k\to \infty$ and taking a countable union over starting slots excludes eventual permanent collisions. Positive lower bounds on idle probability are essential: deterministic retries at probability one can create an absorbing collision state.

Use the constant-retry version of slotted ALOHA. Fresh packets arrive in each slot as independent Poisson random variables $Y_t$ of mean $\nu >0$, and each first attempts in the next slot. Every already backlogged packet independently retries with the same fixed probability $0<p<1$ each slot. Transmission choices are independent of arrivals and past choices. Let $N_t$ be the number of old backlogged packets just before the slot $(t,t+1)$, excluding the fresh $Y_{t-1}$ packets about to make their first attempt. The number of attempts is $\mathrm{Bin}(N_t,p)+Y_{t-1}$, and $Z_t$ records zero, one, or at least two attempts. Exactly one attempt succeeds and leaves; otherwise every fresh packet becomes backlogged. ThereforeThe arrivals $Y_{t-1}$ are independent of $N_t$, since that backlog depends only on earlier arrivals and choices. This convention explains the displayed one-slot index shift.

A throughput bound or positive drift alone does not prove eventual collisions in every slot. Instead use the collision-path coupling for slotted ALOHA. Set $q=1-p$. Given old backlog $n$, the probability of a noncollision, namely zero or one total attempts, isThe terms represent no fresh attempts and zero old attempts, one fresh attempt and no old attempts, or one old attempt and no fresh attempts. Start from backlog $b$ and couple to a hypothetical process in which no packet is ever removed. Until the first noncollision the two processes agree; after $t$ slots the hypothetical old backlog is $b+A_t$, where $A_t$ is the sum of $t$ independent arrivals and hence has Poisson distribution of mean $\nu t$.

A first noncollision of the real process must therefore be a noncollision in this coupled process. The union bound givesWriting $r=e^{-\nu p}<1$, the Poisson generating function gives $\mathbb{E}[q^{A_t}]=r^t$ and $\mathbb{E}[A_t{q}^{A_t}]=\nu tq{r}^t$. Sum the geometric series and its derivative to obtainSince $q^b$ decays exponentially while the bracket grows only linearly, choose a finite threshold $b_0$ such that $\epsilon (b)\le \frac{1}{2}$ for every $b\ge b_0$. Thus from any such backlog, there is conditional probability at least $\frac{1}{2}$ that every subsequent slot collides.

It remains to show that opportunities to use this bound recur, without assuming backlog transience. An arrival batch $Y_{t-1}\ge b_0+1$ forces $N_{t+1}\ge b_0$, since at most one packet departs. Such a batch has strictly positive probability independently in each slot; the waiting time for one is finite almost surely, even after a stopping time. At the first visit to backlog at least $b_0$, begin an attempt at permanent collisions. If it fails, its first noncollision occurs at a finite stopping time; after that, another large arrival batch reaches the threshold and we start again. The Strong Markov property gives conditional failure probability at most $\frac{1}{2}$ for each attempt. The probability of $k$ consecutive failures is consequently at most $2^{-k}$. Letting $k$ tend to infinity provesFor $p=1$, after a slot with at least two fresh packets the next old backlog is at least two, and all old packets retry forever; this gives the same conclusion. For $p=0$ the assertion is false. It also must not be applied to all adaptive protocols: backlog-aware ALOHA with arrival-adjusted attempt probabilities can be stable for sufficiently small arrival rates. The fixed-retry assumption is part of this mathematical model.

In a standard finite-population model, each of at most $M$ stations holds one pending packet, or at most one packet per station may attempt in a slot. Suppose fresh transmission probabilities are bounded below one and retries use $0<p<1$. There is then a uniform positive conditional probability $\delta$ of no fresh attempts; all old packets stay silent with probability at least $q^M$. Thus a slot is idle with conditional probability at least $\delta q^M>0$, regardless of the past. The chance that the next $k$ slots all collide is at most $(1-\delta q^M{)}^k$. Let $k\to \infty$ and take the countable union over possible starting slots: eventual permanent collisions have probability zero. This is finite-population exclusion of permanent ALOHA collisions. Degenerate rules such as retry probability one can instead give absorbing collisions, so this conclusion needs the stated nondegeneracy conditions.

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.

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.

Use the standard infinite-population slotted ALOHA model with independent fresh arrivals with Poisson distribution $Y_t\sim \mathrm{Poisson}(\lambda )$, $\lambda >0$. Newly arrived packets attempt in the next slot. Given $N_t=n$ old backlogged packets, each independently attempts with fixed probability $f$, so the retransmission count has binomial distribution $R_t\sim \mathrm{Binomial}(n,f)$, independent of $Y_t$ and earlier random choices. Let $Z_t$ record whether $R_t+Y_t$ is zero, one, or at least two. A single transmission succeeds and departs; a collision makes every transmitted packet remain. ThereforeOnly the present backlog determines the law of the next independent choices, so $N_t$ is a time-homogeneous Markov chain.

For $0<f<1$, put $q=1-f$ and $b_n=nf{q}^{n-1}$, with $b_0=0$. Its nonzero transition probabilities areFor example, a single fresh arrival leaves the backlog unchanged only if no old packet transmits; if an old packet also transmits, that fresh arrival becomes a new backlogged packet. These cases explain the extra diagonal term and the suppressed one-step increase at $n=0$. At $f=1$ the same formulas hold with $q^0=1$, $b_1=1$ and $b_n=0$ for $n\ne 1$.

Here is an almost-sure proof of permanent collisions in constant-probability slotted ALOHA for $0<f<1$, rather than just a positive-drift heuristic. For $\theta >0$, the conditional exponential increment isAs $n\to \infty$ this tends to a number strictly below one. Choose $M\ge 1$ so the expression is at most one for $n\ge M$. Stopping $e^{-\theta N_t}$ when the chain first enters $\{0,\dots ,M-1\}$ gives a nonnegative supermartingale. Downward jumps have size at most one, so it hits at $M-1$. Optional sampling theorem for a supermartingale, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundThis is an irreducible Markov chain: every positive state can successively decrease to zero, and from zero Poisson batches reach every state at least two, with state one then reached from two. An irreducible recurrent Markov chain would hit that finite set with probability one from every state, contradicting the bound. Hence every state is a transient state, every finite set is visited only finitely often, and $N_t\to \infty$ almost surely.

The conditional success probability is $p(N_t)=e^{-\lambda }(b_{N_t}+\lambda q^{N_t})\to 0$. The centered success indicators form a martingale difference sequence with bounded increments. The strong law for martingales with bounded increments givesThe conditional means have Cesàro average zero, while the strong law of large numbers gives $t^{-1}{\sum }_{u<t}{Y}_u\to \lambda$. Therefore $N_t/t\to \lambda$ almost surely. Finallydecays exponentially along this linear backlog growth. Its sum over $t$ is almost surely finite. The Conditional Borel-Cantelli lemma then implies that only finitely many slots have zero or one transmission. Thus $\boxed{\mathbb{P}(\exists J:Z_t=\ast \text{ for every }t\ge J)=1}$. At $f=1$, a fresh batch of size at least two eventually occurs, after which at least two old packets retransmit in every slot, giving the same conclusion directly.

The qualification $f>0$ is essential: if $f=0$, then $Z_t$ depends only on the independent Poisson arrivals, and zero- or one-arrival slots occur infinitely often. Positive mean arrival rate alone, without the Poisson model or another assumption allowing collisions to develop, would also be insufficient: Bernoulli fresh arrivals and initial backlog zero never collide.

One alternative is binary exponential backoff: after $k$ collisions a packet selects a waiting time uniformly from $\{0,\dots ,2^k-1\}$ and tries when its counter expires. Its attempt behavior depends on its collision history, rather than a common constant $f$. Another possibility, if a backlog estimate ${\hat{N}}_t$ is available, is to set the attempt probability near $1/{\hat{N}}_t$, keeping the offered retransmission count near one. These descriptions illustrate adaptive access rules; they do not assert that every backoff variant is stable at arbitrary load.

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.

Use the slotted ALOHA model with one outstanding packet per active station and a collision channel: a slot with exactly one attempt succeeds, whereas an idle slot or a slot with two or more attempts delivers nothing. Let $Y_t$ be independent Poisson random variables of mean $\nu$, independent also of the transmission choices. Arrivals join after the current slot's attempts. Given $(S_t,N_t)=(S,N)$, the attempt count has a binomial distribution with parameters $N$ and $1/S$. Consequently, for $N\ge 1$,For $N=0$, set $p_0=1$ and $p_1=0$. The equation $N_{t+1}=N_t+Y_t-1_{\{Z_t=1\}}$ adds arrivals and removes precisely one packet following a successful slot. The estimate $S_t\ge 1$ controls the common transmission probability and updates using the idle, success, or collision feedback. The conditional distribution of the next state depends only on $(S_t,N_t)$, so this pair is a Markov chain.

Away from the reflecting floor in $S$, its one-step conditional expectations areWhen $N$ and $S$ are large with $N/S\approx \kappa$, the Poisson limit theorem gives $p_0\approx e^{-\kappa }$ and $p_1\approx \kappa e^{-\kappa }$. Treating these approximate drifts as derivatives motivates the fluid approximation of slotted ALOHA:The floor at $S=1$ is negligible in this interior scaling. This calculation motivates the ordinary differential equations; it is not a proof of a stochastic fluid limit.

For $(a,b,c)=(2-e,0,1)$, putThen $g^{\prime }(\kappa )=(e-2+\kappa )e^{-\kappa }>0$ and $g(1)=0$. On the domain $s>0$, introduce time $\tau$ by $d\tau /dt=1/s$. Differentiating $\kappa =n/s$ giveswhere $r(\kappa )=\kappa [1-(e-2+\kappa )e^{-\kappa }]$.

The function $r$ is strictly increasing from zero to infinity, and $r(1)=e^{-1}$. To check the monotonicity explicitly,Indeed, with $d=3-e\in (0,1)$,because its discriminant is $d^2-4d<0$; and $e^{\kappa }\ge 1+\kappa$. Thus the scalar ordinary differential equation for $\kappa$ points toward the unique value ${\kappa }_{\ast }$ satisfying $r({\kappa }_{\ast })=\nu$. Every trajectory with $s(0)>0$, $n(0)\ge 0$ has bounded $\kappa$ and $\kappa (\tau )\to {\kappa }_{\ast }$. Positivity of $s$ follows from $s(\tau )=s(0)\exp ({\int }_0^{\tau }g(\kappa (u))du)$.

If $0\le \nu <e^{-1}$, then ${\kappa }_{\ast }<1$ and $g({\kappa }_{\ast })<0$. Thus $s(\tau )$ decays exponentially for large $\tau$, andThis is finite-time draining of a fluid model. The unmodified equations have $n/s$ undefined at the origin, so the statement that trajectories converge to the origin needs this endpoint interpretation; continuing with an absorbing zero trajectory is an additional fluid-model convention, not a solution of the displayed equations at the origin.

If $\nu >e^{-1}$, then ${\kappa }_{\ast }>1$ and $g({\kappa }_{\ast })>0$. Now $s(\tau )$ grows exponentially, physical time tends to infinity, andIn particular the trajectory escapes to infinity. Even without the ratio analysis, $\dot{n}\ge \nu -e^{-1}>0$, since ${\max }_{\kappa \ge 0}\kappa e^{-\kappa }=e^{-1}$.

For the actual Markov chain, it is essential not to replace the finite-$N$ success probability by $e^{-1}$: a single backlogged packet can succeed with probability one. Instead, for $N\ge 2$, maximizing over $S\ge 1$ gives the ALOHA throughput boundIf $\nu >e^{-1}$, choose $K_0$ and $r_0<\nu$ so that $p_1(N,S)\le r_0$ for all $N>K_0$, uniformly in $S$. For sufficiently small $\theta >0$,because its derivative at zero is $r_0-\nu <0$. Independence of arrivals and attempts giveswhenever $N>K_0$. For any integer $K\ge K_0$, stop at the stopping time ${\sigma }_K=\inf \{t:N_t\le K\}$. The stopped process $e^{-\theta N_{t\wedge {\sigma }_K}}$ is a nonnegative supermartingale. The optional stopping theorem, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundFrom every state with $N\le K$, a Poisson distribution arrival burst has a uniformly positive probability of sending the next backlog to at least $K+m$, for any fixed $m>0$. From there the probability of never revisiting $N\le K$ is at least $1-e^{-\theta m}$. By the Markov property at successive visits, the probability of infinitely many visits to this strip is zero: each visit has a uniform positive chance of being the last. This holds for every integer $K\ge K_0$, soTherefore the Markov chain is transient for every finite choice of $a,b,c$. The proof is uniform in $S$ and does not infer stochastic transience merely from the approximate ordinary differential equations.

With independent Poisson arrivals of any positive rate and a fixed retry probability $0<f\le 1$, the infinite-population slotted ALOHA model eventually has collisions in every slot almost surely. For $f<1$, an exponential-supermartingale escape bound proves transience of the backlog chain. Bounded martingale increments then give backlog growth at the arrival rate, and the Conditional Borel-Cantelli lemma makes the exponentially unlikely noncollision slots finite in number. At $f=1$, two old packets suffice for permanent collisions. At $f=0$ the assertion is false.

A random access network lets stations make transmission attempts independently using a shared medium. A collision can prevent all attempted packets from being delivered; slotted ALOHA adjusts attempt probabilities using slot feedback.

This feedback family in slotted ALOHA gives $g(\kappa )=A\{2/(e-2)-[e/(e-2)](1+\kappa )e^{-\kappa }\}$, which changes sign at contention ratio one. For $0\le \nu <e^{-1}$, the ratio drift $h=\nu -\kappa e^{-\kappa }-\kappa g$ is strictly negative on $[1,\infty )$ and on some interval beginning below one. The ratio time change for a homogeneous fluid model traps the ratio in a region where $g<0$ and proves finite-time draining. For $\nu >e^{-1}$, backlog drift is at least $\nu -e^{-1}>0$ regardless of this controller. These are statements about the interior fluid model, not a stand-alone theorem of stochastic stability.