If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing machine (UTM) $U$. Say $m_U$ is the normalized prior with respect to a UTM $U$. Is there a $U$ such that $m_U$ has maximum entropy?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
All versions of Solomonoff's prior have infinite entropy. We supply a proof. Let $m: \mathbb{Z}_+ \to [0,1]$ be Solomonoff's prior, where inputs are encoded as integers. Then there is $c>0$ such that $$m(n) \geq c\frac{1}{n (\log n)^2},$$ Let $S$ be the set of all $n$ such that $$m(n) \geq \frac{1}{n}.$$ Since $\sum m(n)$ is convergent, $$\sum_{s \in S} \frac{1}{s} \leq \sum_n m(n) < \infty.$$
The entropy of $m$ is $$ \begin{align*} \sum_n m(n) \log(1/m(n)) &\geq \sum_n c\frac{1}{n (\log n)^2} \log(1/m(n)) \\ &\geq \sum_{n \not\in S} c\frac{1}{n (\log n)^2} \log(1/m(n)) \\ &\geq \sum_{n \not\in S} c\frac{1}{n \log n}. \end{align*} $$
Now $$ \infty = \sum_{n} c\frac{1}{n \log n} = \sum_{n \in S} c\frac{1}{n \log n} + \sum_{n \not\in S} c\frac{1}{n \log n}, $$ and $$\sum_{s \in S} \frac{1}{s \log s} \leq \sum_{s \in S} \frac{1}{s} < \infty,$$ so $$ \sum_{n \not\in S} c\frac{1}{n (\log n)} = \infty. $$