3.2 EM and its Simulated Versions as Precursors Besides a possible difficult computation in the E-step,problems with the EM algorithm (Dempster et al.1977)do occur in the case of multimodal likelihoods.The increase of the likelihood function at each step of the algorithm ensures its convergence to the maximum likelihood estimator in the case of unimodal likelihoods but it implies a dependence on initial conditions for multimodal likelihoods.Several proposals can be found in the literature to overcome this problem,one of which we now describe because of its connection with Gibbs sampling. Broniatowski et al.(1984)and Celeux and Diebolt (1985,1992)have tried to overcome the dependence of EM methods on the starting value by replacing the E step with a simulation step,the missing data z being generated conditionally on the observation z and on the current value of the parameter 0m.The maximization in the M step is then done on the (simulated)complete-data log-likelihood,H(,m).The appeal of this approach is that it allows for a more systematic exploration of the likelihood surface by partially avoiding the fatal attraction of the closest mode.Unfortunately,the theoretical convergence results for these methods are limited.Celeux and Diebolt (1990)have,however,solved the convergence problem of SEM by devising a hybrid version called SAEM(for Simulated Annealing EM), where the amount of randomness in the simulations decreases with the iterations,ending up with an EM algorithm.This version actually relates to simulated annealing methods 3.3 Gibbs,and Beyond Although somewhat removed from statistical inference in the classical sense and based on ear- lier techniques used in Statistical Physics,the landmark paper by Geman and Geman (1984) brought Gibbs sampling into the arena of statistical application.This paper is also responsi- ble for the name Gibbs sampling,because it implemented this method for the Bayesian study of Gibbs random fields which,in turn,derive their name from the physicist Josiah Willard Gibbs (1839-1903).This original implementation of the Gibbs sampler was applied to a discrete image processing problem and did not involve completion.But this was one more spark that led to the explosion,as it had a clear influence on Green,Smith,Spiegelhalter and others. 4 The Revolution The gap of more than 30 years between Metropolis et al.(1953)and Gelfand and Smith (1990)can still be partially attributed to the lack of appropriate computing power,as most 83.2 EM and its Simulated Versions as Precursors Besides a possible difficult computation in the E-step, problems with the EM algorithm (Dempster et al. 1977) do occur in the case of multimodal likelihoods. The increase of the likelihood function at each step of the algorithm ensures its convergence to the maximum likelihood estimator in the case of unimodal likelihoods but it implies a dependence on initial conditions for multimodal likelihoods. Several proposals can be found in the literature to overcome this problem, one of which we now describe because of its connection with Gibbs sampling. Broniatowski et al. (1984) and Celeux and Diebolt (1985, 1992) have tried to overcome the dependence of EM methods on the starting value by replacing the E step with a simulation step, the missing data z being generated conditionally on the observation x and on the current value of the parameter θm. The maximization in the M step is then done on the (simulated) complete-data log-likelihood, H˜ (x, zm|θ). The appeal of this approach is that it allows for a more systematic exploration of the likelihood surface by partially avoiding the fatal attraction of the closest mode. Unfortunately, the theoretical convergence results for these methods are limited. Celeux and Diebolt (1990) have, however, solved the convergence problem of SEM by devising a hybrid version called SAEM (for Simulated Annealing EM), where the amount of randomness in the simulations decreases with the iterations, ending up with an EM algorithm. This version actually relates to simulated annealing methods. 3.3 Gibbs, and Beyond Although somewhat removed from statistical inference in the classical sense and based on ear￾lier techniques used in Statistical Physics, the landmark paper by Geman and Geman (1984) brought Gibbs sampling into the arena of statistical application. This paper is also responsi￾ble for the name Gibbs sampling, because it implemented this method for the Bayesian study of Gibbs random fields which, in turn, derive their name from the physicist Josiah Willard Gibbs (1839–1903). This original implementation of the Gibbs sampler was applied to a discrete image processing problem and did not involve completion. But this was one more spark that led to the explosion, as it had a clear influence on Green, Smith, Spiegelhalter and others. 4 The Revolution The gap of more than 30 years between Metropolis et al. (1953) and Gelfand and Smith (1990) can still be partially attributed to the lack of appropriate computing power, as most 8