7
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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$
    – Penghui Yao
    Commented 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$
    – Anthony Quas
    Commented 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$
    – Anthony Quas
    Commented Dec 11, 2015 at 7:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .