Guessing game of three imbalanced classes Let's imagine we have the following distribution of three classes of data points: A 50%, B 30%, C 20%. What is the guessing strategy that maximizes the number of correct guesses?
Considering 1000 data points for concreteness, I am surprised that randomly guessing A 500 times, B 300 times and C 200 times (250+90+40=380 correct guesses) is inferior to always guessing A (500 correct guesses). Is always guessing A the optimal guessing strategy in this sense for this distribution? Is there a generally optimal guessing strategy if the distribution is known?
 A: Suppose there is a known collection of objects $i, i\in \mathcal S$, each with known probability $\pi_i$ of occurring.  The most general guessing strategy which is independent of any other information about the occurrence of  $i$ consists of guessing the value $i$ with probability $p_i.$  In this case, because the occurrence and the guess are independent, the chance of guessing $i$ correctly equals the chance that $i$ occurs times the chance you guess $i$.  Summing over all the possibilities gives
$$P(\mathbf p) = \sum_{i\in \mathcal S} \pi_i p_i$$
for the chance of a correct guess.
This is a linear function of the $p_i$ subject to linear constraints (namely, all $p_i$ are nonnegative and they all sum to $1$), thereby making it amenable to many optimization techniques (it is a linear program).  A simple version of Hölder's Inequality asserts the chance cannot exceed the largest occurrence probability:
$$P(\mathbf p) = |P(\mathbf p)| \le \left(\max_{i\in \mathcal S} |\pi_i|\right)\left(\sum_{i\in\mathcal S} |p_i|\right) \le \max_{i\in \mathcal S} \pi_i.$$
These inequalities used the facts that (a) all probabilities are nonnegative, so that $|p_i|=p_i$ and $|\pi_i|=\pi_i,$ and (b) the sum of your guessing probabilities cannot exceed $1.$  (It could be less than $1$ if you were ever to guess a value that is not in $\mathcal S$ at all.)
Moreover, the largest value is obviously attainable: always guess any of the $i$ for which $\pi_i$ is the largest.  This justifies and generalizes the conclusion you arrived at for the case $\mathcal S = \{A,B,C\}$ with $\mathbf \pi = (0.5, 0.3, 0.2).$
Comments

*

*Observe that setting $p_i=\pi_i$ (guessing each $i$ at the same rate it is known to occur) yields a success rate of $\sum_{i\in\mathcal S} \pi_i^2.$  This is always strictly less than the largest $\pi_i$ unless all the $\pi_i$ are equal.


*Note that no assumptions whatsoever are made about the number of elements of $\mathcal S:$ in particular, it can be infinite (even uncountably so).  Of course at most a countable number of elements $i\in \mathcal S$ can have positive probabilities of occurring or being guessed.


*Because this analysis is straightforward and elementary, it needs no references: I'm sure these results have been known for a very long time (at least when $\mathcal S$ is finite).
