Pattern Recognition and Machine Learning

11.3. Gibbs Sampling 543

in some particular order or by choosing the variable to be updated at each step at

random from some distribution.

For example, suppose we have a distributionp(z 1 ,z 2 ,z 3 )over three variables,

and at stepτof the algorithm we have selected valuesz 1 (τ),z( 2 τ)andz 3 (τ). We first

replacez 1 (τ)by a new valuez 1 (τ+1)obtained by sampling from the conditional distri-

bution

p(z 1 |z 2 (τ),z( 3 τ)). (11.46)

Next we replacez( 2 τ)by a valuez( 2 τ+1)obtained by sampling from the conditional

distribution

p(z 2 |z( 1 τ+1),z 3 (τ)) (11.47)

so that the new value forz 1 is used straight away in subsequent sampling steps. Then

we updatez 3 with a samplez 3 (τ+1)drawn from

p(z 3 |z( 1 τ+1),z( 2 τ+1)) (11.48)

and so on, cycling through the three variables in turn.

Gibbs Sampling

1. Initialize{zi:i=1,...,M}


2. Forτ=1,...,T:
   
   
   • Samplez( 1 τ+1)∼p(z 1 |z( 2 τ),z 3 (τ),...,zM(τ)).
   
   
   • Samplez
     (τ+1)
     2 ∼p(z^2 |z
   
   
   
   

(τ+1)

1 ,z

(τ)

3 ,...,z

(τ)

M).

..

.

• Samplez
  (τ+1)
  j ∼p(zj|z

(τ+1)

1 ,...,z

(τ+1)

j− 1 ,z

(τ)

j+1,...,z

(τ)

M).

..

.

• Samplez(Mτ+1)∼p(zM|z( 1 τ+1),z 2 (τ+1),...,zM(τ+1)− 1 ).

Josiah Willard Gibbs

1839–1903

Gibbs spent almost his entire life liv-
ing in a house built by his father in
New Haven, Connecticut. In 1863,
Gibbs was granted the first PhD in
engineering in the United States,
and in 1871 he was appointed to
the first chair of mathematical physics in the United

States at Yale, a post for which he received no salary

because at the time he had no publications. He de-

veloped the field of vector analysis and made contri-

butions to crystallography and planetary orbits. His

most famous work, entitledOn the Equilibrium of Het-

erogeneous Substances, laid the foundations for the

science of physical chemistry.