Finding cohesive (low exit probability) sets in a Markov process

Question

The following is a fact about Markov chains that came up in a game theory paper. The purpose of this question is to ask if related notions or similar results are found elsewhere in probability, or are of interest to probabilists.

Fix a finite state space $S$. Let $K(\cdot,\cdot)$ denote the transition kernel of an ergodic, reversible Markov process on $S$, and $\pi$ the associated ergodic distribution. A set $E \subseteq S$ is called $p$-cohesive if, for every $x \in E$, we have $K(x,E)\geq p$: the probability of staying within $E$ conditional on being in it is at least $p$.

Proposition. Fix $p<1/2$ and $\delta >0$. There is an $\epsilon>0$ such that, for any kernel $K$ and set $E$ so that $\pi(E)\geq 1-\epsilon$, there is a $p$-cohesive $F \subseteq E$ with $\pi(F)\geq 1-\delta$. Thus, if in the long run the chain spends a lot of time in $E$, then there is some subset of $E$ in which it also spends a lot of time, and from which the exit probability is bounded.

This is tight in the sense that for any $p> 1/2$, there is an ergodic, reversible Markov chain with no proper, nonempty $p$-cohesive sets (e.g. symmetric random walk on the integers, reflected at two boundaries).

I would be very grateful for pointers on things to read to find connections in the probability literature.

Answer 1

In probabilistic approach to dynamical systems and related literature, what you call 'cohesive' sets are known as almost-invariant sets, coherent sets or meta-stable sets. Here, we are usually interested in partitioning the whole state space into few p-cohesive subsets for which $p\approx 1$, i.e. sets where exit probabilities are close to zero.

One of most popular way of doing such a partition is spectral partitioning, which involves thresholding the second eigenvector of the Markov matrix.

There exist some rigorous bounds on the best 'p' value you can obtain while subdividing into 2 or more subsets, and they depend on second eigenvalue of the Markov matrix.

References: 1). Detecting and locating near-optimal almost-invariant sets and cycles, Froyland and Dellnitz, SIAM journal on scientific computing 2003

2). Statistically optimal almost-invariant sets, G. Froyland, Physica D, 2005

3). Metastability and Dominant Eigenvalues of Transfer Operators, Wilhelm Huisinga, Bernd Schmidt Lecture Notes in Computational Science and Engineering Volume 49, 2006