# Understanding no free lunch theorem

From Wikipedia:

$Y^X$ is the set of all objective functions $f$:$X$→$Y$, where $X$ is a finite solution space and $Y$ is a finite poset. The set of all permutations of $X$ is $J$. A random variable $F$ is distributed on $Y^X$. For all $j$ in $J$, $F o j$ is a random variable distributed on $Y^X$, with $P(F o j = f) = P(F = f o j^{–1})$ for all $f$ in $Y^X$.

Let $a$($f$) denote the output of search algorithm $a$ on input $f$. If $a$($F$) and $b$($F$) are identically distributed for all search algorithms $a$ and $b$, then $F$ has an NFL distribution. This condition holds if and only if $F$ and $F o j$ are identically distributed for all $j$ in $J$. In other words, there is no free lunch for search algorithms if and only if the distribution of objective functions is invariant under permutation of the solution space.

Update:

1. I was wondering if the no free lunch theorem can be equivalently formulated in a pure probability theoretical way as:

$X$ is a finite set and $Y$ is a finite set (not necessarily a finite poset).

$(\Omega, \mathcal{M}, P)$ is a probability space.

$F$ is a mapping from $\Omega$ to $Y^X$. Then $F$ is a measurable mapping, wrt the $\sigma$-algebra on $Y^X$ induced from $\mathcal{M}$ on $\Omega$ by $F$ itself, i.e. it is a random function from $X$ to $Y$.

For any permutation $j$ on $X$, the notation $Foj$ represents the composition of each sample function of $F$ and $j$. Then $Foj$ is also a measurable mapping from $\Omega$ to $Y^X$, i.e. it is a random function from $X$ to $Y$.

For any mapping $a:Y^X \to X$, $a(F)$ is a measurable mapping from $\Omega$ to $X$, wrt the $\sigma$-algebra induced from $\mathcal{M}$ on $\Omega$ by $a$ itself.

Can the quoted no free lunch theorem be formulated equivalently in pure probability theoretical way as:

Random variables $a(F)$ and $b(F)$ have the same distribution for any two mappings $a$ and $b$ from $Y^X$ to $X$, if and only if $F$ and $F o j$ are identically distributed for all permutation $j$ on $X$?

As a pure probability theoretical statement, is the above claim true or false?

2. As a pure probability theoretical statement, do we need $Y$ to be a poset or just a set?
3. What if $X$ and $Y$ are not necessarily finite? In such a general case, does no free lunch theorem still hold?

Original questions (still questions, but the update contains more of my current understanding):

1. As a measurable mapping, what are the domain and codomain of the random variable $F$ so that $F o j$ can make sense? What is the underlying probability space? What does "a random variable is distributed on a set" mean in general?
2. How shall I understand $P(F o j = f) = P(F = f o j^{–1})$ for all $j \in J$ and $f \in Y^X$?

Since $\{ x \in X: F o j(x) = f(x)\} \equiv \{x \in X: F(x) = f o j^{–1}(x) \}$, isn't $P(F o j = f) = P(F = f o j^{–1})$ always true?

3. It seems like an algorithm $a$ is a mapping. What are its domain and codomain, so that $a(f)$ can make sense?
4. I heard an informal explanation of the NFL theorem that no algorithm can solve all problems well. So how is this corresponding to the formal statement of the theorem above?

Thanks and regards!

-

The "output" of deterministic search algorithm $a$ referred to in the Wikipedia article is a sequence in $Y^{|X|},$ not an element of $X.$ You're headed down a blind alley with your map $a:Y^X \rightarrow X.$
Olle Häggström ("Intelligent Design and the NFL Theorems") has observed that the "NFL condition" is exchangeability of the random values $F(x).$ The source on exchangeability that he cites may well provide a rigorous measure-theoretic treatment.