Let A be a column-stochastic matrix. Compute its (complex) eigenvalues, take absolute values, sort in decreasing order, and let lambda2 be the second value on the list (the first is always 1, by Perron's theorem). Lambda2 is (closely related to) the spectral gap of the Markov kernel corresponding to A.
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!
Subscribe to:
Post Comments (Atom)
4 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 all column-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.
Great detailed information, I’ll be visiting you more frequently, here is very interesting information.
Taft-Hartley Benefit Fund Software
Post a Comment