Slice Sampler

An algorithm to generate samples from a univariate, possibly multimodal target distribution \(\pi(x) = \frac{\tilde{\pi}(x)}{Z_\pi}\). The algorithm makes use of auxillary variables by defining the following joint distribution: \[ \hat{\pi}(x,v) = \begin{cases} \frac{1}{Z_\pi} & \text{if } 0\leq v \leq \tilde{\pi}(x)\\ 0 & \text{otherwise}\end{cases}\]

Marginalizing over \(v\) gives the target distribution \(\pi\), since \(\int \hat{\pi}(x,v)\:dv = \int_0^{\tilde{\pi(x)}} \frac{1}{Z_\pi}\:dv = \frac{\tilde{p(x)}}{Z_\pi} = \pi(x)\)

We then use Gibbs sampling to sample from this joint distribution, then discard the auxillary variable samples. The full conditionals are:

\[\pi(v|x) = U_{[0, \tilde{\pi}(x)]}(v)\]

\[\pi(x|v) = U_A(x)\]

Where \(A = \{x: \tilde{\pi}(x)\leq v\}\). To get a uniform sample over \(A\) however, we first need to identify this region. This can be done by first defining an interval \([x_s - L, x_s + R]\) centered at the last sample \(x_s\) with \(L,R\) possibly chosen randomly, and keep extending each endpoint until \(\tilde{\pi}(x_e)<\tilde{\pi}(x_s)\) where \(x_e\) is the endpoint. This is called the stepping out stage. The sample \(x_{s+1}\sim U_A(x)\) is accepted if \(\tilde{\pi}(x_{s+1})>v\), if rejected, the horizontal slice can be narrowed with \(x_{s+1}\) being at the relevant endpoint.