# Optimality of the Bayes classifier

Let $X$ be a random variable with values in $\mathcal{X}$ and $Y$ a random variable with values in $\{0,1\}$. Is it true that : $$\mathbb{P}(g(X) \ne Y) = \int_\mathcal{X} \mathbb{P}\big(g(X)\ne Y \hspace{1mm} \mid X=x\big)d\mathbb{P}_X(x)$$ ?

I agree with this equality in the case where $X$ is discrete (i.e $\mathcal{X}$ is a countable set), but I can't prove why it holds in the general setting where $X$ is not discrete and does not have a density function. Actually, I can't prove the equality when $X$ has a density neither.

I came across this equality in at least 2 articles about statistical learning theory :

The statements, whose proof uses the equality above, say that the Bayes classifier realizes the minimum of the risk $\mathbb{P}(g(X)\ne Y)$ over all measurable functions $g$.

There's no need to treat separately the cases where $X$ is discrete, continuous or neither. We are just taking an iterated expectation here, which is always permissible. The idea is that since probabilities are simply expectations of indicator random variables we can always write something like

\begin{align} P(g(X) \neq Y) &= \text{E} \left (I_{ \{ g(X) \neq Y \}} \right ) \\ &= \text{E} \left [ \text{E} \left (I_{ \{ g(X) \neq Y \}} \mid X \right ) \right ] \\ &= \text{E}[ P(g(X) \neq Y \mid X)] \end{align}

and the integral above is just another way of writing this down. Again, this holds true no matter what "type" of random variable $X$ happens to be.

• You are using $1_{\{g(X)\ne Y\} }= E ( 1_{\{g(X)\ne Y\}} / X)$. Is it because you consider that $1_{\{g(X)\ne Y\}}$ is $\sigma(X)$-measurable ?
• OK I got it. You didn't use the equality $1_{\{g(X)\ne Y\}} = E(1_{\{g(X)\ne Y\}}/X)$. You actually used $E(1_{\{g(X)\ne Y\}})=E [ E(1_{\{g(X)\ne Y\}} / X)]$, which is true for any sigma-algebra. This is what you called iterated expectation.
• I still have a question though. I know what is the probability of an event knowing another event, but I've never seen the probability of an event knowing a random variable. So I don't see what $P(g(X) \ne Y | X )$ means ???
• $P(g(X) \neq Y)$ is just a number, but $P(g(X) \neq Y \mid X)$ is a random function of $X$. For a more concrete example, imagine you roll a die, call the outcome $X$ and then flip a coin with probability of heads $1 / X$. $P(\text{heads})$ is some fixed number, but $P(\text{heads} \mid X) = 1 / X$. Sep 26 '16 at 13:30