Prove the probability of misclassification for K classes

Question

Problem: Consider a classifier C with K class labels trained on $(Y_i, X_i)$, $i = 0, . . . , n.$ Let $(Y_0, x_0)$ be a test observation and $\hat{Y}_0$ be the predicted class label (by $C$ ) for $x_0$. Prove that the probability of misclassification $P(\hat{Y}_0 \ne Y_0|x_0)$ satisfies $P(\hat{Y}_0 \ne Y_0|x_0) ≥ 1 − \max_{\{ k=1,...,K \}} P(Y_0 = k|x_0)$ .

My thinking: Let us suppose we have K classes $C_0, C_1, C_2,…C_{k-1}$. Then Bayes formula gives us:

$P(Y_0 = k|x_0)= \frac{P(x_0)\times P(Y_0=k)}{\sum^{k-1}_k{P(x_0)\times P(Y_0=k)}}$

The Bayes Rule for Minimum Error is to classify a case as belonging to $C_j$ if

${P(x_0)\times P(Y_0=k)} \ge \max_{\{ k=1,...,K \}}{P(x_0)\times P(Y_0=k)} $

Then I could not figure it to move further. I appreciate your suggestions. Thanks!

Answer 1

Substitute $P(\hat Y_0\neq Y_0|x_0)=1-P(\hat Y_0=Y_0|x_0)$, and you get $$P(\hat Y_0=Y_0|x_0)\leq \max_{k=1..K}P(Y_0=k|x_0)$$ which is true because $Y_0\in\{1...K\}$.