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$.

Let $q \in X$ be a fixed test point and let $h$ be a classifier trained by the fixed learning algorithm $A$. Notice that $1_{\{f(q) \neq h(q)\}}(q) = (\frac{f(q)-h(q)}{2})^2$ since $f(x)^2=h(x)^2 = 1$ for all $x \in X$. Then we have that $\frac{1}{|F|}\sum_{f \in F}E[L(f(q),h(q))] = \frac{1}{|F|}\sum_{f \in F} E[1_{\{f(q) \neq h(q) \}}(q)] = \frac{1}{|F|}\sum_{f \in F} (\frac{f(q)-h(q)}{2}) ^ 2 = \frac{1}{2|F|}\sum_{f \in F}(1-h(q)f(q)) = \frac{1}{2}$
since $\sum_{f \in F}f(q) = 0$.
