Max Kaye comments on Mathematical Inconsistency in Solomonoff Induction?

[Max Kaye]

I went through the maths in OP and it seems to check out. I think the core inconsistency is that Solomonoff Induction implies $l(X\cup Y)=l\left(X\right)$ which is obviously wrong. I’m going to redo the maths below (breaking it down step-by-step more). curi has $2l\left(X\right)=l\left(X\right)$ which is the same inconsistency given his substitution. I’m not sure we can make that substitution but I also don’t think we need to.

Let $X$ and $Y$ be independent hypotheses for Solomonoff induction.

According to the prior, the non-normalized probability of $X$ (and similarly for $Y$) is: (1)

$$P\left(X\right)=\frac{1}{2^{l\left(X\right)}}$$

what is the probability of $X\cup Y$? (2)

$$\begin{array}{cc}P(X\cup Y)& =P\left(X\right)+P\left(Y\right)-P(X\cap Y)\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)}}\cdot \frac{1}{2^{l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)}\cdot 2^{l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\end{array}$$

However, by Equation (1) we have: (3)

$$P(X\cup Y)=\frac{1}{2^{l(X\cup Y)}}$$

thus (4)

$$\frac{1}{2^{l(X\cup Y)}}=\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}$$

This must hold for any and all $X$ and $Y$.

curi considers the case where $X$ and $Y$ are the same length, starting with Equation (4), we get (5):

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(X\right)}}-\frac{1}{2^{l\left(X\right)+l\left(X\right)}}\\ & =\frac{2}{2^{l\left(X\right)}}-\frac{1}{2^{2l\left(X\right)}}\\ & =\frac{1}{2^{l\left(X\right)-1}}-\frac{1}{2^{2l\left(X\right)}}\end{array}$$

but (6)

$$\frac{1}{2^{l\left(X\right)-1}}\gg \frac{1}{2^{2l\left(X\right)}}$$

and (7)

$$0\approx \frac{1}{2^{2l\left(X\right)}}$$

so: (8)

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& \simeq \frac{1}{2^{l\left(X\right)-1}}\\ \therefore l(X\cup Y)& \simeq l\left(X\right)-1\\ & \square \end{array}$$

curi has slightly different logic and argues $l(X\cup Y)\simeq 2l\left(X\right)$ which I think is reasonable. His argument means we get $l\left(X\right)\simeq 2l\left(X\right)$. I don’t think those steps are necessary but they are worth mentioning as a difference. I think Equation (8) is enough.

I was curious about what happens when $l\left(X\right)\ne l\left(Y\right)$. Let’s assume the following: (9)

$$\begin{array}{cc}l\left(X\right)& <l\left(Y\right)\\ \therefore \frac{1}{2^{l\left(X\right)}}& \gg \frac{1}{2^{l\left(Y\right)}}\end{array}$$

so, from Equation (2): (10)

$$\begin{array}{cc}P(X\cup Y)& =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\\ \underset{l\left(Y\right)\to \infty }{lim}P(X\cup Y)& =\frac{1}{2^{l\left(X\right)}}+{\frac{1}{2^{l\left(Y\right)}}}^0-{\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}}^0\\ \therefore P(X\cup Y)& \simeq \frac{1}{2^{l\left(X\right)}}\end{array}$$

by Equation (3) and Equation (10): (11)

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& \simeq \frac{1}{2^{l\left(X\right)}}\\ \therefore l(X\cup Y)& \simeq l\left(X\right)\\ \Rightarrow l\left(Y\right)& \simeq 0\end{array}$$

but Equation (9) says $l\left(X\right)<l\left(Y\right)$ --- this contradicts Equation (11).

So there’s an inconsistency regardless of whether $l\left(X\right)=l\left(Y\right)$ or not.