Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models

We consider a high-dimensional mean estimation problem over a binary hidden Markov model, which illuminates the interplay between memory in data, sample size, dimension, and signal strength in statistical inference. In this model, an estimator observes n samples of a d-dimensional parameter vector θ*∈ℝd, multiplied by a random sign Si (1≤ i≤ n), and corrupted by isotropic standard Gaussian noise. The sequence of signs Sii∈[n]∈-1,1n is drawn from a stationary homogeneous Markov chain with flip probability δ∈[0,1/2]. As δ varies, this model smoothly interpolates two well-studied models: the Gaussian Location Model for which δ=0 and the Gaussian Mixture Model for which δ=1/2. Assuming that the estimator knows δ, we establish a nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of |θ*|,δ,d,n. We then provide an upper bound to the case of estimating δ, assuming a (possibly inaccurate) knowledge of θ*. The bound is proved to be tight when θ* is an accurately known constant. These results are then combined to an algorithm which estimates θ* with δ unknown a priori, and theoretical guarantees on its error are stated.