No Free Lunch Theorem, explained.
No free lunch results show equal average search performance under specific uniform distributions over unrestricted objective functions; useful advantages depend on structure or assumptions.
Why it happens
Two non-repeating search orders inspect four binary locations until finding one or exhausting all four. Across all sixteen equally weighted objectives, mean probes are equal. Restricting to five nondecreasing objectives favours right-to-left search.
No free lunch results show equal average search performance under specific uniform distributions over unrestricted objective functions; useful advantages depend on structure or assumptions.
Read the result
The exact family averages matter more than one hidden objective. Uniformly averaging a different family changes the information available to exploit.
A worked example
Add structure to a four-location search
Probe an objective from the sixteen equally likely binary functions using one non-repeating order.
Compare the exact mean probe cost of one point eight seven five for both orders over that unrestricted family.
Restrict to nondecreasing objectives and compare left-to-right average two point eight with right-to-left one point six.
OPTIONAL DEEPER DETAILGo deeper: inside the model
Inside this model
Two non-repeating search orders inspect four binary locations until finding one or exhausting all four. Across all sixteen equally weighted objectives, mean probes are equal. Restricting to five nondecreasing objectives favours right-to-left search.
Where this idea is useful
A practical use
Match an algorithm to the structure of a workload instead of looking for a universal winner across unspecified tasks.
A common misconception
“No free lunch says algorithm design cannot improve anything.”
The result identifies assumptions under which advantages cancel. Practical tasks are structured, so choosing suitable assumptions can make design valuable.
What this explanation leaves out
- The equal-average claim depends on uniform weighting of the unrestricted finite objective family; it does not rank real learning or optimisation systems.
Why count four probes when no location contains one?
Exhausting the domain certifies failure and costs four queries. Counting only successful objectives would change the stated comparison.
What structure makes your chosen algorithm preferable on the tasks that actually occur?
Associated thinkers
Associations marked provisional are awaiting source review.
Further reading
Explore the original research or the teaching reference behind this experiment.