I recently came across the theorem on large deviations for finite Markov chains, which I have some trouble using it. In order to state the theorem we need the following notations first: Let $\Sigma$ be some finite alphabet, $\pi$ an irreducible transition matrix, $\sigma$ an initial state and let $Y_1,...,Y_n,...$ be the Markov chains defined by $\pi$.

Given some function $f:\Sigma\to\mathbb{R}^d$ we set $Z_n=\frac{1}{n}\sum_1^n f(Y_i)$, and for $\lambda\in \mathbb{R}^d$ we define the matrix $\pi_\lambda (i,j)=\pi(i,j)e^{<\lambda,f(j)>}$ and set $\rho(\pi_\lambda)$ to be its Perron-Frobenius eigenvalue.

Now that we have all the definitions, the theorem states that for any $\Gamma \subseteq \mathbb{R}^d$ we have that $$\limsup_{n \to \infty}\frac{1}{n} \log P_\sigma ^\pi (Z_n \in \Gamma)\leq - \inf_{z\in \bar\Gamma} I(z)$$ where $$I(z)=\sup_{\lambda \in \mathbb{R}^d} \{ <\lambda,z>-\log \rho(\pi_\lambda)\}$$

The main goal of course is to show that for suitable choice of $\Gamma$ the expression $\inf_{z\in \bar\Gamma} I(z)$ will be positive and then we get an exponential bound on the probability. Unfortunately, I have no idea how this function looks like, except that it is nonnegative.

In the i.i.d case there is a similar bound which uses the relative entropy to measure how far away $\Gamma$ is from the right limit (namely the expectation of f). What I would like to know is if a similar phenomenon happens here also and if so how to show it. Specifically, I'm interested in $f$ which is a characteristic function of some subset of $\Sigma$.

  • $\begingroup$ Can you define $\rho$? (I suspect I know what you mean, but it would still be good to have it written.) $\endgroup$ – Ian Nov 11 '16 at 0:26
  • $\begingroup$ Also, one would expect that for suitably "generic" $f$ and $\Gamma$ bounded away from the mean of $f$ under the equilibrium distribution, $P_\sigma^\pi(Z_n \in \Gamma)$ should behave like $\lambda_2^n$ where $\lambda_2$ is the second eigenvalue of the transition probability matrix (which is necessarily less than $1$ because the chain is irreducible). Are you specifically interested in cases where $f$ is such that you get a better bound? $\endgroup$ – Ian Nov 11 '16 at 0:31
  • $\begingroup$ An example: you can look at the transition matrix $\begin{bmatrix} 1/2 & 1/2 & 0 \\ 0.01 & 0.98 & 0.01 \\ 0 & 0.0001 & 0.9999 \end{bmatrix}$. In this chain the state $2$ is "metastable": although the equilibrium distribution has state $3$ occupied about 100 times more often than state $2$, probability nevertheless "flows" from $2$ to $3$ via the effect of an eigenvector whose eigenvalue is about $0.99$, which is relatively slow. This makes convergence to the equilibrium distribution quite slow if the initial distribution is concentrated on $\{ 1,2 \}$. $\endgroup$ – Ian Nov 11 '16 at 0:40
  • $\begingroup$ Anton Bovier has richly developed this metastability theory in his writings, some of which can be found free online. $\endgroup$ – Ian Nov 11 '16 at 0:41
  • $\begingroup$ @ian (1) $\rho$ is the Perron-Frobenius eigenvalue which is the the real eigenvalue which equals the spectral radius. (2) Regarding the spectral gap, I thought that it should somehow come into play there, but the question is how. It helps finding how fast you converge to the invariant distribution, but I'm not sure how to use it when computing these averages. (3) Once this matrix is fixed, it might take a long time to get near the invariant distribution, but it will be finite, which doesn't really matter for n big enough. (4) I will try to check Bovier's work to see if it can help me. $\endgroup$ – Ofir Nov 11 '16 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.