[14]

(a) Let U be the reference prefix machine of Theorem 3.1.1 on page 206. Define P(x) = 

U(p)=x 2−l(p)

. Show that 

x P(x) ≤ 1, so P(x) qualifies as a probability mass function over the integers. (We use the term ‘probability mass function’ loosely here for nonnegative real-valued functions summing to at most 1.)

(b) Define P(x)=2−K(x)
. Show that 
x P(x) ≤ 1, the sum taken over all x, so P(x) qualifies as a probability mass function over the integers.

(c) Define P(x|y)=2−K(x|y)
. Show that 
x P(x|y) ≤ 1, for each fixed y, so P(x|y) qualifies as a conditional probability mass function over the integers.

(d) Define P(x)=2−K(x|l(x)). Show that 
x P(x) = ∞, so P(x) does not qualify as a probability mass function.
Comments. Hint for Item (a): use the Kraft inequality, Theorem 1.11.1.
Hint for Item (d): use K(x|l(x) ≤ l(x) + O(1).