The normalization constant in the distribution of a discrete random variable may not be available in closed form; in such cases, the calculation of the likelihood can be computationally expensive. Approximations of the likelihood or approximate Bayesian computation methods can be used; but the resulting Markov chain Monte Carlo (MCMC) algorithm may not sample from the target of interest. In certain situations, one can efficiently compute lower and upper bounds on the likelihood. As a result, the target density and the acceptance probability of the Metropolis–Hastings algorithm can be bounded. We propose an efficient and exact MCMC algorithm based on the idea of retrospective sampling. This procedure can be applied to a number of discrete distributions, one of which is the Conway–Maxwell–Poisson distribution. In practice, the bounds on the acceptance probability do not need to be particularly tight in order to accept or reject a move. We demonstrate this method using data on the emergency hospital admissions in Scotland in 2010, where the main interest lies in the estimation of the variability of admissions, as it is considered as a proxy for health inequalities. Copyright © 2014 John Wiley & Sons, Ltd.