Can someone help me with one step of the following proof of a multinomial concentration inequality taken from Lemma 3 of "The equivalence of weak, strong and complete convergence in l1 for kernel density estimate" (Devroye 83).
Let $p_1, p_2, ..., p_k$ be the parameter of a multinomial distribution ($\sum p_i = 1$). In $n$ experiments for some fixed $n$, let $X_i$ be the number of times that $i$ appears. $\sum_{i=1}^k X_i = n$
Now, let $N \sim $Poisson(n). After another $N$ experiments (completely independent of the previous n experiments), let $X'_i$ be the number of times that $i$ appears in these $N$ experiments. $\sum_{i=1}^k X'_i = N$. This is also known as Poissonization and each $X'_i$ is actually independent Poisson variable with parameter $np_i$.
I understand and can reproduce every other step except for the following inequality:
$$ P(\sum_{i=1}^k \frac{1}{n} |X_i - np_i| \geq \epsilon ) \leq P(|N-n| \geq \frac{2n\epsilon}{5}) + P(\sum_{i=1}^k\frac{1}{n} |X_i'- np_i| \geq \frac{3n\epsilon}{5}) $$
I'm not sure how he obtained this inequality. Also note how there seems to be an extra "n" in the second term. Inequality (2) (Which I think he used for this step) from the proof is the following simple observation: $$ \frac{1}{n} \sum_{i=1}^k |X_i - np_i| \leq \frac{1}{n}\sum_{i=1}^k |X_i-X'_i| + \frac{1}{n}\sum_{i=1}^k |X'_i - np_i| $$
Would greatly appreciate any help/suggestions/pointers to similar proofs. The full proof is pasted below for context:
Turns out that I needed to think about Poissonization in the right way to see this.
Fixing an n, $ U_1, U_2, ..., U_n $ are drawn from the multinomial distribution. Now imagine that these draws are snap-shots taken from another random process where we first pick the number of experiments according to $N \sim Poi(n)$, and then take $N$ draw from the multinomial distribution like before.
So there are two cases: if $ n \geq N$, we have something like: $$ U_1=U'_1, ..., U_N=U'_N, U_{N+1},..., U_n $$ On the other hand, if $N > n$: $$ U_1=U'_1,..., U_n=U'_n, U'_{n+1},..., U_N $$
So we have something rather surprising (to me at least) that is $|N-n| = \sum_{i=1}^k |X_i - X'_i|$. Combining with (2) in the proof and union bound argument, we get
$$ p(\sum_{i=1}^k \frac{1}{n} |X_i-np_i| \geq \epsilon) \leq p(\frac{1}{n}\sum_{i=1}^k |X_i-X'_i| + |X'_i - npi| \geq \epsilon) $$ $$ \leq p(\sum_{i=1}^k \frac{1}{n} |X_i-X'_i| \geq \frac{2\epsilon}{5}) + p(\sum_{i=1}^k \frac{1}{n} |X'_i - npi| \geq \frac{3\epsilon}{5}) $$ $$ = p(|N-n|\geq \frac{2n\epsilon}{5}) + p(|X'_i - npi| \geq \frac{3n\epsilon}{5}) $$
So there is actually an extra $\frac{1}{n}$ in the manuscript.