Minimum probability of a repitition

Question

Let's say we have an experiment, and the outcome is described by a random Variable $X$ with sample space $\Omega = \{x_1, x_2, ..., x_n\}$. We observe the outcome of the experiment twice (the results are independant). What I am interested in is the probability that the same event occurs twice (regardless which of the events it is). My intuition is that the probability that some event occurs twice is minimized when the probabilities of all events are evenly distributed.

Let's look at an example (flipping a coin). First let's say the coin is fair. Then the probability of the same outcome twice is obviously:

$Pr[X_1=\textrm{head} \wedge X_2 = \textrm{head}] + Pr[X_1=\textrm{tail} \wedge X_2 = \textrm{tail}] = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2}$

And now the same thing with an unfair coin ($Pr[X=\textrm{head}]=\frac{1}{4}, Pr[X=\textrm{tail}]=\frac{3}{4}$). Then we get:

$Pr[X_1=\textrm{head} \wedge X_2 = \textrm{head}] + Pr[X_1=\textrm{tail} \wedge X_2 = \textrm{tail}] = \frac{1}{4} \cdot \frac{1}{4} + \frac{3}{4} \cdot \frac{3}{4} = \frac{1}{16} + \frac{9}{16} = \frac{10}{16}$

Therefor the probability of observing the same event twice is smaller in case the probability is evenly distributed. I want to know if this generalizes for more than two events (and how this can be proved).

Answer 1

Probability that the same event occurs twice is $\sum p_i^2$, which we want to minimize. And, our constraints are $\sum_i p_i=1$, $p_i\geq 0$. This is a constrained optimisation problem, and the Lagrangian can be formulated as: $$L=\sum p_i^2-\lambda \left(\sum p_i-1\right)$$ (I've relaxed the constraint $p_i\geq 0$ but even so, the solution satisfy this one as well). When we solve for $\frac{\partial L}{\partial p_i}=0$, we have $p_i=\lambda/2$, which is a constant. This means $p_i=p_j$ for all $i,j$. And, the expression is minimised when all probabilities are equal. Therefore, the probability is minimum when there is most uncertainty around.

A more elementary way (over @whuber's suggestion): For any unequal $p_i,p_j$ pair, you could replace both of them by $(p_i+p_j)/2$, i.e. $p_{i,new}=p_{j,new}=(p_i+p_j)/2$. This still satisfies $\sum p_i=1$ and $p_i\geq 0$, and the decrease we have is

$$p_i^2+p_j^2-\frac{(p_i+p_j)^2}{2}=(p_i-p_j)^2/2$$

which is always $>0$ when $p_i\neq p_j$ for any pair $i,j$.