2
$\begingroup$

Consider a discrete state space $\mathcal{X}$. The expander Chernoff inequality gives subgaussian concentration for the sample mean $\frac1n \sum_{t=1}^n f(X_t)$ for some function $f : \mathcal{X} \to [0,1]$, where $X_t$ follows a discrete time stationary Markov chain. The variance parameter of the subgaussian concentration itself is proportional to the spectral gap of the chain. A small spectral gap would be implied by bottlenecks in the Markov chain (Cheeger's inequality) which would in turn make convergence slow.

Would I be right to think that the existence of bottlenecks would only be problematic if the chain is stationary? By this I mean: assume that the Markov chain is always started from a fixed state $X$, and compare $\frac1n \sum_{t=1}^n f(X_t)$ with its expectation, $\frac1n \mathbb{E}_{\substack{X_1 = X,\\ X_{i+1} \sim P(\cdot | X_i)}} \left[\sum_{t=1}^n f(X_i) \right]$. Can one expect subgaussian concentration with a variance parameter that does not depend on the spectral gap of the chain?

In the extreme case, where the Markov chain has two disjoint components, the stationary chain will never converge, since it may never reach the vertices in the other component. However, when started in a fixed state, the 2nd disjoint component can be thrown away since it appears neither in the observed sample paths, nor in the expectations.

$\endgroup$

1 Answer 1

4
$\begingroup$

Your ``extreme case'' is not a good indication of what happens in a slightly less extreme case. If the chain has a narrow bottleneck between two strongly connected components, for some time it will stay on one side of the bottleneck and you will see the sample mean approach the average of $f$ over this side; but at some random time the chain will cross and the sample mean will move away toward the average of $f$ over the other side. The sample mean should navigate between the two side averages, with only a very slow convergence to the overall average - the behavior will be pretty much the same as for the simplest such case, with two states $a,b$, a probability to stay in one state of $1-\epsilon$ and a probability to switch state of $\epsilon$. Now, the expectation assuming a fixed starting point $x_0$ will (slowly) converge to the overall average, but will not exhibit these oscillations since it averages over all possible switch times. Therefore, whenever the chain gets stuck long enough on one side, you will see a significant gap with the expectation. Such events will occur from time to time, and you cannot expect a strong concentration.

You might be able to get good concentration for a (random) large subset of times, though.

Also note that when your $f$ is specified, you can in some cases improve the spectral gap by choosing appropriately the norm you use on your function space.

$\endgroup$

You must log in to answer this question.

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