Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Random access: the ALOHA slot probabilities and the critical rate of a backoff scheme

Definition
KellyStochasticNetworks_RandomAccess

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

operations-researchprobabilitystochastic-networksstochastic-systems

The random access model of Chapter 5 of Kelly and Yudovina, Stochastic Networks.

Time is slotted and a transmission attempt occupies one slot. New packets arrive in a Poisson stream of rate ν\nuν. A slot with exactly one attempt carries its packet; a slot with two or more is a collision and carries nothing.

ALOHA. After an unsuccessful attempt a station retransmits with probability fff in each following slot. With a backlog of nnn packets awaiting retransmission, exactly one transmission is attempted with probability

e−ν nf(1−f)n−1  +  νe−ν(1−f)n,e^{-\nu}\,n f (1-f)^{n-1} \;+\; \nu e^{-\nu}(1-f)^{n},e−νnf(1−f)n−1+νe−ν(1−f)n,

the two terms being "no new packet and exactly one retransmission" and "one new packet and no retransmission". In the proof of Proposition 5.3, p(n)p(n)p(n) denotes the probability that the channel unjams before the backlog increases, given backlog nnn:

p(n)=e−ν(1+ν)(1−f)n+e−νnf(1−f)n−11−e−ν(1−(1−f)n−nf(1−f)n−1).p(n)=\frac{e^{-\nu}(1+\nu)(1-f)^{n}+e^{-\nu}n f(1-f)^{n-1}} {1-e^{-\nu}\bigl(1-(1-f)^{n}-nf(1-f)^{n-1}\bigr)} .p(n)=1−e−ν(1−(1−f)n−nf(1−f)n−1)e−ν(1+ν)(1−f)n+e−νnf(1−f)n−1​.

Acknowledgement-based schemes. A station learns nothing about the channel except whether its own transmissions succeeded. A packet attempts transmission xxx slots after arrival with probability h(x)h(x)h(x), independently across packets, with h(1)=1h(1)=1h(1)=1. On a channel externally jammed from time 000, every retransmission occurs, the number of attempts in slot ttt is Poisson with mean ν∑r=1th(r)\nu\sum_{r=1}^{t}h(r)ν∑r=1t​h(r), and the probability that fewer than two attempts are made in slot ttt is

Pt=(1+ν∑r=1th(r))exp⁡(−ν∑r=1th(r)).P_t=\Bigl(1+\nu\sum_{r=1}^{t}h(r)\Bigr)\exp\Bigl(-\nu\sum_{r=1}^{t}h(r)\Bigr).Pt​=(1+νr=1∑t​h(r))exp(−νr=1∑t​h(r)).

The expected number of such slots is H(ν)=∑t≥1PtH(\nu)=\sum_{t\ge1}P_tH(ν)=∑t≥1​Pt​, and the critical rate is νc=inf⁡{ν:H(ν)<∞}\nu_c=\inf\{\nu : H(\nu)<\infty\}νc​=inf{ν:H(ν)<∞}. ALOHA is the scheme with h(x)=fh(x)=fh(x)=f for every x>1x>1x>1.

Formalization Note The retransmission function is any real sequence; non-negativity and the normalization h(1)=1h(1)=1h(1)=1 are imposed as hypotheses where a statement needs them rather than built in, so that comparison schemes are expressible. The probabilities PtP_tPt​, p(n)p(n)p(n) and the ALOHA success probability are defined by their closed forms, as the book displays them; the Poisson and binomial derivations behind those forms are not part of the definitions.

Definition code
import Mathlib

namespace KellyStochasticNetworks

/-- `ackAttemptRate h t = h(1) + ⋯ + h(t)`.  In an acknowledgement-based scheme, `h x` is the
probability that a packet attempts transmission `x` slots after its arrival (`h 1 = 1`), and on
an externally jammed channel the number of attempts in slot `t` is Poisson with mean
`ν · ackAttemptRate h t`.  Kelly–Yudovina, *Stochastic Networks*, p. 120. -/
def ackAttemptRate (h : ℕ → ℝ) (t : ℕ) : ℝ := ∑ r ∈ Finset.Icc 1 t, h r

/-- `P_t`, the probability that fewer than two transmission attempts are made in slot `t` of the
externally jammed channel: `(1 + ν ∑_{r ≤ t} h(r)) exp(-ν ∑_{r ≤ t} h(r))`. -/
noncomputable def ackSlotProb (h : ℕ → ℝ) (ν : ℝ) (t : ℕ) : ℝ :=
  (1 + ν * ackAttemptRate h t) * Real.exp (-(ν * ackAttemptRate h t))

/-- The ALOHA retransmission function of Example 5.8: `h 1 = 1`, and `h x = f` for `x > 1`. -/
def alohaH (f : ℝ) : ℕ → ℝ := fun x => if x = 1 then 1 else f

/-- `p(n)`, the probability that the ALOHA channel unjams before the backlog increases, given a
backlog of `n` packets.  Kelly–Yudovina, p. 111, in the proof of Proposition 5.3. -/
noncomputable def alohaUnjamProb (ν f : ℝ) (n : ℕ) : ℝ :=
  (Real.exp (-ν) * (1 + ν) * (1 - f) ^ n + Real.exp (-ν) * (n : ℝ) * f * (1 - f) ^ (n - 1))
    / (1 - Real.exp (-ν) * (1 - (1 - f) ^ n - (n : ℝ) * f * (1 - f) ^ (n - 1)))

/-- The probability that exactly one transmission is attempted in an ALOHA slot with backlog `n`:
`e^{-ν} n f (1-f)^{n-1} + ν e^{-ν} (1-f)^n`.  Kelly–Yudovina, p. 110. -/
noncomputable def alohaSuccessProb (ν f : ℝ) (n : ℕ) : ℝ :=
  Real.exp (-ν) * ((n : ℝ) * f * (1 - f) ^ (n - 1)) + ν * Real.exp (-ν) * (1 - f) ^ n

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, ch. 5, pp. 109-123 (PDF pp. 117-131): the ALOHA protocol and the success probability P(Z_t = 1 | N_t = n) pp. 109-110, the unjamming probability p(n) in the proof of Proposition 5.3 p. 111, the acknowledgement-based model and the retransmission function h pp. 119-120, and P_t, H(nu) and nu_c p. 120. sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me