Instatistics,Gibbs sampling or aGibbs sampler is aMarkov chain Monte Carlo (MCMC)algorithm for sampling from a specifiedmultivariateprobability distribution when direct sampling from the joint distribution is difficult, but sampling from theconditional distribution is more practical. This sequence can be used to approximate the joint distribution (e.g., to generate a histogram of the distribution); to approximate themarginal distribution of one of the variables, or some subset of the variables (for example, the unknownparameters orlatent variables); or to compute anintegral (such as theexpected value of one of the variables). Typically, some of the variables correspond to observations whose values are known, and hence do not need to be sampled.

Gibbs sampling is commonly used as a means ofstatistical inference, especiallyBayesian inference. It is arandomized algorithm (i.e. an algorithm that makes use ofrandom numbers), and is an alternative todeterministic algorithms for statistical inference such as theexpectation–maximization algorithm (EM).

As with other MCMC algorithms, Gibbs sampling generates aMarkov chain of samples, each of which iscorrelated with nearby samples. As a result, care must be taken if independent samples are desired. Samples from the beginning of the chain (theburn-in period) may not accurately represent the desired distribution and are usually discarded.

Gibbs sampling is named after the physicistJosiah Willard Gibbs, in reference to an analogy between thesampling algorithm andstatistical physics. The algorithm was described by brothersStuart andDonald Geman in 1984, some eight decades after the death of Gibbs,^[1] and became popularized in the statistics community for calculating marginal probability distribution, especially the posterior distribution.^[2]

In its basic version, Gibbs sampling is a special case of theMetropolis–Hastings algorithm. However, in its extended versions (seebelow), it can be considered a general framework for sampling from a large set of variables by sampling each variable (or in some cases, each group of variables) in turn, and can incorporate theMetropolis–Hastings algorithm (or methods such asslice sampling) to implement one or more of the sampling steps.

Gibbs sampling is applicable when the joint distribution is not known explicitly or is difficult to sample from directly, but theconditional distribution of each variable is known and is easy (or at least, easier) to sample from. The Gibbs sampling algorithm generates an instance from the distribution of each variable in turn, conditional on the current values of the other variables. It can be shown that the sequence of samples constitutes aMarkov chain, and the stationary distribution of that Markov chain is just the sought-after joint distribution.^[3]

Gibbs sampling is particularly well-adapted to sampling theposterior distribution of aBayesian network, since Bayesian networks are typically specified as a collection of conditional distributions.

Gibbs sampling, in its basic incarnation, is a special case of theMetropolis–Hastings algorithm. The point of Gibbs sampling is that given amultivariate distribution it is simpler to sample from a conditional distribution than tomarginalize by integrating over ajoint distribution. Suppose we want to obtain${\displaystyle k}$ samples of a${\displaystyle n}$-dimensional random vector${\displaystyle \mathbf{X}=(X_1,\dots ,X_n)}$. We proceed iteratively:

• Begin with some initial value${\displaystyle {\mathbf{X}}^{(0)}}$.
• Given a sample${\displaystyle {\mathbf{X}}^{(i)}=\left(x_1^{(i)},\dots ,x_n^{(i)}\right)}$, to obtain the next sample${\displaystyle {\mathbf{X}}^{(i+1)}=\left(x_1^{(i+1)},x_2^{(i+1)},\dots ,x_n^{(i+1)}\right)}$, we can sample each component${\displaystyle x_j^{(i+1)}}$ from the distribution of${\displaystyle X_j}$, conditioned on all the components sampled so far: we condition on${\displaystyle X_{\ell }^{(i+1)}}$ for all${\displaystyle \ell \le j-1}$, and on${\displaystyle X_{\ell }^{(i)}}$ for${\displaystyle j+1\le \ell \le n}$. In other words, we sample${\displaystyle x_j^{(i+1)}}$ according to the distribution${\displaystyle P\left(X_j=\cdot |X_1=x_1^{(i+1)},\dots ,X_{j-1}=x_{j-1}^{(i+1)},X_{j+1}=x_{j+1}^{(i)},\dots ,X_n=x_n^{(i)}\right)}$.

If such sampling is performed, these important facts hold:

• The samples approximate the joint distribution of all variables.
• The marginal distribution of any subset of variables can be approximated by simply considering the samples for that subset of variables, ignoring the rest.
• Theexpected value of any variable can be approximated by averaging over all the samples.

When performing the sampling:

• The initial values of the variables can be determined randomly or by some other algorithm such asexpectation–maximization.
• It is not actually necessary to determine an initial value for the first variable sampled.
• It is common to ignore some number of samples at the beginning (the so-calledburn-in period), and then consider only every${\displaystyle n}$th sample when averaging values to compute an expectation. For example, the first 1,000 samples might be ignored, and then every 100th sample averaged, throwing away all the rest. The reason for this is that (1) thestationary distribution of the Markov chain is the desired joint distribution over the variables, but it may take a while for that stationary distribution to be reached; (2) successive samples are not independent of each other but form aMarkov chain with some amount of correlation. Sometimes, algorithms can be used to determine the amount ofautocorrelation between samples and the value of${\displaystyle n}$ (the period between samples that are actually used) computed from this, but in practice there is a fair amount of "black magic" involved.^{[citation needed]}
• The process ofsimulated annealing is often used to reduce the "random walk" behavior in the early part of the sampling process (i.e. the tendency to move slowly around thesample space, with a high amount ofautocorrelation between samples, rather than moving around quickly, as is desired). Other techniques that may reduce autocorrelation arecollapsed Gibbs sampling,blocked Gibbs sampling, andordered overrelaxation; see below.

Furthermore, the conditional distribution of one variable given all others is proportional to the joint distribution, i.e., for all possible value${\displaystyle (x_i{)}_{1\le i\le n}}$ of${\displaystyle \mathbf{X}}$:

${\displaystyle P(X_j=x_j\mid (X_i=x_i{)}_{i\ne j})=\frac{P((X_i=x_i{)}_i)}{P((X_i=x_i{)}_{i\ne j})}\propto P((X_i=x_i{)}_i)}$

"Proportional to" in this case means that the denominator is not a function of${\displaystyle x_j}$ and thus is the same for all values of${\displaystyle x_j}$; it forms part of thenormalization constant for the distribution over${\displaystyle x_j}$. In practice, to determine the nature of the conditional distribution of a factor${\displaystyle x_j}$, it is easiest to factor the joint distribution according to the individual conditional distributions defined by thegraphical model over the variables, ignore all factors that are not functions of${\displaystyle x_j}$ (all of which, together with the denominator above, constitute the normalization constant), and then reinstate the normalization constant at the end, as necessary. In practice, this means doing one of three things:

1. If the distribution is discrete, the individual probabilities of all possible values of${\displaystyle x_j}$ are computed, and then summed to find the normalization constant.
2. If the distribution is continuous and of a known form, the normalization constant will also be known.
3. In other cases, the normalization constant can usually be ignored, as most sampling methods do not require it.

Gibbs sampling is commonly used forstatistical inference (e.g. determining the best value of a parameter, such as determining the number of people likely to shop at a particular store on a given day, the candidate a voter will most likely vote for, etc.). The idea is that observed data is incorporated into the sampling process by creating separate variables for each piece of observed data and fixing the variables in question to their observed values, rather than sampling from those variables. The distribution of the remaining variables is then effectively aposterior distribution conditioned on the observed data.

The most likely value of a desired parameter (themode) could then simply be selected by choosing the sample value that occurs most commonly; this is essentially equivalent tomaximum a posteriori estimation of a parameter. (Since the parameters are usually continuous, it is often necessary to "bin" the sampled values into one of a finite number of ranges or "bins" in order to get a meaningful estimate of the mode.) More commonly, however, theexpected value (mean or average) of the sampled values is chosen; this is aBayes estimator that takes advantage of the additional data about the entire distribution that is available from Bayesian sampling, whereas a maximization algorithm such asexpectation maximization (EM) is capable of only returning a single point from the distribution. For example, for a unimodal distribution the mean (expected value) is usually similar to the mode (most common value), but if the distribution isskewed in one direction, the mean will be moved in that direction, which effectively accounts for the extra probability mass in that direction. (If a distribution is multimodal, the expected value may not return a meaningful point, and any of the modes is typically a better choice.)

Although some of the variables typically correspond to parameters of interest, others are uninteresting ("nuisance") variables introduced into the model to properly express the relationships among variables. Although the sampled values represent thejoint distribution over all variables, the nuisance variables can simply be ignored when computing expected values or modes; this is equivalent tomarginalizing over the nuisance variables. When a value for multiple variables is desired, the expected value is simply computed over each variable separately. (When computing the mode, however, all variables must be considered together.)

Supervised learning,unsupervised learning andsemi-supervised learning (aka learning with missing values) can all be handled by simply fixing the values of all variables whose values are known, and sampling from the remainder.

For observed data, there will be one variable for each observation—rather than, for example, one variable corresponding to thesample mean orsample variance of a set of observations. In fact, there generally will be no variables at all corresponding to concepts such as "sample mean" or "sample variance". Instead, in such a case there will be variables representing the unknown true mean and true variance, and the determination of sample values for these variables results automatically from the operation of the Gibbs sampler.

Generalized linear models (i.e. variations oflinear regression) can sometimes be handled by Gibbs sampling as well. For example,probit regression for determining the probability of a given binary (yes/no) choice, withnormally distributed priors placed over the regression coefficients, can be implemented with Gibbs sampling because it is possible to add additional variables and take advantage ofconjugacy. However,logistic regression cannot be handled this way. One possibility is to approximate thelogistic function with a mixture (typically 7–9) of normal distributions. More commonly, however,Metropolis–Hastings is used instead of Gibbs sampling.

Suppose that a sample${\displaystyle X}$ is taken from a distribution depending on a parameter vector${\displaystyle \theta \in \mathrm{\Theta }}$ of length${\displaystyle d}$, with prior distribution${\displaystyle g({\theta }_1,\dots ,{\theta }_d)}$. It may be that${\displaystyle d}$ is very large and thatnumerical integration to find the marginal densities of the${\displaystyle {\theta }_i}$ would be computationally expensive. Then an alternative method of calculating the marginal densities is to create a Markov chain on the space${\displaystyle \mathrm{\Theta }}$ by repeating these two steps:

1. Pick a random index${\displaystyle 1\le j\le d}$
2. Pick a new value for${\displaystyle {\theta }_j}$ according to${\displaystyle g({\theta }_1,\dots ,{\theta }_{j-1},\cdot ,{\theta }_{j+1},\dots ,{\theta }_d)}$

These steps define areversible Markov chain with the desired invariant distribution${\displaystyle g}$. Thiscan be proved as follows. Define${\displaystyle x{\sim }_{j}y}$ if${\displaystyle x_i=y_i}$ for all${\displaystyle i\ne j}$ and let${\displaystyle p_{xy}}$ denote the probability of a jump from${\displaystyle x\in \mathrm{\Theta }}$ to${\displaystyle y\in \mathrm{\Theta }}$. Then, the transition probabilities are

So

${\displaystyle g(x)p_{xy}=\frac{1}{d}\frac{g(x)g(y)}{\sum _{z\in \mathrm{\Theta }:z{\sim }_{j}x}g(z)}=\frac{1}{d}\frac{g(y)g(x)}{\sum _{z\in \mathrm{\Theta }:z{\sim }_{j}y}g(z)}=g(y)p_{yx}}$

since${\displaystyle x{\sim }_{j}y}$ is anequivalence relation. Thus thedetailed balance equations are satisfied, implying the chain is reversible and it has invariant distribution${\displaystyle g}$.

In practice, the index${\displaystyle j}$ is not chosen at random, and the chain cycles through the indexes in order. In general this gives a non-stationary Markov process, but each individual step will still be reversible, and the overall process will still have the desired stationary distribution (as long as the chain can access all states under the fixed ordering).

Let${\displaystyle y}$ denote observations generated from the sampling distribution${\displaystyle f(y|\theta )}$ and${\displaystyle \pi (\theta )}$ be a prior supported on the parameter space${\displaystyle \mathrm{\Theta }}$. Then one of the central goals of theBayesian statistics is to approximate the posterior density

${\displaystyle \pi (\theta |y)=\frac{f(y|\theta )\cdot \pi (\theta )}{m(y)}}$

where the marginal likelihood${\displaystyle m(y)={\int }_{\mathrm{\Theta }}f(y|\theta )\cdot \pi (\theta )d\theta }$ is assumed to be finite for all${\displaystyle y}$.

To explain the Gibbs sampler, we additionally assume that the parameter space${\displaystyle \mathrm{\Theta }}$ is decomposed as

${\displaystyle \mathrm{\Theta }=\prod _{i=1}^K{\mathrm{\Theta }}_i={\mathrm{\Theta }}_1\times \cdots {\mathrm{\Theta }}_i\times \cdots \times {\mathrm{\Theta }}_K,(K>1)}$,

where${\displaystyle \times }$ represents theCartesian product. Each component parameter space${\displaystyle {\mathrm{\Theta }}_i}$ can be a set of scalar components, subvectors, or matrices.

Define a set${\displaystyle {\mathrm{\Theta }}_{-i}}$ that complements the${\displaystyle {\mathrm{\Theta }}_i}$. Essential ingredients of the Gibbs sampler is the${\displaystyle i}$-th full conditional posterior distribution for each${\displaystyle i=1,\cdots ,K}$

${\displaystyle \pi ({\theta }_i|{\theta }_{-i},y)=\pi ({\theta }_i|{\theta }_1,\cdots ,{\theta }_{i-1},{\theta }_{i+1},\cdots ,{\theta }_K,y)}$.

The following algorithm details a generic Gibbs sampler:

${\displaystyle \text{Initialize: pick arbitrary starting value}{\theta }^{(1)}=({\theta }_1^{(1)},{\theta }_2^{(1)},\cdots ,{\theta }_i^{(1)},{\theta }_{i+1}^{(1)},\cdots ,{\theta }_K^{(1)})}$

${\displaystyle \text{Iterate a Cycle:}}$

${\displaystyle \text{Step 1. draw}{\theta }_1^{(s+1)}\sim \pi ({\theta }_1|{\theta }_2^{(s)},{\theta }_3^{(s)},\cdots ,{\theta }_K^{(s)},y)}$

${\displaystyle \text{Step 2. draw}{\theta }_2^{(s+1)}\sim \pi ({\theta }_2|{\theta }_1^{(s+1)},{\theta }_3^{(s)},\cdots ,{\theta }_K^{(s)},y)}$

${\displaystyle ⋮}$

${\displaystyle \text{Step i. draw}{\theta }_i^{(s+1)}\sim \pi ({\theta }_i|{\theta }_1^{(s+1)},{\theta }_2^{(s+1)},\cdots ,{\theta }_{i-1}^{(s+1)},{\theta }_{i+1}^{(s)},\cdots ,{\theta }_K^{(s)},y)}$

${\displaystyle \text{Step i+1. draw}{\theta }_{i+1}^{(s+1)}\sim \pi ({\theta }_{i+1}|{\theta }_1^{(s+1)},{\theta }_2^{(s+1)},\cdots ,{\theta }_i^{(s+1)},{\theta }_{i+2}^{(s)},\cdots ,{\theta }_K^{(s)},y)}$

${\displaystyle ⋮}$

${\displaystyle \text{Step K. draw}{\theta }_K^{(s+1)}\sim \pi ({\theta }_K|{\theta }_1^{(s+1)},{\theta }_2^{(s+1)},\cdots ,{\theta }_{K-1}^{(s+1)},y)}$

${\displaystyle \text{end Iterate}}$

Note that Gibbs sampler is operated by the iterative Monte Carlo scheme within a cycle. The${\displaystyle S}$ number of samples${\displaystyle \{{\theta }^{(s)}{\}}_{s=1}^S}$ drawn by the above algorithm formulates Markov Chains with the invariant distribution to be the target density${\displaystyle \pi (\theta |y)}$.

Now, for each${\displaystyle i=1,\cdots ,K}$, define the following information theoretic quantities:

${\displaystyle I({\theta }_i;{\theta }_{-i})=\text{KL}(\pi (\theta |y)||\pi ({\theta }_i|y)\cdot \pi ({\theta }_{-i}|y))={\int }_{\mathrm{\Theta }}\pi (\theta |y)\log (\frac{\pi (\theta |y)}{\pi ({\theta }_i|y)\cdot \pi ({\theta }_{-i}|y)})d\theta ,}$

${\displaystyle H({\theta }_{-i})=-{\int }_{{\mathrm{\Theta }}_{-i}}\pi ({\theta }_{-i}|y)\log \pi ({\theta }_{-i}|y)d{\theta }_{-i},}$

${\displaystyle H({\theta }_{-i}|{\theta }_i)=-{\int }_{\mathrm{\Theta }}\pi (\theta |y)\log \pi ({\theta }_{-i}|{\theta }_i,y)d\theta ,}$

namely, posteriormutual information, posterior differential entropy, and posterior conditional differential entropy, respectively. We can similarly define information theoretic quantities${\displaystyle I({\theta }_{-i};{\theta }_i)}$,${\displaystyle H({\theta }_i)}$, and${\displaystyle H({\theta }_i|{\theta }_{-i})}$ by interchanging the${\displaystyle i}$ and${\displaystyle -i}$ in the defined quantities. Then, the following${\displaystyle K}$ equations hold.^[4]

${\displaystyle I({\theta }_i;{\theta }_{-i})=H({\theta }_{-i})-H({\theta }_{-i}|{\theta }_i)=H({\theta }_i)-H({\theta }_i|{\theta }_{-i})=I({\theta }_{-i};{\theta }_i),(i=1,\cdots ,K)}$.

The mutual information${\displaystyle I({\theta }_i;{\theta }_{-i})}$ quantifies the reduction in uncertainty of random quantity${\displaystyle {\theta }_i}$ once we know${\displaystyle {\theta }_{-i}}$, a posteriori. It vanishes if and only if${\displaystyle {\theta }_i}$ and${\displaystyle {\theta }_{-i}}$ are marginally independent, a posterior. The mutual information${\displaystyle I({\theta }_i;{\theta }_{-i})}$ can be interpreted as the quantity that is transmitted from the${\displaystyle i}$-th step to the${\displaystyle i+1}$-th step within a single cycle of the Gibbs sampler.

Numerous variations of the basic Gibbs sampler exist. The goal of these variations is to reduce theautocorrelation between samples sufficiently to overcome any added computational costs.

• Ablocked Gibbs sampler groups two or more variables together and samples from theirjoint distribution conditioned on all other variables, rather than sampling from each one individually. For example, in ahidden Markov model, a blocked Gibbs sampler might sample from all thelatent variables making up theMarkov chain in one go, using theforward-backward algorithm.

• Acollapsed Gibbs sampler integrates out (marginalizes over) one or more variables when sampling for some other variable. For example, imagine that a model consists of three variablesA,B, andC. A simple Gibbs sampler would sample fromp(A | B,C), thenp(B | A,C), thenp(C | A,B). A collapsed Gibbs sampler might replace the sampling step forA with a sample taken from the marginal distributionp(A | C), with variableB integrated out in this case. Alternatively, variableB could be collapsed out entirely, alternately sampling fromp(A | C) andp(C | A) and not sampling overB at all. The distribution over a variableA that arises when collapsing a parent variableB is called acompound distribution; sampling from this distribution is generally tractable whenB is theconjugate prior forA, particularly whenA andB are members of theexponential family. For more information, see the article oncompound distributions or Liu (1994).^[5]

Inhierarchical Bayesian models withcategorical variables, such aslatent Dirichlet allocation and various other models used innatural language processing, it is quite common to collapse out theDirichlet distributions that are typically used asprior distributions over the categorical variables. The result of this collapsing introduces dependencies among all the categorical variables dependent on a given Dirichlet prior, and the joint distribution of these variables after collapsing is aDirichlet-multinomial distribution. The conditional distribution of a given categorical variable in this distribution, conditioned on the others, assumes an extremely simple form that makes Gibbs sampling even easier than if the collapsing had not been done. The rules are as follows:

1. Collapsing out a Dirichlet prior node affects only the parent and children nodes of the prior. Since the parent is often a constant, it is typically only the children that we need to worry about.
2. Collapsing out a Dirichlet prior introduces dependencies among all the categorical children dependent on that prior — butno extra dependencies among any other categorical children. (This is important to keep in mind, for example, when there are multiple Dirichlet priors related by the same hyperprior. Each Dirichlet prior can be independently collapsed and affects only its direct children.)
3. After collapsing, the conditional distribution of one dependent children on the others assumes a very simple form: The probability of seeing a given value is proportional to the sum of the corresponding hyperprior for this value, and the count of all of theother dependent nodes assuming the same value. Nodes not dependent on the same priormust not be counted. The same rule applies in other iterative inference methods, such asvariational Bayes orexpectation maximization; however, if the method involves keeping partial counts, then the partial counts for the value in question must be summed across all the other dependent nodes. Sometimes this summed up partial count is termed theexpected count or similar. The probability isproportional to the resulting value; the actual probability must be determined by normalizing across all the possible values that the categorical variable can take (i.e. adding up the computed result for each possible value of the categorical variable, and dividing all the computed results by this sum).
4. If a given categorical node has dependent children (e.g. when it is alatent variable in amixture model), the value computed in the previous step (expected count plus prior, or whatever is computed) must be multiplied by the actual conditional probabilities (not a computed value that is proportional to the probability!) of all children given their parents. See the article on theDirichlet-multinomial distribution for a detailed discussion.
5. In the case where the group membership of the nodes dependent on a given Dirichlet prior may change dynamically depending on some other variable (e.g. a categorical variable indexed by another latent categorical variable, as in atopic model), the same expected counts are still computed, but need to be done carefully so that the correct set of variables is included. See the article on theDirichlet-multinomial distribution for more discussion, including in the context of a topic model.

In general, any conjugate prior can be collapsed out, if its only children have distributions conjugate to it. The relevant math is discussed in the article oncompound distributions. If there is only one child node, the result will often assume a known distribution. For example, collapsing aninverse-gamma-distributedvariance out of a network with a singleGaussian child will yield aStudent's t-distribution. (For that matter, collapsing both the mean and variance of a single Gaussian child will still yield a Student's t-distribution, provided both are conjugate, i.e. Gaussian mean, inverse-gamma variance.)

If there are multiple child nodes, they will all become dependent, as in theDirichlet-categorical case. The resultingjoint distribution will have a closed form that resembles in some ways the compound distribution, although it will have a product of a number of factors, one for each child node, in it.

In addition, and most importantly, the resultingconditional distribution of one of the child nodes given the others (and also given the parents of the collapsed node(s), butnot given the children of the child nodes) will have the same density as theposterior predictive distribution of all the remaining child nodes. Furthermore, the posterior predictive distribution has the same density as the basic compound distribution of a single node, although with different parameters. The general formula is given in the article oncompound distributions.

For example, given a Bayes network with a set of conditionallyindependent identically distributedGaussian-distributed nodes withconjugate prior distributions placed on the mean and variance, the conditional distribution of one node given the others after compounding out both the mean and variance will be aStudent's t-distribution. Similarly, the result of compounding out thegamma prior of a number ofPoisson-distributed nodes causes the conditional distribution of one node given the others to assume anegative binomial distribution.

In these cases where compounding produces a well-known distribution, efficient sampling procedures often exist, and using them will often (although not necessarily) be more efficient than not collapsing, and instead sampling both prior and child nodes separately. However, in the case where the compound distribution is not well-known, it may not be easy to sample from, since it generally will not belong to theexponential family and typically will not belog-concave (which would make it easy to sample usingadaptive rejection sampling, since a closed form always exists).

In the case where the child nodes of the collapsed nodes themselves have children, the conditional distribution of one of these child nodes given all other nodes in the graph will have to take into account the distribution of these second-level children. In particular, the resulting conditional distribution will be proportional to a product of the compound distribution as defined above, and the conditional distributions of all of the child nodes given their parents (but not given their own children). This follows from the fact that the full conditional distribution is proportional to the joint distribution. If the child nodes of the collapsed nodes arecontinuous, this distribution will generally not be of a known form, and may well be difficult to sample from despite the fact that a closed form can be written, for the same reasons as described above for non-well-known compound distributions. However, in the particular case that the child nodes arediscrete, sampling is feasible, regardless of whether the children of these child nodes are continuous or discrete. In fact, the principle involved here is described in fair detail in the article on theDirichlet-multinomial distribution.

• A Gibbs sampler withordered overrelaxation samples a given odd number of candidate values for${\displaystyle x_j^{(i)}}$ at any given step and sorts them, along with the single value for${\displaystyle x_j^{(i-1)}}$ according to some well-defined ordering. If${\displaystyle x_j^{(i-1)}}$ is thes^th smallest in the sorted list then the${\displaystyle x_j^{(i)}}$ is selected as thes^th largest in the sorted list. For more information, see Neal (1995).^[6]

It is also possible to extend Gibbs sampling in various ways. For example, in the case of variables whose conditional distribution is not easy to sample from, a single iteration ofslice sampling or theMetropolis–Hastings algorithm can be used to sample from the variables in question.It is also possible to incorporate variables that are notrandom variables, but whose value isdeterministically computed from other variables.Generalized linear models, e.g.logistic regression (aka "maximum entropy models"), can be incorporated in this fashion. (BUGS, for example, allows this type of mixing of models.)

There are two ways that Gibbs sampling can fail. The first is when there are islands of high-probability states, with no paths between them. For example, consider a probability distribution over 2-bit vectors, where the vectors (0,0) and (1,1) each have probability⁠1/2⁠, but the other two vectors (0,1) and (1,0) have probability zero. Gibbs sampling will become trapped in one of the two high-probability vectors, and will never reach the other one. More generally, for any distribution over high-dimensional, real-valued vectors, if two particular elements of the vector are perfectly correlated (or perfectly anti-correlated), those two elements will become stuck, and Gibbs sampling will never be able to change them.

The second problem can happen even when all states have nonzero probability and there is only a single island of high-probability states. For example, consider a probability distribution over 100-bit vectors, where the all-zeros vector occurs with probability⁠1/2⁠, and all other vectors are equally probable, and so have a probability of${\displaystyle \frac{1}{2(2^{100}-1)}}$ each. If you want to estimate the probability of the zero vector, it would be sufficient to take 100 or 1000 samples from the true distribution. That would very likely give an answer very close to⁠1/2⁠. But you would probably have to take more than${\displaystyle 2^{100}}$ samples from Gibbs sampling to get the same result. No computer could do this in a lifetime.

This problem occurs no matter how long the burn-in period is. This is because in the true distribution, the zero vector occurs half the time, and those occurrences are randomly mixed in with the nonzero vectors. Even a small sample will see both zero and nonzero vectors. But Gibbs sampling will alternate between returning only the zero vector for long periods (about${\displaystyle 2^{99}}$ in a row), then only nonzero vectors for long periods (about${\displaystyle 2^{99}}$ in a row). Thus convergence to the true distribution is extremely slow, requiring much more than${\displaystyle 2^{99}}$ steps; taking this many steps is not computationally feasible in a reasonable time period. The slow convergence here can be seen as a consequence of thecurse of dimensionality.A problem like this can be solved by block sampling the entire 100-bit vector at once. (This assumes that the 100-bit vector is part of a larger set of variables. If this vector is the only thing being sampled, then block sampling is equivalent to not doing Gibbs sampling at all, which by hypothesis would be difficult.)

• TheOpenBUGS software (Bayesian inference Using Gibbs Sampling) does aBayesian analysis of complex statistical models usingMarkov chain Monte Carlo.

• JAGS (Just another Gibbs sampler) is a GPL program for analysis of Bayesian hierarchical models using Markov Chain Monte Carlo.

• Church is free software for performing Gibbs inference over arbitrary distributions that are specified as probabilistic programs.

• PyMC is an open sourcePython library forBayesian learning of generalProbabilistic Graphical Models.
• Turing is an open sourceJulia library forBayesian Inference usingprobabilistic programming.

• Bishop, Christopher M. (2006),Pattern Recognition and Machine Learning, Springer,ISBN 978-0-387-31073-2
• Bolstad, William M. (2010),Understanding Computational Bayesian Statistics, John WileyISBN 978-0-470-04609-8
• Casella, G.; George, E. I. (1992). "Explaining the Gibbs Sampler".The American Statistician.46 (3): 167.CiteSeerX 10.1.1.554.3993.doi:10.2307/2685208.JSTOR 2685208. (Contains a basic summary and many references.)
• Gelfand, Alan E.; Smith, Adrian F. M. (1990), "Sampling-Based Approaches to Calculating Marginal Densities",Journal of the American Statistical Association,85 (410):398–409,doi:10.2307/2289776,JSTOR 2289776,MR 1141740
• Gelman, A., Carlin J. B., Stern H. S., Dunson D., Vehtari A., Rubin D. B. (2013),Bayesian Data Analysis, third edition. London:Chapman & Hall.
• Levin, David A.;Peres, Yuval;Wilmer, Elizabeth L. (2008), "Markov Chains and Mixing Times",American Mathematical Society.
• Robert, C. P.; Casella, G. (2004),Monte Carlo Statistical Methods (second edition), Springer-Verlag.

• Markov chain Monte Carlo

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from October 2025