# Transition probabilities for Gibbs Sampling in a Markov Random Field

I am currently reading this paper on Restricted Boltzmann Machines.

On page 22,

Given a Markov Random Field $$\mathbf{X} = (X_1,\ldots,X_N)$$ w.r.t a graph $$G = (V,E)$$ where $$V = \{1 \ldots N\}$$ and $$i \in V$$. The Gibbs sampling procedure is as follows:

At each transition step, pick random variable $$X_i$$, with a probability $$q(i)$$ given by strictly positive probability distribution $$q$$ on $$V$$.

Then, sample a new value of $$X_i$$ based on it's conditional probability distribution given the state $$(x_v)_{v \in V \setminus i}$$ of all other variables $$(X_v)_{v \in V \setminus i}$$ i.e. based on $$\pi(X_i \vert (x_v)_{v \in V \setminus i})$$.

Given the above steps, the paper states the transition probabilities $$p_{xy}$$ for two states $$\mathbf{x},\mathbf{y}$$ of the MRF $$\mathbf{X}$$ to be: I don't quite understand:

1) should $$p_{xx}$$ term have a product over all $$i \in V$$ as opposed to the sum?
2) why $$p_{xy}$$ does not have a sum over all $$i \in V$$.

1. The sum over vertices $i$ in $V$ follows from the Law of Total Probability. To find the probability $p_{\mathbf{xx}}$, we need to consider all the possible ways of transitioning to a state that is identical to the current one $\mathbf{x}$. Well, one such way is to pick node $1$ as the "update node" with probability $q(1)$ and then pick that node's current value $x_1$ according to $\pi$; or we could choose node $2$ with probability $q(2)$ and choose that node's current value $x_2$ from $\pi$; ... ; or we could choose node $N$ from $q$ and update to $x_N$ from $\pi$. The probability of transitioning to the same state as the current one is then the sum of the probabilities of each of these events, which is precisely what equation (17) is saying.
2. There is no analogous sum for $p_{\mathbf{xy}}$ because Gibbs sampling works by updating a single node at a time. So first of all realize that $\mathbf{y}$ is restricted to be a state that differs from $\mathbf{x}$ at a single node; this is what the "else 0" part of equation (16) is saying. Now suppose $\mathbf{y}$ is in fact such a state and it differs from $\mathbf{x}$ only at node $i$. Then the only way we can transition to this $\mathbf{y}$ is if we first select $i$ to be the update node, which happens with probability $q(i)$, and then draw the value $y_i$ from $\pi$.
• You're right that we should account for all ways to reach $\mathbf{y}$ from $\mathbf{x}$, but I'm saying is that there is only one such way for any particular $\mathbf{y}$. It sounds like your confusion is coming from the meaning of the notation $p_{\mathbf{xy}}$. Whereas $p_{\mathbf{xx}}$ is a single number, $p_{\mathbf{xy}}$ defines many different probabilities, one for each possible transition state $\mathbf{y}$. For example, if each random variable $X_i$ in the MRF can take on $m$ different values, then $p_{\mathbf{xy}}$ as given by equation (16) defines $m(N-1)$ probabilities. – tddevlin Jul 13 '17 at 14:13