Latest revision as of 09:40, 1 February 2010

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 E₀ be the event that outcome 0 occurs and E₁ be the event that outcome 1 occurs.

Let Pr(E₀) = p and Pr(E₁) = 1-p, where p is some fixed but arbitrary probability.

Assume, without loss of generality, that p ≥ 1/2. That is, that E₀ is the most likely outcome.

Consider a joint, independent random experiment intended to predict the outcome of the first.

Let F₀ be the event that outcome 0 is predicted and F₁ be the event that outcome 1 is predicted.

Let Pr(F₀) = q and Pr(F₁) = 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 P_err.

Since P_err is linear in q, the extrema are at the endpoints.

Evaluating at q = 0 and q = 1, we find the minimal P_err 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 E₀, the most likely outcome.

Futhermore, P_err 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. E₀ occurs with probability 0.8 and E₁ occurs with probability 0.2).

Approach 1

In the first approach we proceed as above and always predict F₀ (i.e Pr(F₀) = q = 1, Pr(F₁) = 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(F₀) = q = 0.8, Pr(F₁) = 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)

Back to ECE662_topic2_discussions

Back to 2010 Spring ECE 662 mboutin