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$


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.