Comparing Gibbs sampler and variational inference I am learning about variational inference and Gibbs simpler.
I am in the process of deriving variational inference on my own. In this process, I need to make a comparison with Gibbs sampler.
I am reading the book "Machine learning a probabilistic perspective" by Kevin Murphy and I found this sentence that I need help with

"Since we are replacing the neighboring values by their mean value,
the method is known as mean field. This is very similar to Gibbs
sampling (Section 24.2), except instead of sending sampled values
between neighboring nodes, we send mean values between nodes."

Someone please explain how Gibbs sampling sends sampled values between neighbors and VI sends mean values between nodes.
I am looking for an in-depth explanation that shows what is what and how it is meant by this comparison.
 A: Gibbs sampling
I don't know the mean field method, but I work with Gibbs sampler, so let me explain it.
Definitions
Given a set of labels $L$ and an undirected graph $G = (V, E)$ with a non-empty set of vertices $V$ and a set of edges $E \subset V^2$, let us introduce a probability space $(\Omega, \mathcal{F}, P)$ and a random vector $\xi \colon \Omega \rightarrow L^V$. This means that the realisation of $\xi$ is a mapping $\xi(\omega)\colon V \rightarrow L$, called labelling. Let us denote the labelling $\xi(\omega)$ having a value $\ell \in L$ for the argument $v \in V$ a $\xi_v = \ell$.
This random variable should have the Markov property
$$
P(\xi_v = \ell | \xi_{v'}, \forall v' \in V \setminus \{v\})
= P(\xi_v = \ell | \xi_{v'}, \forall v': (v, v') \in E),
\quad \forall v \in V, \forall \ell \in L,
$$
and these probabilities must be known for applying Gibbs sampling.
In other words, the probability of a label $\ell$ in a vertex $v$ is entirely defined by the labels of the neighbours of the vertex $v$ in graph $G$.
Gibbs sampling
Gibbs sampling can work in the following way:

*

*Assign arbitrary labels for every vertex. Thus, you have initial labelling. Let's call it $x^0\colon V \rightarrow L$. Also, let us introduce the step number $i \gets 1$.

*Select an arbitrary ordering for the vertices.

*If you have already visited every vertex, return to the first one and call it $v^i$. Otherwise, Visit the next vertex according to the chosen order and call it $v^i$.

*And sample a new value of the label there from its conditional probability, saving the result to a new mapping $x^i\colon V \rightarrow L$. In formula,
$$
x^i(v^i) \sim P(\xi_{v^i} | \xi_{v'} = x^{i-1}(v^i), \forall v': (v^i, v') \in E), \\
x^i(v') = x^{i-1}(v'), \quad\forall v' \neq v^i.
$$

*If you want to proceed (because you have some stop criteria or for any other reason), make $i \gets i + 1$ and go to step 3.

The symbol "$\sim$" in the formula of the second step means that the value of $x^i(v)$ is generated (sampled) from a probability distribution written after the $\sim$.
I say "can" not because I'm in doubt, but because you may vary the order, you may sample blocks of multiple elements instead of visiting one by one, you can run it in parallel and do other things.
Example
Let me show you an example. Suppose we have a simple model with $L = {a, b}$, $V = {0, 1}$ and $E = {(0, 1)}$ with probabilities
$$
P(\xi_0 = a | \xi_1 = a) = 1/4, \\
P(\xi_0 = b | \xi_1 = a) = 3/4, \\
P(\xi_0 = a | \xi_1 = b) = 1/3, \\
P(\xi_0 = b | \xi_1 = b) = 2/3, \\
$$
and
$$
P(\xi_1 = a | \xi_0 = a) = 1/3, \\
P(\xi_1 = b | \xi_0 = a) = 2/3, \\
P(\xi_1 = a | \xi_0 = b) = 3/7, \\
P(\xi_1 = b | \xi_0 = b) = 4/7. \\
$$
Let us begin the sampling. First, we choose an arbitrary initial labelling. Let it be $x^0 = (a, a)$, where the first position is for $v = 0$ and the second is for $v = 1$.
Next, we use an arbitrary order. Let it be $v = 0$ and then $v = 1$. Let us sample the value of $x^1(0)$. Given a fixed label $x^0(1)$, the probability of the vertex $0$ having a label $a$ is $3/4$, and the probability of the vertex $0$ having a label $b$ is $1/4$. Let us use some generator of uniform distribution and let the value $a$ if it gives us a number less than $1/4$, and $b$ otherwise. I've launched my generator and got $0.5$. It's not less than $1/4$, so I use the value $b$.
Now, we have a labelling $x^1 = (b, a)$. Let us sample the label for the vertex $1$. Given the $x^2(0) = b$ the probabilities of the labels $a$ and $b$ are $3/7$ and $4/7$. So, I launch my generator again, and if it gives me a number less than $3/7$, then I choose label $a$; otherwise, I choose $b$. I've got $0.4$, so we assign $x^2(1) = a$. If I understand the book segment right, one can say that we have "sent" a sampled value from $x^2(0)$ to generate a value $x^2(1)$.
We can repeat these steps over and over. One of our purposes may be to find a marginal probability for $\xi_0$ and $\xi_1$ by counting the number of $a$ and $b$ labels assigned to the corresponding $x^i$. I've designed the probabilities so that $P(\xi_0 = a) = 0.3$, $P(\xi_0 = b) = 0.7$, $P(\xi_1 = a) = 0.4$, and $P(\xi_1 = b) = 0.6)$.
You may find more if you read about Monte Carlo Markov Chain (MCMC). Eventually, the sequence $(x^i: i \in \mathbb{N})$ is a Markov Chain because, given a labelling $x^{i-1}$ and a vertex $v$ you wish to sample, you know the probabilities of any labelling $x^i$. If you wish to estimate the probability $P(\xi_0 = a)$, you may run $n$ iterations of the algorithm and calculate the frequency
$$
n^{-1} \cdot \sum\limits_{i=0}^n [x^i(0) = a] \to P(\xi_0 = a),
\quad n\to\infty,
$$
where $[ \cdot ]$ is $1$ when the underlying expression is true, and $0$ otherwise. This is very similar to the Monte Carlo approach, with the difference that you have a Markov Chain instead of independent samples.
The MCMC has more applications than calculating marginal probabilities, and its use has a bunch of heuristics (it's more than just sampling and calculating an average). Also, you are free to use any other sampler (not only the Gibbs sampler).
