In mathematics and physics, Gibbs sampling is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables. The purpose of such a sequence is to approximate the joint distribution (as with a histogram), or to compute an integral (such as an expected value). Gibbs sampling is a special case of the Metropolis-Hastings algorithm, and thus an example of a Markov chain Monte Carlo algorithm. The algorithm is named after the physicist J. W. Gibbs, in reference to an analogy between the sampling algorithm and statistical physics. The algorithm was devised by Geman and Geman (citation below), some eight decades after the passing of Gibbs, and is also called the Gibbs sampler. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics on Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Since antiquity, people have tried to understand the behavior of matter: why unsupported objects drop to the ground, why different materials have different properties, and so forth. ... Flowcharts are often used to represent algorithms. ... This article defines some terms which characterize probability distributions of two or more variables. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... In statistics, a histogram is a graphical display of tabulated frequencies. ... In calculus, the integral of a function is a generalization of area, mass, volume, sum, and total. ... In probability theory (and especially gambling), the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical... The Sampling distribution Q determines the next point to move to in the random walk. ... Markov chain Monte Carlo (MCMC) methods, sometimes called random walk Monte Carlo methods, are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its stationary distribution. ... Josiah Willard Gibbs (February 11, 1839 – April 28, 1903) was an American mathematical physicist who contributed much of the theoretical foundation that led to the development of chemical thermodynamics and was one of the founders of vector analysis. ... Statistical physics, one of the fundamental theories of physics, uses methods of statistics in solving physical problems. ...

Gibbs sampling is applicable when the joint distribution is not known explicitly, but the conditional distribution of each variable is known. The Gibbs sampling algorithm is to generate an instance from the distribution of each variable in turn, conditional on the current values of the other variables. It can be shown (see, for example, Gelman et al.) that the sequence of samples comprises a Markov chain, and the stationary distribution of that Markov chain is just the sought-after joint distribution. Given two jointly distributed random variables X and Y, the conditional probability distribution of Y given X (written Y | X) is the probability distribution of Y when X is known to be a particular value. ... In mathematics, a (discrete-time) Markov chain, named after Andrei Markov, is a discrete-time stochastic process with the Markov property. ...

Gibbs sampling is particularly well-adapted to sampling the posterior distribution of a Bayesian network, since Bayesian networks are typically specified as a collection of conditional distributions. BUGS (link below) is a program for carrying out Gibbs sampling on Bayesian networks. The posterior probability can be calculated by Bayes theorem from the prior probability and the likelihood function. ... A Bayesian network or Bayesian belief network or just belief network is a directed acyclic graph of nodes representing variables and arcs representing dependence relations among the variables. ...

Implementation

Suppose that a sample X is taken from a distribution depending on a parameter , with prior distribution where . It may be that d is very large and numerical integration to find the marginal densities of the θ_i will be too computationally expensive. Instead a Markov chain is created on the space Θ as follows:

1. Pick a random suffix
2. Pick a new value for θ_j according to

Then it can be shown that this is a reversible markov chain with invariant distribution g as follows. Define if x_i = y_i for all and let p_xy denote the probability of a jump from to . Then This page meets Wikipedias criteria for speedy deletion. ...

so

so the detailed balance equations are satisfied showing that the chain is reversible, and that it has invariant distribution g. In mathematics, and in statistical mechanics in physics, a Markov process is said to show detailed balance if the transition rates between each pair of states i and j in the state space obey where P is the Markov transition matrix, ie Pij = P( Xt =i | Xt-1 =j ); and...

In practice, the suffix j is not chosen at random, and the chain cycles through the suffices in order. In general this gives a non-reversible chain, but it will still have the desired invariant distribution (as long as the chain can access all states under the fixed ordering).

See also

• Gibbs state

A Gibbs state in probability theory and statistical mechanics is an equilibrium probability distribution which remains invariant under future evolution of the system (for example, a stationary or steady-state distribution of a Markov chain, such as that achieved by running a Markov Chain Monte Carlo iteration for a sufficiently...

References

• George Casella and Edward I. George. "Explaining the Gibbs sampler". The American Statistician, 46:167-174, 1992. (Basic summary and many references.)
• A.E. Gelfand and A.F.M. Smith. "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398-409, 1990.
• Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. London: Chapman and Hall. First edition, 1995. (See Chapter 11.)
• S. Geman and D. Geman. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, 1984.
• C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.

External links

• The BUGS Project - Bayesian inference Using Gibbs Sampling