# Prove the probability of misclassification for K classes

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!

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\}$$.
• Yes, it's just $1-P(X=x)=P(X\neq x)$, did you notice that? – gunes Oct 28 '20 at 20:41