## Fast convergence for the random site Gibbs sampler

Hi guys, I'm Giulia from italy... I'm fighting against this problem since a long time and I wanna ask you to help me...

8.4 (10) Fast convergence for the random site Gibbs sampler. Consider (instead
of the systematic scan Gibbs sampler) the random site Gibbs sampler for random
q-colorings. Suppose that the graph G = (V, E) has k vertices,
and each vertex has at most d neighbors. Also suppose that q > 2d2.
(a) Show that for any given v _ V, the probability that v is chosen to be updated
at some step during the first k iterations of the Markov chain is at least 1-e-1.
(Here e _ 2.7183 is, of course, the base for the natural logarithm.)
(b) Suppose that we run two copies of this Gibbs sampler, one starting in a fixed
configuration, and one in equilibrium.
Show that the coupling can be carried out in such a way that for any v _ V and
any m, the probability that the two chains have different colors at the vertex v
at time mk is at most
(e^-1 + (1 – e^-1) 2d/q) (e^-1 + (1 – e^-1) 2d^2/q)^(m-1)

many greetings from rome