Implementations of the exponential mechanism in differential privacy often
require sampling from intractable distributions. When approximate procedures
like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to
both privacy and accuracy. Existing work has examined these effects
asymptotically, but implementable finite sample results are needed in practice
so that users can specify privacy budgets in advance and implement samplers
with exact privacy guarantees. In this paper, we use tools from ergodic theory
and perfect simulation to design exact finite runtime sampling algorithms for
the exponential mechanism by introducing an intermediate modified target
distribution using artificial atoms. We propose an additional modification of
this sampling algorithm that maintains its $epsilon$-DP guarantee and has
improved runtime at the cost of some utility. We then compare these methods in
scenarios where we can explicitly calculate a $delta$ cost (as in $(epsilon,
delta)$-DP) incurred when using standard MCMC techniques. Much as there is a
well known trade-off between privacy and utility, we demonstrate that there is
also a trade-off between privacy guarantees and runtime.