Slotted ALOHA

Time is divided into slots, and a slot succeeds exactly when one station transmits. With backlog $N$ and independent attempt probability $p$, the success probability is $Np(1-p{)}^{N-1}$. Fluid approximation of slotted ALOHA replaces the large-system binomial probabilities by Poisson probabilities.

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.

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

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.

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.

When backlog $N$ and attempt-control scale $S$ are large with $N/S\approx \kappa$, idle and success probabilities approach $e^{-\kappa }$ and $\kappa e^{-\kappa }$. Expected update increments then motivate a fluid model described by ordinary differential equations.

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.

For $N\ge 2$ backlogged stations, the largest one-slot success probability is $(1-1/N{)}^{N-1}$, attained at $p=1/N$. Its limit is $e^{-1}$; the exact finite-$N$ maximum is larger, and for $N=1$ it is one.