target invariant!Hastings (1970)actually refers to Erhman et al.(1960)as a preliminary if specific instance of this sampler.More precisely,this is Metropolis-within-Gibbs except for the name.It is quite amazing that this first introduction of the Gibbs sampler has been completely overlooked,even though the proof of convergence is completely general,based on a composition argument as in Tierney (1994)!The remainder of the paper deals with (a)an importance sampling version of MCMC,(b)general remarks about assessment of the error,(c)an application to random orthogonal matrices(with yet again an example of Gibbs sampling). Three years later,still in Biometrika,Peskun(1973)publishes a comparison of Metropolis' and Barker's forms of acceptance probabilities and shows(again in a discrete setup)that the optimal choice (in terms of the asymptotic variance of any empirical average)is Metropolis'. The proof is a direct consequence of a result by Kemeny and Snell(1960)on the asymptotic variance.Peskun also establishes that this asymptotic variance can improve upon the iid case if and only if the eigenvalues of P-A are all negative,when A is the transition matrix corresponding to the iid simulation and P the transition matrix corresponding to the Metropolis algorithm,but he concludes that the trace of P-A is always positive. 3 Seeds of the Revolution A number of earlier pioneers had brought forward the seeds of Gibbs sampling;in particular. Hammersley and Clifford had produced a constructive argument in 1970 to recover a joint distribution from its conditionals,a result later called the Hammersley-Clifford theorem by Besag (1974,1986).Besides Hastings (1970)and Geman and Geman (1984),already mentioned,other papers that contained the germs of Gibbs sampling are Besag and Clifford (1989),Broniatowski et al.(1984),Qian and Titterington (1990),and Tanner and Wong (1987). 3.1 Besag's Early Work and the Fundamental (Missing)Theorem In the early 1970's,Hammersley,Clifford,and Besag were working on the specification of joint distributions from conditional distributions and on necessary and sufficient conditions for the conditional distributions to be compatible with a joint distribution.What is now known as the Hammersley-Clifford theorem states that a joint distribution for a vector asso- ciated with a dependence graph (edge meaning dependence and absence of edge conditional independence)must be represented as a product of functions over the cligues of the graphs. that is,of functions depending only on the components indexed by the labels in the cliquetarget invariant! Hastings (1970) actually refers to Erhman et al. (1960) as a preliminary if specific instance of this sampler. More precisely, this is Metropolis-within-Gibbs except for the name. It is quite amazing that this first introduction of the Gibbs sampler has been completely overlooked, even though the proof of convergence is completely general, based on a composition argument as in Tierney (1994)! The remainder of the paper deals with (a) an importance sampling version of MCMC, (b) general remarks about assessment of the error, (c) an application to random orthogonal matrices (with yet again an example of Gibbs sampling). Three years later, still in Biometrika, Peskun (1973) publishes a comparison of Metropolis’ and Barker’s forms of acceptance probabilities and shows (again in a discrete setup) that the optimal choice (in terms of the asymptotic variance of any empirical average) is Metropolis’. The proof is a direct consequence of a result by Kemeny and Snell (1960) on the asymptotic variance. Peskun also establishes that this asymptotic variance can improve upon the iid case if and only if the eigenvalues of P − A are all negative, when A is the transition matrix corresponding to the iid simulation and P the transition matrix corresponding to the Metropolis algorithm, but he concludes that the trace of P − A is always positive. 3 Seeds of the Revolution A number of earlier pioneers had brought forward the seeds of Gibbs sampling; in particular, Hammersley and Clifford had produced a constructive argument in 1970 to recover a joint distribution from its conditionals, a result later called the Hammersley–Clifford theorem by Besag (1974, 1986). Besides Hastings (1970) and Geman and Geman (1984), already mentioned, other papers that contained the germs of Gibbs sampling are Besag and Clifford (1989), Broniatowski et al. (1984), Qian and Titterington (1990), and Tanner and Wong (1987). 3.1 Besag’s Early Work and the Fundamental (Missing) Theorem In the early 1970’s, Hammersley, Clifford, and Besag were working on the specification of joint distributions from conditional distributions and on necessary and sufficient conditions for the conditional distributions to be compatible with a joint distribution. What is now known as the Hammersley-Clifford theorem states that a joint distribution for a vector asso￾ciated with a dependence graph (edge meaning dependence and absence of edge conditional independence) must be represented as a product of functions over the cliques of the graphs, that is, of functions depending only on the components indexed by the labels in the clique 6