|
|
Article: 3 Advanced functional techniques.(Mathematical Aspects of Mixing Times in Markov Chains)
- Article from:
- Foundations and Trends in Theoretical Computer Science
- Article date:
- May 1, 2006
- Author:
CopyrightCOPYRIGHT 2006 Now Publishers, Inc. This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
The relation between functional constants and mixing time bounds was studied in Section 2. In this section it is shown that information on functions of large variance, or on functions with small support, can be exploited to show better mixing time bounds.
The argument is simple. Recall that d/dt Var([h.sub.t]) = -2E([h.sub.t], [h.sub.t]). If E(f, f) [greater than or equal to] G(Var(f)) for some G : [R.sub.+] [right arrow] [R.sub.+] and f : [OMEGA] [right arrow] [R.sub.+] with Ef = 1, then it follows that d/dt Var([h.sub.t]) = -2E([h.sub.t], [h.sub.t]) [less than or equal to] -2G(Var([h.sub.t])). With a change of variables to I = Var([h.sub.t]), this becomes dI/dt ...