# Check the validity of the distribution in the proof of No-Free-Lunch Theorem

I'm reading the proof of No-Free-Lunch Theorem (quoted at the end of this question) in Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, p.37, the author wrote:

Let $$C$$ be a subset of $$\mathcal{X}$$ of size $$2m$$. Note that there are $$T = 2^{2m}$$ possible functions from $$C$$ to $$\{0,1\}$$. Denote these functions by $$f_{1},...,f_{T}$$. For each such function, let $$D_{i}$$ be a distribution over $$C×\{0,1\}$$ defined by:

$$D_{i}(\{(x,y)\}) = \begin{cases} 1/|C|\text{ if }y=f_{i}(x)\\ 0 \text{ otherwise} \end{cases}$$

I'm suspecting that $$D_{i}$$ defined in this way is a valid distribution because even though on the surface we have $$|C|(1/|C|)=1$$, there's no guarantee that $$f_{i}$$ will return correct labels for all examples in $$C$$ and so the cumulative probability may less than $$|C|(1/|C|) = 1$$?

The Theorem stated in the book as follows:

Let $$A$$ be any learning algorithm for the task of binary classification with respect to the 0−1 loss over a domain X . Let m be any number smaller than $$|X|/2$$, representing a training set size. Then, there exists a distribution D over X ×{0,1} such that:

1. There exists a function $$f :X \to\{0,1\}$$ with $$L_{\mathcal{D}}(f)=0$$.
2. With probability of at least 1/7 over the choice of $$S \sim D^{m}$$ we have that $$L_{\mathcal{D}}(A(S)) ≥ 1/8$$.