Proposition 2.4 -- the coupon collector's tail bound
ProvedMarkovMixing.coupon_tailmarkov-chainsmixing-timesprobability
For the coupon collector with types and any :
This bound drives the top-to-random shuffle analysis later in the series.
Preamble
import Definitions.Def_mm_classical
Formal statement
namespace MarkovMixing
/-- **Proposition 2.4** (LPW): the coupon collector time exceeds
`⌈n log n + cn⌉` with probability at most `e^{-c}`. -/
theorem coupon_tail (n : ℕ) (hn : 1 ≤ n) (c : ℝ) (hc : 0 < c) :
couponMissProb n ⌈(n : ℝ) * Real.log n + c * n⌉₊ ≤ Real.exp (-c) := by
sorry
end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 2.2, Proposition 2.4, p. 23