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.
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.
Yep. I should have gone and cited it, actually.