# Bounding $L^1$ norm of multinomial data

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\}$$

• How did you get the second inequality in the Chebyshev inequality? Aug 6 '15 at 14:42
• 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? Aug 6 '15 at 15:33
• (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\}$ Aug 6 '15 at 19:45
• (2) Yeah. Rolled back to the original version ($(d-1)$ may be better only for small $d$-s) Aug 6 '15 at 20:02
• Lots of details missing in this answer. For example, $p_j(1-p_j) \le 1/4$ is being used silently. May 13 '19 at 6:46