Let $X=\left(X_{1},...,X_{k}\right)$ be a random variable that follows a multinomial distribution with $n$ trials and $k$ categories, with probabilities $p_{1},...,p_{k}$ such that $p_{1}-\delta\geq p_{2}\geq...\geq p_{k}$ for some $\delta> 0$.
Let $\mathrm{mode}(X):=\left\{ i\ |\ \forall j\ X_{i}\geq X_{j}\right\} $ and $\mathrm{maj}(X)$ be the r.v. such that $$ \Pr(\mathrm{maj}(X)=i)=\frac{1\!\!1_{\left\{ i\in\mathrm{mode}(X)\right\} }}{\left|\mathrm{mode}(X)\right|} $$ i.e. $\mathrm{maj}(X)$ is the most frequent value in the realization of $X$ (breaking ties uniformly at random).
I'm interested in lower bounding $\Pr(\mathrm{maj}(X)=1)-\Pr(\mathrm{maj}(X)=2)$. For $n\in \Omega(\delta^{-2})$ we can use the Chernoff bound and for $n\in \Theta(\delta^{-2})$ we can use the Berry-Esseen inequality. But what can be said when $n\in o(\delta^{-2})$?
Some people told me I should find such estimates somewhere, but nobody could point out a reference. This is what I got so far.
Using the fact that the cumulative distribution of the binomial can be expressed in terms of the regularized incomplete beta function, I'm able to prove the following.
Lemma. For $k=2$ it holds $$ \Pr(\mathrm{maj}(X)=1)-\Pr(\mathrm{maj}(X)=2)\geq\sqrt{\frac{2n-2}{\pi}}\delta\left(1-\delta^{2}\right)^{\frac{n-2}{2}} $$
From the previous lemma, I can prove, inductively, a lower bound for general $k$ at the price of a multiplicative factor $e^{-c\left(k-2\right)}$ for some constant $c>0$: $$ \Pr(\mathrm{maj}(X)=1)-\Pr(\mathrm{maj}(X)=2)\geq \sqrt{\frac{2n-2}{\pi}}\frac{\delta\left(1-\delta^{2}\right)^{\frac{n-2}{2}}}{e^{\left(k-2\right)c}} $$
I don't think $\Pr(\mathrm{maj}(X)=1)-\Pr(\mathrm{maj}(X)=2)$ decays exponentially in $k$.
So, do anybody have a reference or some better bounds for the following?
Question. Give a good lower bound on $\Pr(\mathrm{maj}(X)=1)-\Pr(\mathrm{maj}(X)=2)$ when $n\in o(\delta^{-2})$.
