The Kolmogorov complexity, universal distribution, and coding theorem for generalized length functions
K. Kobayashi · IEEE Transactions on Information Theory · 1997
A function h(w) is said to be useful for the coding theorem if the coding theorem remains to be true when the lengths |w| of codewords w in it are replaced with h(w). For a codeword w=a/sub 0/a/sub 1/...a/sub m-1/ of length m and an infinite sequence Q=(q/sub 0/, q/sub 1/, q/sub 2/, ...) of real numbers such that 0<q/sub n//spl les/ 1/2 , let |w|/sub Q/ denote the value /spl Sigma//sub n=0//sup m-1/ (if a/sub n/=0 then -log/sub 2/q/sub n/, else -log/sub 2/(1-q/sub n/)), that is, -log/sub 2/, (the probability that flippings of coins generate x) assuming that the (i+1)th coin generates a tail (or 0) with probability q/sub i/. It is known that if 0