Probability of majority vote to be correct Let $X$ be a random variable taking values from $[k] = \{1, 2, ..., k\}$ with probabilities $p_1, ..., p_k$, respectively. Suppose that $X$ is slightly more likely to be 1: there exists some $\epsilon > 0$ such that for all $1 < i \leq k$, $p_1 - p_i \geq \epsilon$.
Now, suppose we have $n$ independent copies of $X$: $X_1, X_2, ..., X_n$. For each $j \in [k]$, define the random variable $Y_j$ to be the "number of votes" for $j$: $Y_j := |\{t \in [n] : X_t = j\}|$.
Define the majority random variable $M$ to be the "winner candidate", i.e. the arg-max of $Y_1,...,Y_k$ (if there is more than a single maximizer, $M$ equals one of them arbitrarily. In order to make $M$ well defined, assume it equals the smallest such index).
I want to bound the probability that $M \neq 1$. For $k=2$ the problem is well-known and an exponential bound is not difficult to obtain.
My attempt
I am not sure about it at all, but this is what I tried. From the union bound,
$$\Pr[M \neq 1] \leq \Pr[\exists i\neq 1: Y_i > Y_1] \leq \sum_{i=2}^k \Pr[Y_i > Y_1] \text{ ,}$$
And by the law of total probability,
$$\Pr[Y_i > Y_1] = \sum_{t=0}^n \Pr[Y_i >Y_1 | Y_i + Y_1 = t]\Pr[Y_1 + Y_i = t]$$
Now $\Pr[Y_i+Y_1 = t]$ is like Binomial random variable with success probability $p_1 + p_i$, which is smaller than $2p_1 -\epsilon$ by the assumption on $X$. Thus, $\Pr[Y_1 + Y_i = t] \leq {n \choose t}(2p_1 - \epsilon)^t (1-2p_1 + \epsilon)^{n-t}$.
Furthermore, $\Pr[Y_i >Y_1 | Y_i + Y_1 = t] = \Pr[Y_1 \leq t/2 - 1 | Y_1 + Y_i = t]$. I think that this is like asking what is the probability that a Binomial random variable $B(t, p_1)$ is smaller than $t/2$. I can bound it using Hoeffding's inequality:
$$ \Pr[Y_i >Y_1 | Y_i + Y_1 = t] \leq e^{-2t(p_1 - 1/2)^2}.$$
Then I can combine the two results and conclude that
$$\Pr[M \neq 1] \leq (k-1)  \sum_{t=0}^n e^{-2t(p_1 - 1/2)^2} {n \choose t}(2p_1 - \epsilon)^t (1-2p_1 + \epsilon)^{n-t}. $$
My issue with this solution (beyond just not being sure if that's right) is that if $p_1 = 1/2$ I would expect the majority to be $1$ with overwhelming probability, but this bound does not capture this behaviour, which makes me trust it even less.
 A: Possible approach / too long for a comment.
Informal reasoning: Out of all the variables $Y_i$, in a sense the most "important" one is $Y_1$, and it is most "important" to get its value right.
You want the event $E = \{\exists i > 1: Y_i > Y_1\}$, and you want to model $E$ as the union of events $E_i = \{Y_i > Y_1\}$ and then approximate using the union bound.  The $E_i$ events are clearly dependent, but worse, IMHO they are positively correlated, because they are "mainly" dependently through the value of $Y_1$:  If $Y_1$ is "large", all the $P(E_i)$ will be small, while if $Y_1$ is "small", all the $P(E_i)$ will be large.
Now the union bound is tight when the events are mutually exclusive, so using it on "positively correlated" events leads to a big error.
Possible approach: I would suggest conditioning all your calculations on $Y_1 = y$, i.e.
$$P(E) = \sum_y P(Y_1 = y) P(E \mid Y_1 = y) \le \sum_y P(Y_1 = y) \sum_i P(E_i \mid Y_1 = y)$$
I think this captures much of the dependence between the $E_i$ events, and leads to a smaller overall error in the way union bound is deployed.  Or look at it another way, I think that, when conditioned on $Y_1 = y$, the events $E_i$ become less positively correlated (closer to independent, still not exclusive by any stretch).
As a small bonus, the values involved are all binomial:

*

*$P(Y_1 = y) = P(Bin(p_1, n) = y) $, and


*$P(E_i \mid Y_1 = y) = P(Bin(\frac{p_i}{1 - p_1}, n-y) >y)$.  I am not personally familiar with bounds for "binomial tails", but you seem to know of at least one (Hoeffding's) and I assume there are good bounds available.  At worst, if you can live with an approximation (not a bound) then the Gaussian approximation works very well in practice for large $n$.
If you actually pursue this further, I'd be curious to know how well it works.  If not, hopefully you find the discussion interesting anyway.  :)
