Linear separability

(Cover, 1965)  Suppose we have \(N\) data points distributed at random in \(\mathbb{R}^d\) with an unspecified distribution.  Assume that there is no subset of \(d\) or fewer points which are linearly dependent.  We then assign each of the points to one of the two classes \(\mathcal{C}_1\) and \(\mathcal{C}_2\) with equal probability.

The fraction \(F(N,d)\) of realizations that is linearly separable is given by the expression
\[ F(N,d) = \left\{
    \begin{matrix}
    1 \quad &\mathrm{when}\; N \le d+1 \\
    \frac{1}{2^{N-1}}\sum\limits_{i=0}^d \left( \begin{matrix} N-1 \\ i \end{matrix} \right) \quad & \mathrm{when}\; N \ge d + 1
    \end{matrix}\right.
  \] Intuitively, the probability of separability increase with increasing dimension \(d\).

[TODO] include plot...

http://www-isl.stanford.edu/~cover/papers/paper76.pdf