[19] Let P be a probability mass function and let A ⊆ N be computably enumerable. Define PA(x) = P(x|x ∈ A) and PA(x)=0



for x ∈ A, and let PA be computable and H(PA) finite. Show that x PA(x)C(x|A, PA) ≤ H(PA) +O(1), where the O(1) term is independent of P and A.

Comments. Hint: Let x1, x2,... be an enumeration of A by nonincreasing PA(xi

) probabilities. We can find this enumeration, since we can enumerate A until the first k elements constitute Ak and max{PA(x) :

x ∈ Ak} ≥ 1 − 

y∈Ak PA(y). The x that achieves the maximum is x1, and so on. Clearly, C(xi

|A, PA) ≤ log i + O(1). This yields 

x PA(x)

C(x|A, PA) ≤ 

i PA(xi

) log i + O(1) ≤ H(PA) + O(1) with the O(1)

term independent of P and A. (The last inequality follows from PA(xi



) ≤

1≤j≤i PA(xj )/i yielding log(iPA(xi

)) ≤ log 1 = 0. Therefore, log i ≤

log 1/PA(xi

).) Source: Adaption of an idea of B. List, personal communication, 1996.