Limit of multinomial distributions Let $(X_1, X_2, ..., X_n)$ follow a multinomial distribution with parameters $n$ and $\mathbf{p}=(p_1, p_2,..., p_n) = (p+ \frac{1-p}{n}, \frac{1-p}{n},...,\frac{1-p}{n})$.
I am trying to prove that $\mathbb{P}(\max_k X_k \neq X_1) \to 0$ as $n\to \infty$. My idea is to first use the sub-additivity property to write $\mathbb{P}(\max_k X_k \neq X_1) \leq \mathbb{P} (\cup_{k=2}^n \{ X_k \geq X_1\}) \leq \sum_{k=2}^n \mathbb{P}(X_k \geq X_1)$ and then prove that for a fixed $k\ne 1$, the quantities $ \mathbb{P}(X_k \geq X_1) = O(1/n^2)$, say. I strongly believe that this is the case as $\mathbf{E}[X_1] \sim np$ and $\mathbf{E}[X_k] = 1-p$ for $k\ne 1$, but I seem to be caught in some nasty loop trying to prove this.

I think Hoeffding's inequality
is enough to show $P(X_k \ge X_1)$ is small.
Let $Z_1,\ldots,Z_n$ be i.i.d., each taking values $1$, $0$, and $-1$ with respective probabilities $\frac{1}{n}(1-p)$, $\frac{n-2}{n}(1-p)$, and $p+\frac{1}{n}(1-p)$.
Then
$$X_k - X_1 \overset{d}{=} Z_1 + \cdots + Z_n.$$
We have $E[Z_i]=-\frac{p}{2}$ for each $i$, so Hoeffding's inequality implies
$$P(X_k \ge X_1) = P(Z_1+\cdots+Z_n \ge 0) \le \exp\left(-\frac{2(np/2)^2}{4n}\right) = \exp(-p^2 n/8).$$
Plugging this into your union bound should give you what you need.
