3
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ It might help to reformulate your desired conclusion in terms of a mixing time. $\endgroup$ Nov 25, 2014 at 22:33
  • $\begingroup$ Nice question but it is totally unclear where what you want to know differs from what you do know and what exactly you are trying to get. It would be much better (for me, at least), if there was some clearly posed yes/no type problem (with understanding that if the answer is "yes", you get all you need, and if it is "no", then the ball goes back to your court and you think of how to save the question to keep it useful for your purposes or decide that the game is over). $\endgroup$
    – fedja
    Nov 26, 2014 at 2:05
  • $\begingroup$ Dear Steve, fedja: Thank you for the thought and the comments. I added one precise (though perhaps overly optimistic) conjecture, and related it to mixing times. As I say, I am also interested in partial results, but I understand that it is a little unfair to ask for partial results without saying what they are part of! Thanks again. $\endgroup$
    – M.Burtke
    Nov 26, 2014 at 5:02
  • $\begingroup$ (PS: In case it makes a difference, I explain the reason for the vagueness of the initial question. I used such a bound for a very nice, symmetric collection of matrices in the middle of a calculation in a recent paper, and was able to do everything by hand. I now have a bunch of examples where I'd like to do `the same' calculation, and this is the one step where I seem to be using the symmetry of the initial calculation in a way that I don't understand.) $\endgroup$
    – M.Burtke
    Nov 26, 2014 at 5:23

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.