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

$\endgroup$
  • $\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 Apr 5 '19 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 Apr 6 '19 at 19:56
  • $\begingroup$ @Artemy Hello again Artemy! Thank you for the comments, I have updated the question. $\endgroup$ – litmus Apr 6 '19 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 Apr 7 '19 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 Apr 8 '19 at 14:49
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 Apr 8 '19 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 Apr 8 '19 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 Apr 8 '19 at 20:40

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.