EDIT: Some specific conjectures added.
This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen this before (the question is simple enough that I can't imagine it hasn't been studied).
Consider an $n$ by $n$ stochastic matrix $P = [p_{ij}]$ with stationary measure $\pi$. That is, the matrix $P$ satisfies:
$0 \leq p_{ij} \leq 1$.
$\sum_{j} p_{ij} = 1$ for all $1 \leq i \leq n$.
$\pi_{j} = \sum_{i} \pi_{i} p_{ij}$ for all $1 \leq j \leq n$
If helpful, I am happy to assume that the stochastic matrix is reversible, i.e. to replace the last equality above with the strictly stronger assumption
$\pi_{j} p_{ji} = \pi_{i} p_{ij}$ for all $1 \leq i,j \leq n$.
I then fix a small $0 < \epsilon \ll 1$. Let $\mu$ be a distribution (that is, a vector satisfying $\sum_{i} \mu_{i} = 1$, $\mu_{i} \geq 0$) that satisfies
$\mu \geq (1 - \epsilon) \mu P$.
I would like to conclude
$\mu_{i} \geq C \pi_{i}$
for some constant $0 < C < 1$. My basic question is: how big can I make $C$?
I'm interested in almost anything in this direction, and particularly interested in results that say `if $\epsilon$ is small relative to some reasonable graph statistics(e.g. that it is small compared to the spectral gap of $P$, or $n^{-1}$, or the conductance of $P$, etc), then $C$ is bigger than some absolute constant. I'm happy to allow almost any reasonable assumption about $P$ (e.g. that it is fairly sparse, that the associated graph has smallish degree, etc).
EDIT: In response to the comments, I give a precise conjecture. Assume reversibility of $P$ and that $p_{ii} \geq \frac{1}{2}$ for all $1 \leq i \leq n$. Write the eigenvalues of $P$ as $1 = \lambda_{1} > \lambda_{2} \geq \ldots \geq \lambda_{n} \geq 0$. Then
Conjecture: For $\epsilon < \frac{1 - \lambda_{2}}{10}$, we can choose $C > \frac{1}{10}$.
Of course, the 10's are arbitrary - I would be perfectly satisfied if they were replaced by any specific number. To relate this to mixing times, I note that this conjecture is (up to small universal constants) stronger than:
Conjecture: For $\epsilon < \frac{1}{10 \tau_{\mathrm{mix}}}$, we can choose $C > \frac{1}{10}$.
I have played around with various examples, and certainly it is the case that the best value of $C$ depends on the details of $P$ (not just on $n$, $\pi$ and $\epsilon$) and that it can sometimes be `quite small.' For example, if $p_{ij} \propto \textbf{1}_{|i-j| \leq 1}$, it is easy to check that we can have $\mu_{i} \approx (1-\epsilon)^{n}$, while $\pi_{i} \approx \frac{1}{n}$. In this example (and in all other examples I've worked out by hand), the constant $C$ can be made reasonably large once $\epsilon$ is on the order of the conductance of the chain (the conductance is given by $\Phi = \inf_{S \subset [n]} \frac{\sum_{i \in S, j \notin S} p_{ij}}{\sum_{i \in S} \pi_{i} \sum_{j \notin S} \pi_{j}}$). On the other hand, we clearly get something from this sort of inequality once $\epsilon$ is very small.
Thanks for any suggestions!
