Markov chains Reversibility(detailed balance) a transition probability distribution is reversible with respect to an initial distribution if, for the markov chain X1, X2, they specify, the distribution of pairs Xixi+1 is exchangeable P(Xi=x, Xn+1=y)=P(Xi=y, Xn+1=X,VXy E S Reversibility implies stationarity but not vice versa (marginalize w.r.t. y: P(Xi=x)=P(Xn+1=x),Vx E S Reversibility plays two roles in Markov chain theory elementary transition probability constructed by all known methods that preserve a specified equilibrium distribution are reversible reversibility makes the markov chain Clt much sharper and conditions much simpler. · Functionals Functional g: S-R.g(Xi, g(X2), is usually not a Markov chainMarkov Chains • Reversibility (detailed balance) – A transition probability distribution is reversible with respect to an initial distribution if, for the Markov chain 𝑋1 , 𝑋2 , ⋯ they specify, the distribution of pairs (𝑋𝑖 ,𝑋𝑖+1 ) is exchangeable 𝑃 𝑋𝑖 = 𝑥, 𝑋𝑛+1 = 𝑦 = 𝑃 𝑋𝑖 = 𝑦, 𝑋𝑛+1 = 𝑥 , ∀𝑥, 𝑦 ∈ 𝑆 – Reversibility implies stationarity, but not vice versa. (marginalize w.r.t. 𝑦: 𝑃 𝑋𝑖 = 𝑥 = 𝑃 𝑋𝑛+1 = 𝑥 , ∀𝑥 ∈ 𝑆) – Reversibility plays two roles in Markov chain theory: elementary transition probability constructed by all known methods that preserve a specified equilibrium distribution are reversible; reversibility makes the Markov chain CLT much sharper and conditions much simpler. • Functionals – Functional 𝑔: 𝑆 → ℝ. 𝑔 𝑋1 , 𝑔 𝑋2 , ⋯ is usually not a Markov chain