Second-Order Asymptotics in Fixed-Length Source Coding and Intrinsic Randomness

Abstract

There is a difference between the optimal rates of fixed-length source coding and intrinsic randomness when we care about the second-order asymptotics. We prove this difference for general information sources and then investigate independent and identically distributed (i.i.d.) random variables and Markovian variables as examples. The difference is demonstrated through an investigation of the second-order asymptotic behavior of the rates. A universal fixed-length source code attaining the second-order optimal rate is also proposed. The difference between the rates of fixed-length source coding and intrinsic randomness proves that the outputs of fixed-length source codes are not uniformly distributed.