Contents
Optimality of Always Predicting the Most Likely Outcome
Theorem
Choosing the most likely outcome is the best you can do (better than choosing randomly from any distribution).
Proof
Consider a random experiment with 2 outcomes, 0 and 1.
Let E0 be the event that outcome 0 occurs and E1 be the event that outcome 1 occurs.
Let Pr(E0) = p and Pr(E1) = 1-p, where p is some fixed but arbitrary probability.
Assume, without loss of generality, that p ≥ 1/2. That is, that E0 is the most likely outcome.
Consider a joint, independent random experiment intended to predict the outcome of the first.
Let F0 be the event that outcome 0 is predicted and F1 be the event that outcome 1 is predicted.
Let Pr(F0) = q and Pr(F1) = 1-q.
An error occurs when we predict incorrectly. The probability of error is
$ \displaystyle P_{err} = Pr((E_0 \cap F_1) \cup (E_1 \cap F_0)) = Pr(E_0 \cap F_1) + Pr(E_1 \cap F_0) $.
By independence,
$ \displaystyle Pr(E_0 \cap F_1) = Pr(E_0) \cdot Pr(F_1) $
$ \displaystyle Pr(E_1 \cap F_0) = Pr(E_1) \cdot Pr(F_0) $.
So,
$ \displaystyle P_{err} = Pr(E_0) \cdot Pr(F_1) + Pr(E_1) \cdot Pr(F_0) = p(1-q) + (1-p)q = (1-2p)q + p $.
We would like to choose q ∈ [0, 1] to minimize Perr.
Since Perr is linear in q, the extrema are at the endpoints.
Evaluating at q = 0 and q = 1, we find the minimal Perr is 1-p at q = 1 (since p ≥ 1/2).
Thus, the optimal strategy for predicting the outcome of the first experiment is:
Always (with probability q = 1) predict E0, the most likely outcome.
Futhermore, Perr is a strictly decreasing function of p on the interval p ∈ [1/2, 1].
That is, as p goes from 1/2 to 1, the accuracy of the prediction increases.
This is consistent with the information theoretic description of entropy (which has its maximum at p = 1/2) as the "average uncertainty in the outcome".
Clearly, the less uncertain the outcome is, the better we should expect to be able to predict it.
Example
Consider two approaches for predicting an experiment with p = 0.8 (i.e. E0 occurs with probability 0.8 and E1 occurs with probability 0.2).
Approach 1
In the first approach we proceed as above and always predict F0 (i.e Pr(F0) = q = 1, Pr(F1) = 1-q = 0).
With this approach we have
$ \displaystyle Pr(E_0 \cap F_0) = 0.8 $
$ \displaystyle Pr(E_0 \cap F_1) = 0 $
$ \displaystyle Pr(E_1 \cap F_0) = 0.2 $
$ \displaystyle Pr(E_1 \cap F_1) = 0 $
$ \displaystyle P_{err} = Pr(E_0 \cap F_1) + Pr(E_1 \cap F_0) = 0.2 $
Approach 2
In the second approach we predict randomly according to the distribution of the first experiment (i.e. Pr(F0) = q = 0.8, Pr(F1) = 1-q = 0.2).
With this approach we have
$ \displaystyle Pr(E_0 \cap F_0) = 0.64 $
$ \displaystyle Pr(E_0 \cap F_1) = 0.16 $
$ \displaystyle Pr(E_1 \cap F_0) = 0.16 $
$ \displaystyle Pr(E_1 \cap F_1) = 0.04 $
$ \displaystyle P_{err} = Pr(E_0 \cap F_1) + Pr(E_1 \cap F_0) = 0.32 $
The error in the second approach is greater than the error in the first approach.
Therefore, always choosing the most likely outcome is better than choosing randomly according to the distribution.
--Jvaught 19:59, 26 January 2010 (UTC)
Minor edits and reformatting, Pritchey 10:55, 28 January 2010 (UTC)
