Does an optimal linear classifier perform no better then chance iff class distributions have the same mean? Assuming there is some nice $P(x, y)$ over $\mathbb R^n \times \{0, 1\}$, can we claim that: The expected accuracy of the optimal linear classifier trained on a large sample from $P(x, y)$ would not exceed 0.5 if and only if $$\mathbb E[x|y=0] = \mathbb E[x|y=1]$$?
I mean, something like:
$$ P \Big[\mathcal R_P(h^*) \geq 0.5 + \delta \Big] \leq \text{veryfastdecrease}(\delta) \iff \mathbb E[x|y=0] = \mathbb E[x|y=1] $$
Where 


*

*$\mathcal R_P (h) = \mathbb E_{x, y\sim P}[h(x) \neq y]$

*$h^* = \arg\min_{h\in H}\mathcal R_P(h)$

*$H = \{h : x \mapsto \text{sign}(Ax+b)\}$


Thank you.
 A: The answer is no. I'll show a simple counterexample where $p(x \mid y=0)$ and $p(x \mid y=1)$ have the same mean, but it's possible to construct a linear classifier with misclassification rate better than chance. (Side note: chance-level performance is only 0.5 when the marginal probabilities of each class are equal; if one class were more probable than the other, we could always output that class as our prediction and be right most of the time).
Let's consider a one-dimensional case, with $X \in \mathbb{R}$. Inputs from the first class have a uniform distribution on the interval $[0, a]$:
$$P(x \mid y=0)
= \left \{ \begin{array}{cl}
  \frac{1}{a} & \text{if } 0 \le x \le a \\
  0 & \text{otherwise}
\end{array} \right .$$
Inputs from the second class have an exponential distribution, with mean equal to that of the uniform distribution (i.e. $\frac{a}{2}$):
$$P(x \mid y=1)
= \left \{ \begin{array}{cl}
  \frac{2}{a} e^{-\frac{2}{a} x} & \text{if } x \ge 0 \\
  0 & \text{otherwise}
\end{array} \right .$$
Here's a plot of the input distribution for each class when $a=3$:

Construct a classifier $f_t$ with threshold $t \ge 0$, such that the predicted class is 0 if the input is less than or equal to the threshold, and 1 if the input exceeds the threshold. This classifier is trivially linear because we're using the input itself as the decision variable.
$$f_t(x)
= \left \{ \begin{array}{cl}
  0 & \text{if } x \le t \\
  1 & \text{otherwise} \\
\end{array} \right .$$
We can measure the the classifier's performance for a given threshold using the misclassification rate (i.e. expected value of the 0-1 loss).
$$L(t) = \int_{-\infty}^t P(x \mid y=1) p(y=1) dx
+ \int_t^\infty P(x \mid y=0) p(y=0) dx$$
Say the classes are equiprobable, so $p(y=0) = p(y=1) = 0.5$. So, chance-level performance is 0.5. Plugging everything in, we have:
$$\begin{array}{ccl}
  L(t) & = & \int_{0}^t \frac{1}{a} e^{-\frac{2}{a} x} dx
             + [t \le a] \int_t^a \frac{1}{2a} dx \\
       & = & \frac{1}{2} - \frac{1}{2} e^{-\frac{2t}{a}}
             + [t \le a] \left ( \frac{1}{2} - \frac{t}{2a} \right )
\end{array}$$
where $[\cdot]$ is the Iverson bracket, which returns 1 when its argument is true, otherwise 0.
The misclassification rate can be less than 0.5 (chance level in this case). Here's the misclassification rate as a function of the threshold, for the same example input distributions as above ($a=3$):

