Unequal sampling for Monte Carlo EM algorithms

The EM algorithm is a widely used tool for calculating maximum likelihood estimates in problems involving incomplete data. The E-step of the algorithm involves an expectation of the complete data log-likelihood conditional on observed data. Even if the expectation step of the EM algorithm is analytically intractable it can often be approximated via Monte Carlo techniques. In many applications of EM the expectation step involves a sum of independent but not identically distributed components. In such cases, the sum of expectations can be approximated by a sum independent Monte Carlo means. All applications of Monte Carlo EM that we are aware of use an equal allocation rule for the Monte Carlo sample sizes in this setting. However, if the log-likelihood components have unequal variances, then it is clearly more efficient to use an unequal allocation rule. In this note, we discuss allocation rules for Monte Carlo resources and suggest a general but simple procedure for improving the efficiency of Monte Carlo implementations of the EM algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.