###### tags: `one-offs` `sampling` `markov chains` `monte carlo`

# Slicing and Random Walk Metropolis

**Overview**: In this note, I explain some connections between Slice Sampling and the Random Walk Metropolis MCMC algorithm.

## Algorithm Formulations and Reordering Steps

Consider the following MCMC transition kernel, with q some symmetric proposal:

1. At x,

a) Sample $u\sim\mathcal{U}\left[0,1\right]$.

b) Define the set $S\left(x,u\right) = \left\{ y: \frac{\pi \left(y\right)}{\pi \left(x\right)} >u \right\}$.

c) Sample $y\sim q\left(x,y\right)$.

d) If $y\in S\left(x,u\right)$, then move to $y$; else, stay at $x$.

Reading carefully, one can check that this is in fact equivalent to a standard Random Walk MH scheme. This framing essentially transposes the usual order of the 'propose' and 'evaluate' steps. A byproduct of this perspective is that it allows RWMH to be viewed as a coarse approximation to (Ideal) Slice Sampling, wherein you would instead do

1. At $x$,

a) Sample $u \sim \mathcal{U}\left[0,1\right]$.

b) Define the set $S \left(x,u\right) = \left\{ y: \frac{\pi \left(y\right)}{\pi \left(x\right)} > u \right\}$.

c) Sample $y \sim \mathcal{U} \left(S \left(x,u\right)\right)$.

d) Move to y.

Under fairly mild assumptions, this allows for a clean proof that (Ideal) Slice Sampling _dominates_ RWMH in terms of $\mathrm{L}^{2}$ convergence behaviour. There is also a similar result for 'hybrid' slice sampling, which is more-or-less implementable (c.f. Ideal Slice Sampling, whose implementability depends on the topology of the sets $S \left(x,u\right))$.

I became aware of this super nice observation from [this paper](https://arxiv.org/abs/1505.00579), published [here](https://cambridge.org/core/journals/journal-of-applied-probability/article/comparison-of-hitandrun-slice-sampler-and-random-walk-metropolis/9E32DA02A6E30F0D405C4D1115759BD3); I do not know whether it had also appeared earlier. Anyhow, very neat!