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.

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.