Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exercise 5.8 — a scheme that gives up has νc=∞\nu_c = \inftyνc​=∞

Proved
KellyStochasticNetworks.ack_scheme_summable_h

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

analysisprobabilitystochastic-networksstochastic-systems

Consider an acknowledgement-based scheme whose retransmission function is non-negative and summable, ∑x≥1h(x)<∞\sum_{x\ge1}h(x)<\infty∑x≥1​h(x)<∞. By the first Borel–Cantelli lemma a packet then makes only finitely many attempts — the scheme discards it after finitely many tries. Show that its critical rate is infinite: for every arrival rate ν>0\nu>0ν>0,

H(ν)=∑t≥1Pt=∞.H(\nu)=\sum_{t\ge1}P_t=\infty .H(ν)=t≥1∑​Pt​=∞.

The reason is immediate once stated: if St=∑r≤th(r)S_t=\sum_{r\le t}h(r)St​=∑r≤t​h(r) converges to a finite limit S∞S_\inftyS∞​, then Pt=(1+νSt)e−νStP_t=(1+\nu S_t)e^{-\nu S_t}Pt​=(1+νSt​)e−νSt​ converges to (1+νS∞)e−νS∞>0(1+\nu S_\infty)e^{-\nu S_\infty}>0(1+νS∞​)e−νS∞​>0, and a series whose terms do not tend to zero diverges.

This is the opposite extreme from the goal of this mission. A scheme that retransmits persistently enough to satisfy condition (5.7) jams at every positive rate; a scheme that gives up entirely has H(ν)H(\nu)H(ν) infinite at every positive rate, so infinitely many slots stay uncontested — at the cost of the packets it discarded. Between them lie the schemes with a finite positive νc\nu_cνc​, of which Ethernet is one.

Formalization Note "H(ν)=∞H(\nu)=\inftyH(ν)=∞" is stated as failure of summability of the sequence of slot probabilities, which is the form the argument produces and the form the definition of νc\nu_cνc​ uses.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_RandomAccess
Formal statement
namespace KellyStochasticNetworks

theorem ack_scheme_summable_h (h : ℕ → ℝ) (hh : ∀ x, 0 ≤ h x) (hsum : Summable h)
    (ν : ℝ) (hν : 0 < ν) : ¬ Summable (fun t : ℕ => ackSlotProb h ν (t + 1)) := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 125 (PDF p. 133), Exercise 5.8: 'Show that if sum_{x=1}^{infinity} h(x) < infinity a packet is transmitted at most a finite number of times (equivalently, it is discarded after a finite number of attempts), and that nu_c = infinity. [Hint: First Borel-Cantelli lemma.]' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

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