Let theta be max TV(x,y), where x and y range over the columns of A and TV(x,y) is 1/2 the L1 distance of the two vectors x and y. Theta is also called the (Doeblin) contraction coefficient of the Markov operator induced by A.

It's easy to see that lambda2 and theta are numbers between 0 and 1. Here is a simple example where lambda2=0 while theta=1:

0 0 0

0 1 1

1 0 0

It seems that we always have lambda2 <= theta, but I don't have a proof of this. I also can't imagine that I'm the first to observe this -- can someone point me to a reference? Maybe suggest a proof?

**Update**: thanks to David Aldous and Cristopher Moore for telling me how to prove this (well-known) fact. I won't elaborate, since nobody else seems to care, but if anyone does, let me know and I'll post a proof. I'd be thrilled to see an elementary proof (i.e., one not relying on Perron-Frobenius), so consider that a challenge!

## 3 comments:

Hey Leo, Could you post the proof? :)

I'm in thesis-writing crunch-mode (hoping to submit a draft today/tomorrow), so I'll be brief.

In fact, let me quote David Aldous himself:

"From any start, the variation distance between the time-t distribution and the stationary distribution is bounded by \theta^t for each t. But Perron-Frobenius theory shows that asymptotically the variation distance goes as constant \lambda_2^t.

In the Aldous-Fill draft book, this is the ``\tau_2 \leq \tau_1"

inequality."

(That book draft may be found here.)

That proves the claim for Markov chains having a stationary distribution, but I'm numerically observing that the claim seems to hold true for

allcolumn-stochastic matrices -- and I don't currently have a proof of this!Update -- after consulting Pierre Bremaud's book (and some helpful correspondence with Pierre) I see that the claim indeed holds for all stochastic matrices. If you get a hold of the book, look at Thm. 7.2 and the remark on p. 238 about how Dobrushin's (Doeblin's) coefficient upper-bounds SLEM.

I will do a more detailed post on this, or maybe even write up a brief expository note.

Post a Comment