Transforming a categorical distribution by repeating trials and taking a plurality Suppose you have a K-sided, weighted die. This is represented by a categorical distribution.
Now, let's say you roll the die N times, and then pick a "winner" by choosing whichever outcome has a plurality of the rolls. If there is a tie and nobody has a plurality, then there is a new outcome, which is "no winner."
This now yields a new categorical distribution derived from the old one, except with the "no winner" outcome added.
For N=1, you get the original distribution, and as N->infinity, I believe you get the uniform distribution on the modes of the original distribution.
How can I compute this categorical distribution from the original, given an arbitrary choice of N?
Alternatively, is there anything like this that handles the "no winner" case slightly differently, since it's pathological anyway? For instance, suppose you break ties by doing one more trial and trying again.
There ought to be some way to compute it from the multinomial distribution, but I'm really hoping the whole thing can be digested down into a simple expression of the original distribution.
 A: The win outcome is defined when there is a plurality, and at least $N=3$ trials would be needed. The possible win situations can be seen in the following table
\begin{array}{ll}
 \text{Number of trials ($N$)} & \text{Number of required outcomes to win}             \\
3                      & \text{3 or 2}                                         \\
4                      & \text{4 or 3 or 2*}                                   \\
5                      & \text{5 or 4 or 3 or 2*}                              \\
6                      & \text{6 or 5 or 4 or 3* or 2*}                        \\
7                      & \text{7 or 6 or 5 or 4 or 3* or 2*}                   \\
8                      & \text{8 or 7 or 6 or 5 or 4* or 3* or 2*}             \\
9                      & \text{9 or 8 or 7 or 6 or 5 or 4* or 3* or 2*}        \\
10                     & \text{10 or 9 or 8 or 7 or 6 or 5* or 4* or 3* or 2*}
\end{array}
where the star sign adds the condition that no other category (side) should happen the same number of times or more. For example, when $N=4$, if a category shows 4 or 3 times or if it happens two times and no other category happens 2 times then it is a win for that category.
A general expression for the marked cases (with a star) is not easy (for small $N$ they are easy to calculate though). This is the difference between winning by majority and winning by plurality. If we exclude cases that win by plurality, then a lower bound can be found. In such case, assume a category is represented by a random variable $X$ that can choose values $x_i$ for $i\in[1,K]$ and also assume the repeated trials are independent. Then for $N\ge 3$ we have
$$\Pr(x_i \text{ winning})>\sum_{j=\left \lfloor \frac{N}{2} \right \rfloor+1}^{N}\binom{N}{j}\left [ \Pr\left ( X=x_i \right ) \right ]^j$$
where $\Pr\left ( X=x_i \right )$ is the original probability of the category $x_i$.
