0
$\begingroup$

My current research (on Probabilistic Automaton) brought me to the following question regarding Markov Chains. I state the definitions for the sake of clarity.

Let $M$ be a discrete-time finite Markov Chain over the set of states $Q = \{1,\ldots,n\}$ with transition matrix $P \in \mathbb{R}^{n \times n}$. I'll define $p_{i,j}(n) = (P^n)_{i,j}$ as the probability that the walk is at state $j$ after $n$ steps, when starting from state $i$. I understand that if $M$ is irreducible then there is an unique stationary distribution $\pi \in \mathbb{R}^n$ such that $P \pi = \pi$, and if $M$ is also aperiodic it holds that, for any $i \in Q$,

$$ \lim_{n \to \infty} p_{i,j}(n) = \pi(j) $$

If $M$ is not aperiodic, we still have convergence of the Ceraso sum as

$$ \lim_{n \to \infty} \frac{\sum_{k=1}^n p_{i,j}(k)}{n} = \pi(j) $$

I'm interested in understanding how fast is this convergence. After some research I came accross the notion of mixing time, which essentially measures how fast any distribution turns into the stationary one. According to Wikipedia, the mixing time is defined as

$$ t_{min}(\varepsilon) = \min \left\{ t\geq 0 : \max_{q \in Q} \left[ \max_{A \subseteq Q} \left| P(X_t \in A | X_0 = q) - \sum_{a \in A} \pi(a) \right| < \varepsilon \right] \right\} $$

Finding a bound for this parameter $t_{min}(\varepsilon)$ allows to control the probabilities $p_{i,j}(t)$ for any $i$ after enough steps $t$. Nevertheless, I'm working on a slightly different thing, which I do not know if it is equivalent of not.

Given a sequence of states $q_1 \ldots q_k$ I define the probability of this path as $P(q_1 \ldots q_k) = \prod_{i=0}^{k-1} P(X_{i+1} = q_{i+1} | X_{i} = q_i$) (where from now on I fix some initial position $q_0$ as $P(X_0 = q_0) = 1$). Given any path $q_1\ldots q_k$ one can compute the number of times that the path visits the state $j$ as $ocurr(q_1\ldots q_k, j) = |\{q_i = j : 1 \leq i \leq k\}|$, and it holds that if $M$ is irreducible with stationary distribution $\pi$ then

$$ \mu\left\{ q_1 q_2 \ldots \in Q^\mathbb{N} : \lim_{k \to \infty} \frac{ocurr(q_1 \ldots q_k, j)}{k} = \pi(j) \right\} = 1 $$

where the measure $\mu$ is the natural one induced by the probabilities over the prefixes of the paths (i.e. for any $q_1 \ldots q_k \in Q^k$ it holds that $\mu(\{q_1' \ldots \in Q^\mathbb{N} : q_i' = q_i \text{ for } 1\leq i \leq k\}) = P(q_1\ldots q_k)$). This last equation tells us that all paths (but a zero measure set) "converge" to the stationary distribution in terms of the Cesaro sum. Nonetheless, I need a more fine grained result of this kind. More precisely, given some $b \in \mathbb{N}$ and a precission $\varepsilon$: how likely is that a path of length $b$ behaves like the stationary distribution, in terms of the Cesaro sum? More formally, I want a good lower bound in terms of $b$ and $\varepsilon$ of

$$ P\left(\{q_1 \ldots q_b \in Q^b : \left|\frac{ocurr(q_1 \ldots q_b, j)}{b} - \pi(j)\right| < \varepsilon \, \,\,\forall j\in Q\right) $$

So, my questions are: Is there a known result similar to what I'm asking? Can this bound be inferred using the mixing time of the Markov Chain? What are some good references to look for answers to these questions?

I've entered into this world in the last months, so any advice will help :)

$\endgroup$

1 Answer 1

1
$\begingroup$

Indeed, there exist well-established results that provide quantitative bounds on the probability that the empirical distribution of states along a finite path deviates from the stationary distribution. Specifically, concentration inequalities for Markov chains, such as the Azuma-Hoeffding inequality adapted to the Markovian setting, can be utilized to bound this probability.

For a finite, irreducible, and aperiodic Markov chain with stationary distribution $\pi$, the empirical frequency of visiting state $j$ after $b$ steps is given by $\dfrac{\text{occurr}(q_1 \ldots q_b, j)}{b}$. Under certain conditions, the following concentration inequality holds for any $\varepsilon > 0$:

$$ \mathbb{P}\left( \left| \dfrac{\text{occurr}(q_1 \ldots q_b, j)}{b} - \pi(j) \right| \geq \varepsilon \right) \leq 2 \exp\left( - \dfrac{2 \varepsilon^2 b}{\tau_{\text{rel}}} \right), $$

where $\tau_{\text{rel}}$ denotes the relaxation time of the Markov chain, which is inversely proportional to the spectral gap and related to the mixing time $t_{\text{mix}}(\varepsilon)$. The spectral gap is defined as $1 - \lambda_2$, with $\lambda_2$ being the second-largest eigenvalue (in absolute value) of the transition matrix $P$.

This inequality indicates that the probability of the empirical frequency deviating from the stationary distribution by at least $\varepsilon$ decreases exponentially with the length of the path $b$, scaled by the relaxation time. To derive such inequalities, one often employs martingale techniques and leverages the Markov chain's mixing properties. The Azuma-Hoeffding inequality for martingales is adapted to account for the dependencies inherent in Markov chains by considering the Doob martingale associated with the chain.

Moreover, the mixing time $t_{\text{mix}}(\varepsilon)$ plays a crucial role in quantifying how quickly the Markov chain converges to equilibrium. It is intimately connected to these concentration bounds, as a faster mixing time implies tighter concentration around the stationary distribution.

Therefore, the mixing time can indeed be used to assess how rapidly the empirical frequencies converge to the stationary distribution in a probabilistic sense. For a comprehensive treatment of these concentration inequalities and their proofs, I recommend consulting Markov Chains and Mixing Times by Levin, Peres, and Wilmer. Additionally, the paper Concentration Inequalities for Markov Chains by Chatterjee and Varadhan provides an in-depth analysis of concentration results specific to Markov processes.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .