  The right to be forgotten has been legislated in many countries, but its
enforcement in the AI industry would cause unbearable costs. When single data
deletion requests come, companies may need to delete the whole models learned
with massive resources. Existing works propose methods to remove knowledge
learned from data for explicitly parameterized models, which however are not
appliable to the sampling-based Bayesian inference, i.e., Markov chain Monte
Carlo (MCMC), as MCMC can only infer implicit distributions. In this paper, we
propose the first machine unlearning algorithm for MCMC. We first convert the
MCMC unlearning problem into an explicit optimization problem. Based on this
problem conversion, an {\it MCMC influence function} is designed to provably
characterize the learned knowledge from data, which then delivers the MCMC
unlearning algorithm. Theoretical analysis shows that MCMC unlearning would not
compromise the generalizability of the MCMC models. Experiments on Gaussian
mixture models and Bayesian neural networks confirm the effectiveness of the
proposed algorithm. The code is available at
\url{https://github.com/fshp971/mcmc-unlearning}.
