# Concentration inequality for i.i.d. negative multinomial variables

Let $\mathbf p=(p_0,p_1,\cdots,p_m)$ be a probability vector, such that $p_0+p_1+\cdots+p_m=1$. Let $X_1,X_2,\cdots$ be i.i.d. random variables distributed according to the categorical distribution parameterized by $\mathbf p$, meaning that $\Pr[X_i=j] = p_j$ for $j=1,\cdots,m$.

Let $k$ be the first $X_k$ such that $X_k=0$. I'm interested in the random variable $Z := \sum_{i=1}^k{\mathbb I[X_i]=1}$. Namely, this is the number of occurreces of item 1 until $X_k=0$. It follows a negative multinomial distribution: https://en.wikipedia.org/wiki/Negative_multinomial_distribution

What I'm interested is the following question:

Let $Z_1,\cdots,Z_n$ be i.i.d. random variables defined in the above manner. How can we derive an upper bound of the tail probability $$\Pr\left[\left|\frac{1}{n}\sum_{i=1}^n{Z_i} - \mathbb EZ\right| > t\right]?$$

I think you can ignore every value of $X_i$ apart from occurrences of $0$ or $1$, and letting $q=\dfrac{p_0}{p_0+p_1}$, this suggests $Z$ has a geometric distribution on $\{0,1,2,3,\ldots\}$ with parameter $q$, so $\Pr[Z=z]=(1-q)^zq= \dfrac{p_1^zp_0}{(p_0+p_1)^{z+1}}$ and $\mathbb E[Z]= \dfrac{1-q}{q} = \dfrac{p_1}{p_0}$ and $\text{Var}(Z)=\dfrac{p_1}{p_0}+\dfrac{p_1^2}{p_0^2}$, meaning $S=\sum_1^n Z_i$ has a negative binomial distribution with $$\Pr[S=s] ={s+n-1 \choose s} \dfrac{p_1^sp_0^n}{(p_0+p_1)^{s+n}}$$ and $\mathbb E[S]= \dfrac{np_1}{p_0}$ and $\text{Var}(S)=\dfrac{np_1}{p_0}+\dfrac{np_1^2}{p_0^2}$ so $\mathbb E\left[\frac1nS\right]= \dfrac{np_1}{p_0}$ and $\text{Var}\left(\frac1nS\right)=\dfrac{p_1}{np_0}+\dfrac{p_1^2}{np_0^2}$
You want $\Pr\left[ S < \dfrac{np_1}{p_0} - nt \right]+\Pr\left[ S > \dfrac{np_1}{p_0}+nt\right]$ which you can calculate exactly as $$\Pr\left[\left|\frac{1}{n}\sum_{i=1}^n{Z_i} - \mathbb EZ\right| > t\right]=1 - \sum_{s=\big\lceil \frac{np_1}{p_0}-nt\big\rceil}^{\big\lfloor \frac{np_1}{p_0} +nt\big\rfloor}\Pr[S=s]$$ using the earlier expression for $\Pr[S=s]$, where $\lceil x\rceil$ is $x$ rounded up while $\lfloor x\rfloor$ is $x$ rounded down
So for example with $\mathbf p=\left(\frac12,\frac13,\frac16\right)$, $n=5$ and $t=\frac14$, I think you would get $1-\dfrac{13608}{78125} - \dfrac{54432}{390625}= \dfrac{268153}{390625}= 0.68647168$