Markov chain mixing time

In <a href="/facts/Probability_theory/mFBn51rE">probability theory</a>, the mixing time of a <a href="/facts/Markov_chain/5oP5hntk">Markov chain</a> is the time until the Markov chain is "close" to its <a href="/facts/Steady_state/qgrL4BNs">steady state</a> <a href="/facts/Probability_distribution/EpsKKVRu">distribution</a>.
More precisely, a fundamental result about <a href="/facts/Markov_chains/5oP5hntk">Markov chains</a> is that a finite state irreducible aperiodic chain has a unique stationary distribution π and, regardless of the initial state, the time-t distribution of the chain converges to π as t tends to infinity. Mixing time refers to any of several variant formalizations of the idea: how large must t be until the time-t distribution is approximately π? One variant, total variation distance mixing time, is defined as the smallest t such that the <a href="/facts/Total_variation_distance_of_probability_measures/agdAvDuW">total variation distance of probability measures</a> is small:

t
          
            mix
          
        
        (
        ε
        )
        =
        min
        
          {
          
            t
            ≥
            0
            :
            
              max
              
                x
                ∈
                S
              
            
            
              
                [
              
            
            
              max
              
                A
                ⊆
                S
              
            
            
              |
              
                Pr
                (
                
                  X
                  
                    t
                  
                
                ∈
                A
                ∣
                
                  X
                  
                    0
                  
                
                =
                x
                )
                −
                π
                (
                A
                )
              
              |
            
            
              
                ]
              
            
            ≤
            ε
          
          }
        
        .
      
    
    {\displaystyle t_{\operatorname {mix} }(\varepsilon )=\min \left\{t\geq 0:\max _{x\in S}{\Big [}\max _{A\subseteq S}\left|\Pr(X_{t}\in A\mid X_{0}=x)-\pi (A)\right|{\Big ]}\leq \varepsilon \right\}.}

Choosing a different 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
, as long as 
 
 
 
 ε
 <
 1
 
 /
 
 2
 
 
 {\displaystyle \varepsilon <1/2}
 
, can only change the mixing time up to a constant factor (depending on 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
) and so one often fixes 
 
 
 
 ε
 =
 1
 
 /
 
 4
 
 
 {\displaystyle \varepsilon =1/4}
 
 and simply writes 
 
 
 
 
 t
 
 
 m
 i
 x
 
 
 
 
 
 {\displaystyle t_{\mathrm {mix} }}
 
. 
This is the sense in which <a href="/facts/Dave_Bayer/qYyL7nIh">Dave Bayer</a> and <a href="/facts/Persi_Diaconis/AsI5mBLp">Persi Diaconis</a> (1992) proved that the number of riffle <a href="/facts/Shuffle/H8a3TynB">shuffles</a> needed to mix an ordinary 52 card deck is 7. Mathematical theory focuses on how mixing times change as a function of the size of the structure underlying the chain. For an 
 
 
 
 n
 
 
 {\displaystyle n}
 
-card deck, the number of riffle shuffles needed grows as 
 
 
 
 1.5
 
 log
 
 2
 
 
 ⁡
 n
 
 
 {\displaystyle 1.5\log _{2}n}
 
. The most developed theory concerns <a href="/facts/Randomized_algorithms/Fngl1zgk">randomized algorithms</a> for <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> algorithmic counting problems such as the number of <a href="/facts/Graph_coloring/J6HoBfP0">graph colorings</a> of a given 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertex graph. Such problems can, for sufficiently large number of colors, be answered using the <a href="/facts/Markov_chain_Monte_Carlo/eTjk3WQy">Markov chain Monte Carlo</a> method and showing that the mixing time grows only as 
 
 
 
 n
 log
 ⁡
 (
 n
 )
 
 
 {\displaystyle n\log(n)}
 
 (Jerrum 1995). This example and the shuffling example possess the rapid mixing property, that the mixing time grows at most polynomially fast in 
 
 
 
 log
 
 
 {\displaystyle \log }
 
(number of states of the chain). Tools for proving rapid mixing include arguments based on <a href="/facts/Conductance_(probability)/y29dPtPz">conductance</a> and the method of <a href="/facts/Coupling_(probability)/7Gp6yAqH">coupling</a>. In broader uses of the Markov chain <a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo method</a>, rigorous justification of simulation results would require a theoretical bound on mixing time, and many interesting practical cases have resisted such theoretical analysis.

Markov chain mixing time open-in-new

Markov chain mixing time