= Collision-path coupling for slotted ALOHA
{title2=$\mathbb P_b(\text{a future noncollision})\leq\varepsilon(b),\quad\varepsilon(b)\to0$}
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+npq^{n-1}]$. The <union bound> and the <Poisson distribution> give
$$
\varepsilon(b)=e^{-\nu}q^b\left[\frac{1+\nu+bp/q}{1-r}+\frac{p\nu r}{(1-r)^2}\right].
$$
Indeed $\mathbb E[q^{A_t}]=r^t$ and $\mathbb E[A_tq^{A_t}]=\nu tq r^t$. Thus $\varepsilon(b)\to0$. 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.
Back to article page
