Let $(X_1,\dotsc, X_k)$ be distributed multinomial with parameters $n, (p_1\dotsc,p_k)$ and suppose $p_1>p_j$ for $j\neq 1$ so that category 1 is the most likely outcome from any given realization. I am looking for an upper bound on the probability that $X_1$ will not be the maximum realized category i.e. $P(\max_j X_j\neq X_1)$. Does anyone know of a good reference for such a problem?
One approach I had is to look at $P(X_1-X_j\leq 0)$ for any $j$, which can be bounded using Hoeffding's inequality: https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
I can upper bound this uniformly for all $j$ i.e. a single bound derived using Hoeffding works. I can then bound $P(\cup_{j\neq 1} X_1-X_j\leq 0)$ using the sum by applying the uniform bound to each term in the sum. My issue is: I think the upper bound is too conservative, particularly if $k$ is large. I don't really have a theoretical reason to think so, just a hunch.
Any comments on how I might better approach this would be greatly appreciated!