I'm going to walk through some logic that I believe I've heard somewhere before...but I can't remember where and I am interested in citing it. Does anyone know where I could cite this type of thinking and its conclusion?

Also, I am interested in whether this line of reasoning is correct, or if there are some holes in it.

I am studying a deterministic process and I want to build a mathematical model for how it works, both for inference and for prediction. The process has the following inputs and outputs.

Input: $p$ binary predictors and I know that nothing outside these $p$ predictors influences the outcome. I'll imagine $p \approx 100$ to create the right flavor of problem.

Output: 1 binary outcome

So, if I observed all $2^p$ possible inputs and their resultant outputs (assuming no measurement error), there would be nothing to do - I would know everything there is to know about this process.

But, I can't really observe all the possible inputs when $p$ is more than about 5 or 6 and I'm interested in situations where $p$ is around 100. So, let's imagine a slightly more realistic situation (but only slightly!).

Imagine I observed "only" $2^p - 1$ inputs and their resultant outputs. How would I predict the output for the final possible input?

It seems there must be at least two possible rules -- one that, if it were true, would give a 0 for the last set of input and one that, if it were true, would give a 1 for the last set of input. And there's no way to choose between them without seeing the last input!

I can only choose between the two (or maybe there are more?) rules based on a priori beliefs about which rules are reasonable/likely/good/useful and which are not.

Though this setup seems fanciful, I would argue it's the easiest possible situation in which a model could be fit.

  1. The outcome was binary, and any continuous response could be simplified with binarization.
  2. There are no unknown inputs. I could ignore some of them to return to the situation where most statistical modeling efforts exist -- some inputs are unknown and their effects are sopped up into the residual error term or similar.
  3. The inputs are binary. Any continuous valued input could be binarized without losing information by turning it into a set of "greater than this cutoff?" "greater than that cutoff?" binary values.

1 Answer 1


This idea is essentially the "no free lunch" theorem: if you make no assumptions, then anything is possible, and predicting anything is impossible. As a corollary, no predictive algorithm is uniformly better than another algorithm across all datasets.

There are many posts about the theorem on this site; there's also the website no-free-lunch.org. The standard citation there seems to be:

Wolpert (1996). The Lack of A Priori Distinctions Between Learning Algorithms. Neural Computation 8 (7), 1341-1390. (doi) (Google scholar)

But, of course, predictive inference is not a hopeless task. We just need to make assumptions that we think are reasonably likely to be true; this is the idea of inductive bias.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.