Two Lemmas on Prediction and Complexity

Introduction

In a previous article, I introduced a definition of a random variable that says, in simple terms, a source is random, and observing that source will in turn generate a random variable, if the source generates a sequence of observations that is eventually, approximately, Kolmogorov-random.

Note that my definition of a random variable is close enough to Per Martin-Löf’s, that it’s possible he, or someone else, already proved variations of these results –

I noticed these results in the context of my work on A.I. and physics, which are my primary areas of interest.

The Lemmas

For simplicity, let’s assume that observing the source generates truly Kolmogorov-random strings, since there is some nuance to the definition I offered in the previous article that adds only confusion, with no meaningful upside.

Recall that if a binary string $x$ is Kolmogorov-random, then the Kolmogorov complexity of $x$ , denoted $K(x)$ , which is the shortest input to a UTM, $y$ , that will generate $x$ , is such that the length of $y$ , denoted $|y|$ , is equal to $|x| + c$ , for some constant $c$ that does not depend upon $x$ . For example, if $c$ is the length of the “print” function, then because any string can be generated on a UTM by providing the string in question as an argument to the “print” function, it follows that for all strings $x$ , $K(x) \leq |x| + c$ .

Given a binary string $x$ , let $x_n$ denote the first $n$ entries of $x$ , and let $U(x)$ denote the output of a UTM when given $x$ as input.

Lemma 1. If a binary string $x_n$ is Kolmogorov-random, for all $n \in \mathbb{N}$ , then there is no computable function $f$ that can generate the next $n - k$ entries of $x$ , given the first $k$ entries of $x$ , for all $n,k \in \mathbb{N}$ .

Proof. Assume such a function $f$ exists. It follows that, given the first $k$ entries of $x$ , namely, $x_k =(x_1,x_2, \ldots, x_k)$ , we can generate the next $n - k$ entries $(x_{k+1}, \ldots, x_n)$ on a UTM, using $f$ , specifying $n$ . Because $x_n$ is Kolmogorov-random, and because we can specify any integer $m$ with at most $\log(m)$ bits, it follows that $K(x_n) \leq |f| + k + \log(n)$ , which implies that, $n - \log(n) \leq |f| - c + k$ . Note that the difference $|f| - c$ is constant, and because we can, for any fixed value of $k$ , choose an arbitrarily large value of $n$ , there is, therefore, no such function $f$ that exists for all $n,k \in \mathbb{N}$ , which completes the proof by contradiction.

Lemma 2. If a string $x_n$ is Kolmogorov-random, for all $n \in \mathbb{N}$ , and there is some computable function $f$ that can generate an unbounded number of entries of $x$ , then $f$ is subject to the inequality below.

Proof. Assume such a function $f$ exists. It follows that $f$ can generate some unbounded number of entries of $x$ , namely $S = \{x_{n_1}, x_{n_2}, \ldots, \}$ , where $n_i$ is the index of some entry within $x$ , each listed in order. Let $k \in \mathbb{N}$ . Because $f$ can generate an unbounded number of entries of $x$ , we can provide an argument $z$ , such that $U(f,z)$ will generate exactly $k$ entries of $x$ , in order. It follows that we can construct a substring of $x$ on a UTM, that contains $k$ entries of $x$ , in order, with any missing entries represented by some special character. Call the resultant string $s$ , and assume that $n = |s|$ . Note that $K(z) \leq \log(k)$ . This implies that $K(s) \leq |f| + \log(k)$ .

Note that we can generate $x_n$ given $s$ , the list of indexes that correspond to the missing entries within $s$ , and a string generated by concatenating the missing entries of $s$ that are within $x_n$ into a single string, $y$ . Because the maximum index of any entry within $y$ is $n$ , it follows that we can specify any such individual index with at most $\log(n)$ bits. Since there are $n - k$ entries in $y$ , it follows that we can specify all of the indexes within $y$ with at most $(n - k) \log(n)$ bits.

This implies that,

$K(x_n) \leq K(s) + K(y) + (n - k) \log(n) \leq [|f| + \log(k)] + (n - k) + (n - k) \log(n)$ .

This in turn implies that,

$n + c \leq |f| + \log(k) + (n - k) + (n - k) \log(n)$ ,

and so,

$c \leq |f| + \log(k) - k + (n - k) \log(n)$ .

If such a function $f$ exists, then this is a surprising result, since it implies that you can predict an unbounded number of non-sequential observations of a random variable, albeit subject to constraints. The question is, is there another reason why such a function cannot exist?

Discover more from Information Overload

Subscribe to get the latest posts sent to your email.

Discover more from Information Overload

Share this:

Related

Leave a comment Cancel reply