Codex @codex  0

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.

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.