Induction

Let the world of sense data available to an observer be an infinite sequence of bits. At time 0 the observer wishes to verify or refute a hypothesis about the sequence. The hypothesis is a prediction of the entire string from time 0 on. The question of induction is whether the observer can, by verifying that the pattern holds until a certain time n, make it more likely that the pattern holds beyond time n, and possibly holds for ever, without making any a-priori assumptions whatsoever about the sequence.

Clearly, if n is any fixed number then the answer is negative. For any n, and any hypothesis, there is a sequence (actually, an infinite number of sequences) for which the hypothesis holds for bits 1 through n, and fails on bit n + 1. Thus, the observer is led to adopt the hypothesis only to have it fail immediately upon adoption.

If, however, the observer can generate random bits, then some induction is possible. In this case the observer can generate a random number n which is distributed over the natural numbers and which has a probability p_k of being equal to k. If the sequence fits the hypothesis to bit m, then the observer will only adopt the hypothesis in the case n < m and, if so, will make at least one successful inductive prediction unless n = m – 1. Thus, the probability of making an immediate error is p_m. Given the distribution, p_k, k = 1, 2, …, the highest chance for immediate failure occurs when pm maximizes p_k over k = 1, 2, …. Thus, the minimax strategy for the probability of immediate failure is to minimize the maximum p_k. Under the constraint that the expected value for n should be no more than a certain value, b, the minimax strategy for the observer is to sample n uniformly over the range 1, 2, …, 2b. The probability of adoption and immediate failure in this case is no more than 1 / 2b, regardless of what the sequence is.

Similarly, the chance of hypothesis adoption and failure within d predictions is d / 2b. Being able to predict with any confidence that a certain hypothesis will hold forever is clearly impossible no matter how many trials one is allowed to make before adopting the hypothesis.

Similar analysis holds, mutatis mutandis, if the sense-data is assumed to be a observed continuously in time. Observing the hypothesis holding for a certain random period of time enables the observer to predict with some confidence that the hypothesis would continue to hold for some comparable length of time beyond that observation period.

Advertisement