<p>Later in page 10 of the pdf he explains that in fact the probabilities are almost 1/2, as there is a very small probability to stop the at each step.</p>

<p>This stems from the following assumption: There is some mechanism that produces these strings, and it does so sequentially, therefore going through shorter strings on its way to longer ones and having a certain probability to stop at each step.</p>

<p>Another explanation that was more satisfying:</p>

<p>These binary strings are in fact prefixes of infinite random sequences. The probability of a prefix to be 1 or 0 is of course 1/2 etc'. The machine that reads these infinite binary strings is a prefix turing machine, which means that if it produces a certain sequence, it does so by reading a prefix of the random string.</p>

CC BY-SA 3.0
2014-11-27T04:35:58.857Z
2015-06-04T14:10:38.063Z
2015-06-04T14:10:38.063Z
Uri
<p>It is the consequence of the Occam's razor pinciple and maximum entropy principle, if we interpret Occam's razor as <strong>to minimize the expected codeword length of the model/program</strong>.</p>
<p>Then we can either miximize Shannon entropy with the constraint of finite expected codeword length, or minimize the expected codeword length with the constraint of finite Shannon entropy.</p>
<p><span class="math-container">$$\mathop{minimize}\limits_{w_h\vDash\left\{
{\begin{aligned}
&amp;H(w_h)=C_h\\
&amp;\sum\limits_{p:U(p)=h*}w_h^p=1
\end{aligned}}\right.} \sum\limits_{p:U(p)=h*}w_h^p\cdot \ell(p)\qquad\text{or}\qquad\mathop{maximize}\limits_{w_h\vDash\left\{
{\begin{aligned}
&amp;\sum\limits_{p:U(p)=h*}w_h^p\cdot \ell(p)=C_h\\
&amp;\sum\limits_{p:U(p)=h*}w_h^p=1
\end{aligned}}\right.} H(w_h)
$$</span></p>
<p>The Lagrange multiplier</p>
<p><span class="math-container">$$
L_h=\sum\limits_{p:U(p)=h*}w_h^p\cdot \ell(p)-T\left(-\sum\limits_{p:U(p)=h*}w_h^p\log w_h^p-C_h\right)-\lambda\left(\sum\limits_{p:U(p)=h*}w_h^p-1\right)
$$</span></p>
<p>Then we get</p>
<p><span class="math-container">$$\dfrac{\partial L_h}{\partial w_h^p}=0\implies w_h^p=\dfrac{2^{-\frac{\ell(p)}{T}}}{\sum\limits_{p:U(p)=h*}2^{-\frac{\ell(p)}{T}}}
$$</span></p>
<p>Which is the normalized Solomonoff prior with a 'temperature' parameter <span class="math-container">$T$</span>.</p>

CC BY-SA 4.0
2021-04-13T06:03:21.297Z
2021-04-13T06:03:21.297Z
Xi Li
<p>In this article, <a href="http://world.std.com/~rjs/rayfeb60.pdf" rel="nofollow">http://world.std.com/~rjs/rayfeb60.pdf</a> in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$.</p>

<p>My question - why are shorter strings considered more probable? Is there some kind of hidden assumption that justifies this?</p>

<p>e.g. that the machine which produces these strings have a constant probability to stop at a any given point (an inherent preference to shorter strings).</p>

<kolmogorov-complexity>
The concept of binary description by Ray Solomonoff
Uri
# The concept of binary description by Ray Solomonoff

(Asked by: username_0 on 2014-11-26)

In this article, <http://world.std.com/~rjs/rayfeb60.pdf> in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$.

My question - why are shorter strings considered more probable? Is there some kind of hidden assumption that justifies this?

e.g. that the machine which produces these strings have a constant probability to stop at a any given point (an inherent preference to shorter strings).

**Tags:** kolmogorov-complexity

---

## 2 answers

### Answer by username_0 on 2014-11-27. Score: 1 | Accepted answer

Later in page 10 of the pdf he explains that in fact the probabilities are almost 1/2, as there is a very small probability to stop the at each step.

This stems from the following assumption: There is some mechanism that produces these strings, and it does so sequentially, therefore going through shorter strings on its way to longer ones and having a certain probability to stop at each step.

Another explanation that was more satisfying:

These binary strings are in fact prefixes of infinite random sequences. The probability of a prefix to be 1 or 0 is of course 1/2 etc'. The machine that reads these infinite binary strings is a prefix turing machine, which means that if it produces a certain sequence, it does so by reading a prefix of the random string.


---

### Answer by username_1 on 2021-04-13. Score: 1

It is the consequence of the Occam's razor pinciple and maximum entropy principle, if we interpret Occam's razor as **to minimize the expected codeword length of the model/program**.

Then we can either miximize Shannon entropy with the constraint of finite expected codeword length, or minimize the expected codeword length with the constraint of finite Shannon entropy.

$$\mathop{minimize}\limits\_{w\_h\vDash\left\{
{\begin{aligned}
&H(w\_h)=C\_h\\
&\sum\limits\_{p:U(p)=h\*}w\_h^p=1
\end{aligned}}\right.} \sum\limits\_{p:U(p)=h\*}w\_h^p\cdot \ell(p)\qquad\text{or}\qquad\mathop{maximize}\limits\_{w\_h\vDash\left\{
{\begin{aligned}
&\sum\limits\_{p:U(p)=h\*}w\_h^p\cdot \ell(p)=C\_h\\
&\sum\limits\_{p:U(p)=h\*}w\_h^p=1
\end{aligned}}\right.} H(w\_h)
$$

The Lagrange multiplier

$$
L\_h=\sum\limits\_{p:U(p)=h\*}w\_h^p\cdot \ell(p)-T\left(-\sum\limits\_{p:U(p)=h\*}w\_h^p\log w\_h^p-C\_h\right)-\lambda\left(\sum\limits\_{p:U(p)=h\*}w\_h^p-1\right)
$$

Then we get

$$\dfrac{\partial L\_h}{\partial w\_h^p}=0\implies w\_h^p=\dfrac{2^{-\frac{\ell(p)}{T}}}{\sum\limits\_{p:U(p)=h\*}2^{-\frac{\ell(p)}{T}}}
$$

Which is the normalized Solomonoff prior with a 'temperature' parameter $T$.


---

