This paper provides a precise error analysis for the maximum likelihood estimate â_(ML)(u1n) of the parameter a given samples u1n= (u1, ..., u_n)idrawn from a nonstationary Gauss-Markov process U_i = aU_(i-1) + Z)_i, i ≥ 1, where U0= 0, a > 1, and Ziis are independent Gaussian random variables with zero mean and variance σ2. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula that we derived previously for the asymptotically stationary Gauss-Markov sources, i.e., |a|<;1. New ideas in the nonstationary case include separately bounding the maximum eigenvalue (which scales exponentially) and the other eigenvalues (which are bounded by constants that depend only on a) of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound.

This paper provides a precise error analysis for the maximum likelihood estimate â(u) of the parameter a given samples u = (u1, ... , un)T drawn from a nonstationary Gauss-Markov process Ui= αUi-1+ Zi, i ≥ 1, where α > 1, U0= 0, and Zz's are independent Gaussian random variables with zero mean and variance σ2. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula derived in our previous work [1] for the (asymptotically) stationary GaussMarkov sources, i.e., |α|<; 1. New ideas in the nonstationary case include a deeper understanding of the scaling of the maximum eigenvalue of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound.

The Gauss-Markov source produces Ui= aUi-1+ Zifor i≥1, where U0= 0, |a|i~N (0,σ2) are i.i.d. Gaussian random variables. We consider lossy compression of a block of n samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion d>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 ℝ(d)+√(V(d)/n) Q-1(ϵ)+0(1/√n),where V(d) is the dispersion,ϵ ∈ (0, 1) is the excess-distortion probability, and Q-1is 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 02/(1+|a|2, R(n,d,ϵ) of the Gauss-Markov source coincides with that of Zi, 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 observation.

The Gauss-Markov source produces Ui=aUi-1+ Zi for i ≥ 1, where and Zi ~ N(0, σ2) are i.i.d. Gaussian random variables. We consider lossy compression of a block of n samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion d > 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, ε ∈ (0,1) is the excess-distortion probability, and Q-1is the inverse of the 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 02,R(n, d, c)of the Gauss-Markov source coincides with that of Zi, 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.

We consider the problem of communication over a network containing a hidden and malicious adversary that can control a subset of network resources, and aims to disrupt communications. We focus on omniscient node-based adversary, i.e., the adversary can control a subset of nodes, and knows the message, network code and packets on all links. Characterizing information-theoretically optimal communication rates as a function of network parameters and bounds on the adversarially controlled network is in general open, even for unicast (single source, single destination) problems. In this work we characterize the information-theoretically optimal randomized capacity of such problems, i.e., under the assumption that the source node shares (an asymptotically negligible amount of) independent common randomness with each network node a priori. We propose a novel computationally-efficient communication scheme whose rate matches a natural information-theoretically “erasure outer bound” on the optimal rate. Our schemes require no prior knowledge of network topology, and can be implemented in a distributed manner as an overlay on top of classical distributed linear network coding.