Compute transition probabilities for reversible dynamics wrt Gibbs measure

Question

I'm looking at this paper about Gibbs measure on random graph. I don't understand how to compute transition probabilities for the first example (known as Glauber or Metropolis dynamics, pag 4-5) for checking the reversibility wrt the defined Gibbs measure.

Given $n$, each of n individuals takes one of two opinions $X_i(0) \in \{+1, −1\}$ independently and uniformly at random for $i \in [n] = \{1,... ,n\}$. At each subsequent time $t$, one individual $i$, chosen uniformly at random, computes the opinion imbalance: $M ≡ \sum_{j=1}^{n} X_j$ and $M^{(i)} ≡ M − X_i$. Then, he/she changes his/her opinion with probability:

$P_{flip}(X) = \exp(−2β \tfrac{|M^{(i)}|}{n}) \quad$ if $M^{(i)}X_i > 0 $ and $1$ otherwise.

This dynamics (aperiodic irreducible Markov chain) is reversible wrt to the stationary measure:

$\mu(x)=\tfrac{1}{Z}\exp \{\tfrac{\beta}{n}\ \sum_{(i,j)} x_ix_j$}

which means that $\mu(x) P(x\rightarrow x') = \mu(x') P(x' \rightarrow x)$, for any configuration $x$ and $x'$. How can I compute the one-step transition probability $P(x\rightarrow x')$? Is it immediate?

Answer 1

In this model it is easiest to describe $P(x \to x')$ through three cases:

1. More than one person changes their opinion. This has probability zero.
2. Exactly one person changes their opinion. This has probability equal to the probability that that person is chosen $(1/n)$ times the probability that they would actually change their opinion if they were chosen (which you stated in your question).
3. No one changes their opinion. This has probability $1$ minus the sum of all of the probabilities in #2.

Case 1 winds up being trivial to check reversibility, you get 0=0. Case 3 is also trivial to check reversibility, because $x=x'$ so that you just have $\mu(x)P(x \to x)=\mu(x)P(x \to x)$. The nontrivial part is case 2, where it is crucial that the acceptance probability is chosen "just right" to match the stationary distribution.