No free lunch theorem proof Assume that learning algorithm $A$ is fixed. Let $D = \{(x_1,y_1),...,(x_N,y_N)\}$, $F$ is set of a data-generating functions(meaning $f \in F$ then $f(x_i) = y_i$ and that functions in $F$ are consistent with the data )and $h:X\rightarrow Y$ is a classifier trained by the algorithm $A$. $L(f(x),y) $ is 1/0-loss function. Then i want to show that $\frac{1}{|F|}\sum_{f \in F}E[L(f(q),h(q))] = \frac{1}{2}$ where $q$ is a test point such that $x_i \neq q$ for all $i$.
My attempt $E[L(f(q),h(q))] = E[I_{f(q) \neq h(q) }(q)] = P(\{f(q) \neq h(q))$ where $I_{f(q) \neq h(q) }(q)$ is an indicator function. How should i evaluate $P(\{f(q) \neq h(q)\})$? My intuition says that $P(\{f(q)\neq h(q)\}) = \frac{1}{2}$, but i cant come up with a formal argument for that.
Any help is apperciated.
Update:
Could i argue that if $h$ just makes a random-guess then the probability that the guess is correct is $\frac{1}{2}$ so therefore $P(\{h(q) \neq f(q)\}) = \frac{1}{2}$ and then the claim follows.
Update2:
If i think the problem this way: for all $f \in F$ there exists a classifier $h$ which is trainable by the algorithm $A$. I still need the fact that how good the classifier $h$ is, which is quite hard to find out
Update3
I assume that data-generating functions $f$ are equally likely and that $h$ is fixed. I still think how i define probability of goodness of $h$ given $f$.

For the usual set-up of the No Free Lunch theorem there's less here than meets the eye. The domain ${\cal X}$ is discrete, ${\cal F}$ is the (finite) set of all (deterministic) functions from ${\cal X}$ to $\{0,1\}$ such that $f(x_i)=y_i$ for data in the training set. That is, for every $x$ not in the training set, ${\cal F}$ contains exactly as many functions with $f(x)=1$ and $f(x)=0$, and that's why better-than-chance prediction is impossible.
In the question as given it's not clear what is random in the expectation, but the basic argument will be the same whatever it is.  If you want the average performance of $h$ over all possible test data (or, equivalently, over a random sample of test data drawn with equal probability from all possibilities), then you will be accurate exactly half the time with a binary $Y$. This is true regardless of your algorithm for choosing $h$: whatever $h$ is, for any given $x$ either $h(x)=1$ or $h(x)=0$ and each option is wrong exactly half the time.
The No Free Lunch theorem isn't actually very useful because we never actually care about the average performance with equal weight on all possible test data. It's mainly interesting because it shows you can't possibly have a proof that an algorithm A_1 is uniformly better than another algorithm A_2 (only that it's better on  some interesting subclass of problems)
