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

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.

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

• Thanks for this. I am familiar with spectral partitioning, but here the result is about finding large sets (under the invariant distribution of the whole chain) that contain large sets with bounded-above (not quite 'low') exit probability... And the kinds of techniques based on the spectral gap won't do the trick, as far as I can see. Jan 20 '14 at 19:21