Problem 2

Consider the cycle graph C₁ with vertices V = {0,..., n-1}. Let = {1,-1}V

and define a function f : → R+ by

n-1

f(x) = II A²²+¹,

i=0

where >> 0 is fixed (if i = n − 1, ₁+1 refers to zo). Let Z = Eren f(x) and

T(x) = f(x)/Z a distribution on 2.

1/nConsider the following Markov chain on : Given a state r , select

i~ Unif(V) and set

x :=

with probability (1+X-2 (₁-1+₁+₁))~¹

with probability (1+²(²-1+²+₁)-¹

(note that these probabilities sum up to 1).

1. Prove that the Markov Chain is ergodic with stationary distribution 7.

Now assume that A = (3/2)¹/4 and therefore

(1+X-4)-¹ = 0.6 and (1+X4)-¹=0.4.

7

2. Let u be an arbitrary distribution on 2, and (X₂), (Y) be two runs of this

Markov Chain where Xo and Yo ~T. Find a coupling of (X), (Y)

such that for every t≥ 0 and d > 0,

E[Dt+1 - Dt | D₁ = d] ≤²

n

-0.2 - - .0.8.

-.d.

n

where D, denotes the number of vertices in which X differs from Y₁.

3. Use the previous item to bound the mixing time of the Markov Chain.