IlyaShpitser comments on Rationality Quotes Thread September 2015 - Less Wrong

3 Post author: elharo 02 September 2015 09:25AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (482)

You are viewing a single comment's thread. Show more comments above.

Comment author: IlyaShpitser 10 October 2015 06:29:46PM *  0 points [-]

H(x) \proportional E[K(x)]

What does this mean? What is the expectation taken with respect to? I can construct an example where the above is false. Let x1 be the first n bits of Chaitin's omega, x2 be the (n+1)th, ..., 2nth bits of Chaitin's omega. Let X be a random variable which takes the value x1 with probability 0.5 and the value x2 with probability 0.5. Then E[K(X)] = 0.5 * O(n) + 0.5 * O(n) = O(n), but H(X) = 1.


edit: Oh, I see, this is a result on non-adversarial sample spaces, e.g. {0,1}^n, in Li and Vitanyi.

Comment author: [deleted] 12 October 2015 02:27:48AM 0 points [-]

edit: Oh, I see, this is a result on non-adversarial sample spaces, e.g. {0,1}^n, in Li and Vitanyi.

Yep. I should have gone and cited it, actually.