--- title: "Reply to 'Mathematical Inconsistency in Solomonoff Induction?'" date: 2020-09-04 parent: Posts layout: post published: true ---

This is a reply to this LessWrong post.

I went through the maths in OP and it seems to check out. I think the core inconsistency is that SI implies l(X ∪ Y) = l(X )  . I’m going to redo the maths below (breaking it down step-by-step more). curi has 2l(X ) = l(X)  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:

P(X ) =--1--
       2l(X )
(1)

what is the probability of X ∪ Y  ?

P (X  ∪Y ) = P (X )+ P (Y )− P(X ∩ Y )
           --1--  --1-   --1-- -1--
         = 2l(X ) + 2l(Y) − 2l(X) ⋅2l(Y)
           --1--  --1-   ----1-----
         = 2l(X ) + 2l(Y) − 2l(X) ⋅2l(Y )
           --1--  --1-   ----1----
         = 2l(X ) + 2l(Y) − 2l(X)+l(Y)
(2)

However, by Equation (1) we have:

              1
P(X ∪ Y) = -l(X∪Y-)
           2
(3)

thus

   1       1      1        1
2l(X∪Y-) = 2l(X-) + 2l(Y-) − 2l(X)+l(Y)
(4)

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)

---1---= --1--+ --1- − ---1-----
2l(X∪Y )  2l(X )  2l(Y)   2l(X)+l(Y)
       = --1--+ --1--− ----1----
         2l(X )  2l(X )  2l(X)+l(X )
       = --2--− --1--
         2l(X )  22l(X)
       = ---1---− --1--
         2l(X )−1   22l(X)
(5)

but

---1---   --1--
2l(X)− 1 ≫ 22l(X)
(6)

and

0 ≈ --1--
    22l(X)
(7)

so

   ---1---≃ ---1---
   2l(X∪Y )  2l(X )−1
∴ l(X ∪ Y ) ≃ l(X )− 1
         □
(8)

curi has slightly different logic and argues l(X ∪ Y) ≃ 2l(X )  which I think is reasonable. His argument means we get l(X ) ≃ 2l(X )  . 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(X ) ⁄= l(Y )  . Let’s assume the following:

  l(X) < l(Y )

∴ -1l(X)-≫ -l1(Y-)
  2      2
(9)

so, from Equation (2)

      P (X  ∪Y ) =--1--+ --1- − ----1----
                 2l(X )  2l(Y)   2l(X)+l(Y)
                             0        // 0
  lim  P (X  ∪Y ) =--1--+ --/1/ − ---/1/---
l(Y)→∞            2l(X )  /2l(Y)   /2/l(X)+l(Y)
    ∴ P (X  ∪Y ) ≃--1--
                 2l(X )
(10)

by Equation (3) and Equation (10)

      1       1
   2l(X-∪Y) ≃ 2l(X)
∴ l(X ∪Y ) ≃ l(X)

    ⇒ l(Y ) ≃ 0
(11)

but Equation (9) says l(X) < l(Y )  – this contradicts Equation (11). ■

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