  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
$\theta_{*}\in\mathbb{R}^{d}$, multiplied by a random sign $ S_i $ ($1\le i\le
n$), and corrupted by isotropic standard Gaussian noise. The sequence of signs
$\{S_{i}\}_{i\in[n]}\in\{-1,1\}^{n}$ is drawn from a stationary homogeneous
Markov chain with flip probability $\delta\in[0,1/2]$. As $\delta$ varies, this
model smoothly interpolates two well-studied models: the Gaussian Location
Model for which $\delta=0$ and the Gaussian Mixture Model for which
$\delta=1/2$. Assuming that the estimator knows $\delta$, we establish a nearly
minimax optimal (up to logarithmic factors) estimation error rate, as a
function of $\|\theta_{*}\|,\delta,d,n$. We then provide an upper bound to the
case of estimating $\delta$, assuming a (possibly inaccurate) knowledge of
$\theta_{*}$. The bound is proved to be tight when $\theta_{*}$ is an
accurately known constant. These results are then combined to an algorithm
which estimates $\theta_{*}$ with $\delta$ unknown a priori, and theoretical
guarantees on its error are stated.
