Section 5.1 — the ALOHA backlog drifts upward once it is large
ProvedKellyStochasticNetworks.aloha_drift_positiveIn the ALOHA protocol with arrival rate and retransmission probability , the backlog of packets awaiting retransmission is a Markov chain with drift
where is the probability that exactly one transmission is attempted. Three facts.
- For that probability factors as
which is the form in which the book states the drift condition. 2. It tends to as , for any fixed . 3. Consequently, for every there is a backlog beyond which the drift is strictly positive: the success probability is eventually smaller than .
The reading is the one the book draws: whatever the arrival rate, once the backlog is large enough ALOHA's collisions make it grow larger still. Note what this does not establish — positive drift does not imply transience, as Remark 5.2 shows with an explicit recurrent chain of positive drift. The stronger conclusion, that ALOHA jams forever, is Proposition 5.3.
Formalization Note The success probability is the closed form of the definition item; the Poisson-plus-binomial derivation of it is not part of this statement. The factorization is asserted only for , where means what it should.
import Mathlib import Definitions.Def_KellyStochasticNetworks_RandomAccess
namespace KellyStochasticNetworks
theorem aloha_drift_positive (ν f : ℝ) (hν : 0 < ν) (hf : 0 < f) (hf1 : f < 1) :
(∀ n : ℕ, 1 ≤ n → alohaSuccessProb ν f n
= Real.exp (-ν) * ((n : ℝ) * f + (1 - f) * ν) * (1 - f) ^ (n - 1))
∧ Filter.Tendsto (fun n : ℕ => alohaSuccessProb ν f n) Filter.atTop (nhds 0)
∧ ∃ N : ℕ, ∀ n ≥ N, alohaSuccessProb ν f n < ν := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.