3
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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