The Dispersion of the Gauss-Markov Source

The Gauss-Markov source produces U_i = aU_(i–1) + Z_i for i ≥ 1, where U_0 = 0, |a| 0, and we show that the dispersion has a reverse waterfilling representation. This is the first finite blocklength result for lossy compression of sources with memory. We prove that the finite blocklength rate-distortion function R(n; d; ε) approaches the rate-distortion function R(d) as R(n; d; ε) = R(d)+ √ V(d)/n Q–1(ε)+o(1√n), where V (d) is the dispersion, ε ε 2 (0; 1) is the excess-distortion probability, and Q^(-1) is the inverse Q-function. We give a reverse waterfilling integral representation for the dispersion V (d), which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all 0 < d ≥ σ^2 (1+|σ|)^2, R(n; d; ε) of the Gauss-Markov source coincides with that of Z_i, the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of n samples of the Gauss-Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter a based on n observations