Editing Gibbs sampling (section)

== Properties ==
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.
* The [[expected 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 as [[expectation–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-called ''burn-in period''), and then consider only every <math>n</math>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) the [[stationary 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 a [[Markov chain]] with some amount of correlation. Sometimes, algorithms can be used to determine the amount of [[autocorrelation]] between samples and the value of <math>n</math> (the period between samples that are actually used) computed from this, but in practice there is a fair amount of "[[Black magic (programming)|black magic]]" involved.
* The process of [[simulated 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 the sample space, with a high amount of [[autocorrelation]] between samples, rather than moving around quickly, as is desired). Other techniques that may reduce autocorrelation are ''collapsed Gibbs sampling'', ''blocked Gibbs sampling'', and ''ordered overrelaxation''; see below.

=== Relation of conditional distribution and joint distribution ===
Furthermore, the conditional distribution of one variable given all others is proportional to the joint distribution, i.e., for all possible value <math>(x_i)_{1\leq i\leq n}</math> of <math>\mathbf{X}</math>:

:<math>P(X_j=x_j\mid (X_i=x_i)_{i\neq j}) = \frac{P((X_i=x_i)_i)}{P((X_i=x_i)_{i\neq j})} \propto P((X_i=x_i)_i)</math>

"Proportional to" in this case means that the denominator is not a function of <math>x_j</math> and thus is the same for all values of <math>x_j</math>; it forms part of the [[normalization constant]] for the distribution over <math>x_j</math>.  In practice, to determine the nature of the conditional distribution of a factor <math>x_j</math>, it is easiest to factor the joint distribution according to the individual conditional distributions defined by the [[graphical model]] over the variables, ignore all factors that are not functions of <math>x_j</math> (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:
# If the distribution is discrete, the individual probabilities of all possible values of <math>x_j</math> are computed, and then summed to find the normalization constant.
# If the distribution is continuous and of a known form, the normalization constant will also be known.
# In other cases, the normalization constant can usually be ignored, as most sampling methods do not require it.