Abstract
In order to generate a universal probability distribution to extrapolate a binary string
x of length
i, we feed random bits into a universal device,
M. When we find an input string that gives an output matching
x, we continue the successful input with random bits until
M produces a zero or one as output. The relative probabilities of these two continuations can give a normalized prediction for the probability of the symbol following
x. There is, however, a probability,
P
i
+
1
(
u
)
that the continued random input string will not generate any output for the
(
i
+
1
)
th symbol.
We will show
E
μ
∑
i
=
1
n
P
i
(
u
)
⩽
k
μ
ln
2
. Here
E
μ
is the expected value with respect to
μ, the probability distribution that created
x.
k
μ
is the Kolmogorov complexity of
μ with respect to
M.
n is any positive integer. Usually we do not know
μ and so we do not know
k
μ
. However, if
μ is the uniform distribution, we can usually find a good upper bound for
k
μ
.