1
$\begingroup$

Consider some finite string $x=(x_1,x_2,...,x_{n-1},x_n)$ that is drawn from a non-stationary process. Would it be possible to use the algorithmic probability formula, defined by Solomonoff as, $$ P_M(x)=\sum_{i=1}^{\infty}2^{-|s_{i}(x)|} $$ to predict $x_n$, by computing the probability $$P_M(x_n | x_1,...x_{n-1})=P_M(x_1,x_2,...,x_{n-1},x_n)/P_M(x_1,x_2,...,x_{n-1})$$? Or is it a necessity that the process that $x$ is drawn from be stationary?

Edit: Here $s_i(x)$ refers to the $i$-th program which generated $x=(x_1,x_2,...,x_{n-1})$ and we want to predict the probability that $x_n$ is either a $1$ or a $0$.

Improve this question
$\endgroup$
6
  • $\begingroup$ Interesting, but I'm a bit confused. I mean, I can use any probability to predict anything. So are you asking whether it's a good idea or not? That depends where $x$ comes from. But this feels philosophical ... also, it's not computable, so in that sense, I think "no, not possible". $\endgroup$
    – usul
    Commented Apr 5, 2019 at 12:52
  • 1
    $\begingroup$ @litmus I think your question shows some confusions. First, I believe you are using $s_i(x)$ to refer to the $i$-th program which generates $x$, which should be explained. Second, it is not $s_i(x)$ that has a universal distribution, rather the "universal distribution" is $P_M$ itself, as defined above. Lastly, it is not clear what you mean by a "non-stationary binary string". Usually a random process (i.e., a distribution over infinite strings) is said to be is stationary or not stationary, not a particular finite string. $\endgroup$
    – Artemy
    Commented Apr 6, 2019 at 19:56
  • $\begingroup$ @Artemy Hello again Artemy! Thank you for the comments, I have updated the question. $\endgroup$
    – litmus
    Commented Apr 6, 2019 at 20:19
  • 1
    $\begingroup$ That helps but I might still not be entirely understanding your question. The equation you have states exactly how to compute (or, more specifically, lower semicompute) $P_M(x)$ for any finite string $x$. Are you asking whether it is allowed for $x$ to be sampled from some non-stationary random process, say with distribution $Q$? If so, then yes -- the above probability measure is defined for any finite string whatsoever. $\endgroup$
    – Artemy
    Commented Apr 7, 2019 at 0:06
  • $\begingroup$ @Artemy Yes, that is exactly what I wanted to know, thanks! If you want to elaborate your comment as an answer instead, I'd be very happy to accept it. Also, please feel free to edit my question if you think that there are some parts that could be more clear for posterity. $\endgroup$
    – litmus
    Commented Apr 8, 2019 at 14:49

1 Answer 1

Reset to default
1
+50
$\begingroup$

The equation you have for algorithmic probability states how to compute (or, more specifically, lower semicompute) $P_M(x)$ for any finite string $x$, so it can also be used to predict $x_n$ by evaluating $P_M(x_n \vert x_1, \dots , x_{n-1})$. It holds for any finite string $x$ -- it does not matter what distribution (if any) $x$ is drawn from.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks so much for your help @Artemy! Are there any papers (or books) you would recommend that introduces / teaches the basics of algorithmic probability? And also any papers/books on Turing machines or anything else you think is necessary to grasp the fundamentals? $\endgroup$
    – litmus
    Commented Apr 8, 2019 at 19:29
  • 1
    $\begingroup$ @litmus, Li and Vitanyi's An Introduction to Kolmogorov Complexity and its Applications, as well as Chaitin's Algorithmic Information Theory are good books to read on this topic. $\endgroup$
    – kodlu
    Commented Apr 8, 2019 at 20:06
  • 1
    $\begingroup$ In addition to the recommendations by @kodlu, which I would second, Marcus Hutter's work is very good. A good place to start might be his "non-technical" introduction, arxiv.org/pdf/cs/0703024.pdf . $\endgroup$
    – Artemy
    Commented Apr 8, 2019 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .