In this paper we introduce a new stochastic variant of the EM algorithm. The algorithm combines the principle of multiple imputation and the theory of simulated annealing to deal with cases where the E-step and the M-step can be intractable or numerically inefficient.