  Metropolis-Hastings estimates intractable expectations - can differentiating
the algorithm estimate their gradients? The challenge is that
Metropolis-Hastings trajectories are not conventionally differentiable due to
the discrete accept/reject steps. Using a technique based on recoupling chains,
our method differentiates through the Metropolis-Hastings sampler itself,
allowing us to estimate gradients with respect to a parameter of otherwise
intractable expectations. Our main contribution is a proof of strong
consistency and a central limit theorem for our estimator under assumptions
that hold in common Bayesian inference problems. The proofs augment the sampler
chain with latent information, and formulate the estimator as a stopping tail
functional of this augmented chain. We demonstrate our method on examples of
Bayesian sensitivity analysis and optimizing a random walk Metropolis proposal.
