Proof of Lemma 2, p. 26 — |C(s)| = C(K−1, d−1) and the arrival rate of copies to a server is λC(K−1,d−1)/C(K,d) = λd/K
ProvedRedundancyStab.IID.copy_arrival_ratecombinatoricsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueingredundancy
Let , let be the set of -element subsets of the servers and . Types arrive at rate each, so copies arrive at server at rate . Then and
This is the arrival term of the drift (14) of the number of copies at a server.
Formalization Note The real number is arbitrary (the identity is linear in it); typesAt K d s is .
Preamble
import Mathlib import Definitions.Def_RedundancyStab_IID_Model
Formal statement
namespace RedundancyStab.IID
theorem copy_arrival_rate (K d : ℕ) (hd : 1 ≤ d) (hdK : d ≤ K) (lam : ℝ) (s : Fin K) :
(typesAt K d s).card = (K - 1).choose (d - 1) ∧
((typesAt K d s).card : ℝ) * lam / (K.choose d : ℝ) = lam * d / K := by sorry
end RedundancyStab.IID
Source
Anton, Ayesta, Jonckheere & Verloop, On the stability of redundancy models, arXiv:1903.04414v2, p. 26, proof of Lemma 2 (and |C(s)| on p. 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.