Let $(X_1, X_2, \cdots, X_d) \sim Multinomial(n,(p_1,p_2, \cdots, p_d) )$. I would like to have a high probability bound on $$ \sum_{i=1}^d |X_i - np_i|. $$

I know that the marginal of each $X_i$ is binomial, so can I use this term by term in the summation to get a high probability bound of like $\sum_{i=1}^d\sqrt{np_i(1-p_i)}$?


Using Chebyshev's inequality

$$P\left\{\sum_{i=1}^d |X_i-np_i|\ge t\right\}\le \sum_{i=1}^d P\left\{|X_i-np_i|\ge \frac{t}{d}\right\}\le \sum_{i=1}^d \frac{np_i(1-p_i)}{(t/d)^2}$$

Using Hoeffding's inequality

$$P\left\{\sum_{i=1}^d |X_i-np_i|\ge t\right\}\le 2d\exp \left\{-\frac{2t^2}{nd^2} \right\}$$

  • $\begingroup$ How did you get the second inequality in the Chebyshev inequality? $\endgroup$
    – jmmss4418
    Aug 6 '15 at 14:42
  • $\begingroup$ Ok, so the second inequality follows from $P(\sum|X_i-np_i| \geq t) \leq P( \max_i X_i \geq t/d)$. But why even go through the trouble of writing $|X_d - np_d|$ the way you did? A bound involving $d$ would be better than $2(d-1)$, right? $\endgroup$
    – jmmss4418
    Aug 6 '15 at 15:33
  • $\begingroup$ (1) $P(\sum|X_i-np_i| \geq t) \leq P(\cup_i \{X_i \geq t/d\}\}\le \sum P\{X_i\ge t/d\}$ $\endgroup$
    – d.k.o.
    Aug 6 '15 at 19:45
  • $\begingroup$ (2) Yeah. Rolled back to the original version ($(d-1)$ may be better only for small $d$-s) $\endgroup$
    – d.k.o.
    Aug 6 '15 at 20:02
  • $\begingroup$ Lots of details missing in this answer. For example, $p_j(1-p_j) \le 1/4$ is being used silently. $\endgroup$
    – dohmatob
    May 13 '19 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.