# approximate stationary distributions of a doubly stochastic matrix and its supports

Given a doubly stochastic matrix $M$ and a distribution $v$,let $M=\sum_{\sigma\in S_n}p_{\sigma}M_{\sigma}$ be any Birkhoff decomposition of $M$, where $M_{\sigma}$ is the permutation matrix induced by $\sigma$ and $\{p_{\sigma}\}$ is a distribution. Suppose $v$ is an $\epsilon$-approximate stationary distribution of $M$, i.e., $$\|v-Mv\|_{TV}\leq\epsilon,$$ where $\|\cdot \|_{TV}$ is the total variance. Does it imply the following $$\sum_{\sigma}p_{\sigma}\|v-M_{\sigma} v\|_{TV}\leq \epsilon',$$ where $\epsilon'=f(\epsilon)$ only depends on $\epsilon$, and goes to 0 if $\epsilon$ goes to 0. In other words, is $v$ also an approximate stationary distribution of $M_{\sigma}$ in expectation? It is not hard to prove when $\epsilon=0$. I wonder whether this problem has been studied.

Thanks.

• Is it obvious what is meant by "the Birkhoff decomposition" in this question? Because the decomposition of a doubly stochastic matrix into permutation matrices is not necessarily unique. So is your question "for all decompositions ..." or "does there exist a decomposition such that ..."? – Joe Bebel Jan 7 '16 at 1:07
• Thanks for pointing it out. I have no solution to either case. @Joe Bebel – Penghui Yao Jan 8 '16 at 2:09

I think the answer is no: the rate at which $\epsilon'$ goes to 0 does depend on the size of the matrix. Here is my argument, which is not yet worked out in complete detail.
I want to consider a circle of large radius $R$ that is discretized with a very fine mesh. Imagine an approximation to a normal distribution with variance 1 centred at a point on the circle so that it decays almost to 0 before it wraps around. This is $\nu$. Now the matrix $M$ is convolution with another approximate normal distribution with variance $\eta^2$. A Birkhoff decomposition (in general, I don't think it's unique) is just the obvious one: $M$ is a combination of rotations by different amounts.
If you do this, I think $\|\nu-\nu M\|_\text{TV}\sim \eta^2$ while for typical $\sigma$, I think you have $\|\nu-\nu M_\sigma\|_\text{TV}\sim\eta$.
To actually do the calculation, I would prefer to work with true normal distributions on $\mathbb R$. If $X$ is distributed as $N(0,1)$ and $\Delta$ is distributed as $N(0,\eta^2)=\eta\cdot N(0,1)$, then $X+\Delta\sim N(0,1+\eta^2)$, so that $\|\nu_{X+\Delta}-\nu_{X}\|_\text{TV}\sim\eta^2$. On the other hand, $\|\nu_{X+t}-\nu_X\|_\text{TV}\sim t$, so that since the typical value of $\Delta$ is of order $\eta$, the expected order here is larger.
• Thanks. In your example, do you mean $\epsilon'=\sqrt{\epsilon}$? That is good for the purpose. Here being dimension-independent means that $\epsilon'=f(\epsilon)$, which only depends on $\epsilon$. @Anthony Quas – Penghui Yao Dec 9 '15 at 18:28
• I kind of agree, but it seems unlikely that you could ever obtain an $f(\epsilon)$ that was not of the form $C\cdot\epsilon$. I'll think about higher dimensional Gaussians later... – Anthony Quas Dec 10 '15 at 6:13