Download Mathematical Aspects of Mixing Times in Markov Chains by Ravi Montenegro, Prasad Tetali PDF

By Ravi Montenegro, Prasad Tetali

Offers an creation to the analytical elements of the speculation of finite Markov chain blending instances and explains its advancements. This e-book seems at a number of theorems and derives them in basic methods, illustrated with examples. It comprises spectral, logarithmic Sobolev recommendations, the evolving set method, and problems with nonreversibility.

Show description

Read Online or Download Mathematical Aspects of Mixing Times in Markov Chains (Foundations and Trends in Theoretical Computer Science) PDF

Best stochastic modeling books

Mathematical aspects of mixing times in Markov chains

Offers an advent to the analytical points of the idea of finite Markov chain blending occasions and explains its advancements. This booklet seems at a number of theorems and derives them in easy methods, illustrated with examples. It contains spectral, logarithmic Sobolev options, the evolving set technique, and problems with nonreversibility.

Stochastic Processes in Physics Chemistry and Biology

The speculation of stochastic strategies presents a major arsenal of tools appropriate for interpreting the impression of noise on quite a lot of structures. Noise-induced, noise-supported or noise-enhanced results occasionally supply an evidence for as but open difficulties (information transmission within the frightened method and data processing within the mind, approaches on the mobilephone point, enzymatic reactions, and so on.

Stochastic Integration Theory

This graduate point textual content covers the speculation of stochastic integration, a massive zone of arithmetic that has a variety of functions, together with monetary arithmetic and sign processing. aimed toward graduate scholars in arithmetic, statistics, chance, mathematical finance, and economics, the e-book not just covers the speculation of the stochastic necessary in nice intensity but in addition offers the linked idea (martingales, Levy techniques) and demanding examples (Brownian movement, Poisson process).

Lyapunov Functionals and Stability of Stochastic Difference Equations

Hereditary structures (or platforms with both hold up or after-effects) are customary to version techniques in physics, mechanics, regulate, economics and biology. a big point of their research is their balance. balance stipulations for distinction equations with hold up could be got utilizing Lyapunov functionals.

Extra info for Mathematical Aspects of Mixing Times in Markov Chains (Foundations and Trends in Theoretical Computer Science)

Example text

It was established at the beginning of this section that spectral gap and the log-Sobolev constant cannot be used to establish a sharp mixing time bound for a walk on the cycle Z/mZ. Instead we use the spectral profile. 1) it can be used to lower bound spectral profile. Given r ∈ [0, 1] the conductance profile is minp+q p+q ≥ 2mr . imized at the set A = {0, 1, . . , rm − 1}, with Φ(A) = mπ(A) Then Λ(r) ≥ p+q Φ2 (r) ≥ . 2. 10. We now show a matching lower bound. Let xk denote the direction of the kth step, so x ∈ {−1, 0, +1}.

11. If Z ≥ 0 is a nonnegative random variable and g is a nonnegative increasing function, then E (Z g(Z)) ≥ EZ g(EZ/2) . 2 Proof. (from [61]) Let A be the event {Z ≥ EZ/2}. Then E(Z 1Ac ) ≤ EZ/2, so E(Z1A ) ≥ EZ/2. Therefore, E (Z g(2Z)) ≥ E (Z1A g(EZ)) ≥ Let U = 2Z to get the result. EZ g(EZ). 2 284 Evolving Set Methods It is fairly easy to translate these to mixing time bounds. 6 it is appropriate to let f (z) = 1−z z for L bounds. 5) τ2 ( ) ≤ 2x(1 − x)(1 − C√z(1−z) (x))  π∗       1   1+ 2 /4 dx     4π∗ x(1 − x)(1 − C√ (x)) z(1−z) 1+3π∗ 1 with the first integral requiring x 1 − C√z(1−z) 1+x to be convex.

2. 6 this distance decreases at a rate of Cz log(1/z) each step, as is the case with e−ρ0 in continuous time. 5) will be used to give an alternate approach to the spectral profile bounds. 6), ˆ n f (π(Sn )) ≤ } to be an upper bound on and define τ ( ) = min{n : E the mixing time of our distance. 7. profile is Given a function f : [0, 1] → R+ the f -congestion Cf (r) = max Cf (A) where π(A)≤r 1 Cf (A) = 0 f (π(Au )) du . f (π(A)) The f -congestion is Cf = maxA⊂Ω Cf (A). 8. ˆ n+1 f (π(Sn+1 )) − E ˆ n f (π(Sn )) = −E ˆ n f (π(Sn )) (1 − Czf (z) (Sn )) E ˆ n f (π(Sn )) ≤ −(1 − Czf (z) ) E Proof.

Download PDF sample

Mathematical Aspects of Mixing Times in Markov Chains (Foundations and Trends in Theoretical Computer Science) by Ravi Montenegro, Prasad Tetali


by Richard
4.1

Rated 4.69 of 5 – based on 35 votes