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.


  • $\begingroup$ 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 ..."? $\endgroup$
    – Joe Bebel
    Jan 7, 2016 at 1:07
  • $\begingroup$ Thanks for pointing it out. I have no solution to either case. @Joe Bebel $\endgroup$ Jan 8, 2016 at 2:09

1 Answer 1


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.

  • $\begingroup$ 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 $\endgroup$ Dec 9, 2015 at 18:28
  • $\begingroup$ 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... $\endgroup$ Dec 10, 2015 at 6:13
  • $\begingroup$ So I did a rough calculation for a higher-dimensional Gaussian, and got the same scaling. I'd still be quite surprised if that's universal. $\endgroup$ Dec 11, 2015 at 7:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.