[32] Suppose we want to obtain information about a certain object x. It is not a good policy to guess blindly. The mutual information of two objects x and y was given in Example 3.8.2 on page 253 as I(x; y) = K(y) − K(y|x, K(x)). Show that 

y m(y)2I (x;y) = O(1).

Comments. In words, the expected value of 2I (x;y) is small, even with respect to the universal distribution m(x). Hint: by the coding theorem, Theorem 4.3.3, we have 2I (x;y) = 2−K(y|x,K(x))/m(x) + O(1). Source:

[P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 2008].