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