On the $\alpha$-lazy version of Markov chains in estimation and testing problems

Estimating the parameters of a discrete distribution and distinguishing whether an unknown distribution is identical to a reference one or is $\varepsilon$-far from it under some notion of distance, assuming access to iid samples, are two classical and well studied problems in statistics and computer science (e.g. Han et al. (2015), Kamath et al. (2015), Orlitsky and Suresh (2015), Batu et al. (2001), Valiant and Valiant (2017) and the references therein). In contrast, research on the analogue problems assuming the samples are obtained from a single long trajectory generated by an unknown Markov chain is rather young. This work is concerned with the latter and adds to the still rather short list of works on the subject: Wolfer and Kontorovich (2019, 2020, 2021), Cherapanamjeri and Bartlett (2019), Daskalakis et al. (2018), Chan et al. (2021), Fried and Wolfer (2021) and Hao et al. (2018). We shall review the results of these works in the Related literature section.

Before we rigorously present our main results, let us somewhat informally sketch their motivation: In Wolfer and Kontorovich (2021, Theorem 3.1) an estimator for the transition matrix $M$ of an unknown ergodic Markov chain was constructed, based on a single long trajectory generated by the Markov chain. In addition, they upper bounded the sample complexity of obtaining an estimation whose distance from $M$ under the infinity norm is less than a prescribed $\varepsilon\in(0,1)$ with high probability. The assumption that the unknown Markov chain is ergodic is crucial in their sample complexity analysis since it relies on concentration bounds (cf. Paulin (2015)) which assume ergodicity. We have noticed that it is possible to generalize their results to irreducible but possibly periodic Markov chains in the following way: Let $M$ be an irreducible Markov chain on $d$ states from which we can sample a single long trajectory of arbitrary length. Recall that if $\alpha\in(0,1)$ and $I$ denotes the identity matrix of size $d$, then $\mathcal{L}_{\alpha}(M)=\alpha I+(1-\alpha)M$ is called the $\alpha$-lazy version of $M$. It is well known that the $\alpha$-lazy version of an irreducible Markov chain is ergodic. Crucially, it is possible to simulate $\mathcal{L}_{\alpha}(M)$ even when one only has access (as is the case here) to a black box that generates a single long trajectory from $M$ (cf. (6) of Section 2.2). This simulation results in a trajectory sampled from the ergodic Markov chain $\mathcal{L}_{\alpha}(M)$ on which we may apply the estimator mentioned above. Finally, we pull back the estimation of $\mathcal{L}_{\alpha}(M)$ to an estimation of $M$.

Several questions immediately arise from this procedure:

1. (a)

   Can it be done with other estimation problems or even other statistical inference problems, e.g. identity testing?

2. (b)

   The $\alpha$-lazy version of a Markov chain is a special case of a matrix transformation. Can the procedure be done with other transformations?

3. (c)

   An upper bound for the sample complexity of the original (ergodic) estimation problem involves (the inverse of) the pseudo spectral gap $\gamma_{\text{ps}}(M)$ of an ergodic Markov chain $M$. It follows that the sample complexity in the irreducible case is upper bounded by $\gamma_{\text{ps}}(\mathcal{L}_{\alpha}(M))$ for $M$ an irreducible Markov chain. Since $\gamma_{\text{ps}}(M)=0$ for an irreducible but periodic Markov chain $M$, no meaningful comparison between $\gamma_{\text{ps}}(M)$ and $\gamma_{\text{ps}}(\mathcal{L}_{\alpha}(M))$ is possible. Instead, we ask the following question: Suppose $M$ is ergodic. How are $\gamma_{\text{ps}}(M)$ and $\gamma_{\text{ps}}(\mathcal{L}_{\alpha}(M))$ related? An answer to this question quantifies the “price” one has to pay for not being sure whether an unknown irreducible Markov chain is periodic or not.

Our first two main results address the questions in (a) and (b) that are related to Markov chains estimation problems, by which we mean a tuple $(\Theta,\rho,\mathcal{M}^{\circ})$ where $\Theta$ is a set, $\rho\colon\Theta\times\Theta\to\mathbb{R}_{+}$ is a distance function, i.e., for $x,y\in\Theta$ it holds: $\rho(x,y)=0$ if and only if $x=y$ (Notice that we neither assume that $\rho$ is symmetric nor that it satisfies the triangle inequality. Thus, in addition to metrics such as the total variation or the Hellinger distance, our machinery is applicable to, for example, the Kullback–Leibler divergence). The set $\mathcal{M}^{\circ}$ is a subset of the set of all transition matrices of irreducible Markov chains on $d$ states which we denote by $\mathcal{M}_{d}^{\textnormal{irr}}$. The set $\Theta$ consists of the values that the parameter to be estimated can take and is accompanied by a map $\theta\colon\mathcal{M}_{d}^{\textnormal{irr}}\to\Theta$. The distance function $\rho$ is used to measure the distance between the true value of the parameter and its estimation. Following the works mentioned above, in the setting we consider we have access to a single long trajectory generated from an unknown Markov chain $M$, started from an arbitrary state, and the purpose is to construct an estimator for some parameter of interest $\theta(M)$ such that the distance between the estimation and the true value of the parameter is less than a prescribed $\varepsilon\in(0,1)$. Along with the estimator we would like to know in advance how long the trajectory must be for the estimation to succeed. The minimal necessary trajectory length is referred to as the sample complexity. Since the estimation relies on a random trajectory, there is generally some probability that the trajectory obtained is not informative. Thus, in addition to $\varepsilon$, the sample complexity depends also on $\delta\in(0,1)$ such that the estimator is guaranteed to succeed with probability at least $1-\delta$.

The following theorem provides a sufficient condition for the feasibility of the procedure we described above. It uses the notions of a solution to an estimation problem and of extendibility of their solutions which will be defined in Section 3.1:

Let us demonstrate a typical usage of Theorem 1.1 by applying it on the problem of estimating the transition matrix mentioned above: We have

For $\mathcal{M}^{\circ}$ we take $\mathcal{M}_{\pi_{\star},\gamma_{\text{ps}}}$ which is defined as the set of all ergodic Markov chains on $d$ states whose minimum stationary probability and pseudo spectral gap are lower bounded by $\pi_{\star},\gamma_{\text{ps}}\in(0,1)$, respectively. The set $\mathcal{M}_{\pi_{\star},\gamma_{\text{ps}}}$ is the default choice in this work since the sample complexity of the problems that we consider was shown to be upper bounded by expressions that involve $\frac{1}{\gamma_{\text{ps}}}$ and $\frac{1}{\pi_{\star}}$. Taking $\varphi=\mathcal{L}_{\alpha}$ and $\ell(\varepsilon)=(1-\alpha)\varepsilon$ for every $\varepsilon\in(0,1)$, a natural candidate for $g$ is $\mathcal{L}_{\alpha}^{-1}$ but it may well result in a matrix that is not irreducible. Even worse, we might end up with negative entries on the main diagonal, i.e., not a row-stochastic matrix. In order to guarantee an estimation which is an irreducible Makrov chain, $\mathcal{L}_{\alpha}^{-1}$ is followed by a projection on the set of all row-stochastic matrices of size $d$ which we denote by $\mathcal{M}_{d}$, which, in turn, is followed by an additional adjustment to guarantee irreducibility. We discuss this example in detail in Example 3.2(b).

Our second main result shows that there are cases in which extending solutions is hard:

In Example 3.4 we shall show that the assumptions of Theorem 1.2 are satisfied in the setting of Wolfer and Kontorovich (2019, Theorem 8.1) who constructed an estimator for the pseudo spectral gap (in absolute error).

Our third main result is a reformulation of Theorem 1.1 to Markov chains identity testing problems. In this setting one needs to decide, based on a single long trajectory generated from an unknown Markov chain, whether a certain parameter of the Markov chain equals a specific value or is $\varepsilon$-far from it under some notion of distance for $\varepsilon\in(0,1)$. We will apply the theorem on the Markov chains identity testing problem considered by Wolfer and Kontorovich (2020, Theorem 4.1) in which the parameter of interest is the transition matrix. The formal definition of Markov chains identity testing problems and of extendibility of their solutions is given in Section 3.2.

Our last main result addresses the question in (c), namely, the connection between $\gamma_{\text{ps}}(M)$ and $\gamma_{\text{ps}}(\mathcal{L}_{\alpha}(M))$ for an ergodic Markov chain $M$. Recall that the pseudo spectral gap captures the mixing time (cf. (5)) and that there exists a universal constant $c$ such that

(Lemma 4.5). We conjecture (Conjecture 4.6) that a similar inequality holds for the pseudo spectral gap. As a consequence of the following theorem we show that for an ergodic Markov chain $M$ such that $\gamma_{\text{ps}}(M)$ is obtained at $k=1$ (cf. (4)) it holds

This confirms the conjecture for this class of ergodic Markov chains that contains all ergodic and reversible Markov chains.

In the following theorem $\gamma(M)$ denotes the spectral gap of a reversible Markov chain $M$ and $M^{\dagger}$ denotes the multiplicative reversibilization of an irreducible Markov chain $M$:

The paper is structured as follows: After a short literature review, in Section 2 we recall definitions and well known facts regarding Markov chains and their $\alpha$-lazy versions that will be used throughout this work. Our main reference here is Levin and Peres (2017); In section 3, that contains our main results, we formulate the framework and demonstrate its usage; Section 4 is devoted to the sample complexity aspect of moving to an $\alpha$-lazy version.

Definition 3.1, together with its analogue - Definition 3.5 - provide the basis for this work. The reader might find it useful to keep the following story in mind while reading them: Suppose we are interested in a certain parameter of irreducible Markov chains, e.g. their minimum stationary probability. Let $\Theta$ denote the set of all values that this parameter may take, e.g. $(0,1/2]$. Denote by $\theta(M)$ the value that the parameter takes for $M\in\mathcal{M}_{d}^{\textnormal{irr}}$. Let $\hat{\theta}$ be an estimator that upon receiving a trajectory from an unknown $M\in\mathcal{M}_{d}^{\textnormal{irr}}$, outputs an estimation $\hat{\theta}(M)$ of $\theta(M)$ whose “quality” is measured by a distance function $\rho$. Suppose we know that for some class $\mathcal{M}^{\circ}\subseteq\mathcal{M}_{d}^{\textnormal{irr}}$ the estimator needs not more than $m_{0}\in\mathbb{N}$ samples in order to output a “good” estimate with “high” probability. Now, suppose we want to use this estimator for Markov chains not belonging to $\mathcal{M}^{\circ}$. If there is a map $\varphi$ into $\mathcal{M}^{\circ}$, the following recipe might work: Given $M\in\mathcal{M}_{d}^{\textnormal{irr}}$, apply $\hat{\theta}$ on $\varphi(M)\in\mathcal{M}^{\circ}$ and then pull back the estimation $\hat{\theta}(\varphi(M))$ to an estimation of $\theta(M)$.