Independent trials succeed with probability p. For T counting trials through first success, compare exact P(Tm) with…
Quant ResearchLevel: IntermediateExact tail versus generic bound
Independent trials succeed with probability p. For T counting trials through first success, compare exact P(T>m) with what the mean alone can guarantee.
Hints
- No success in the first m trials defines the tail.
- For an integer T, >m is >=m+1.
Answer
Exactly P(T>m)=(1-p)^m. Since T is integer and E[T]=1/p, Markov gives P(T>m)=P(T>=m+1)<=1/[p(m+1)], capped at one. The exact tail decays exponentially, the generic bound only polynomially.
Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial