Slice sampling is a type of Markov chain Monte Carlo algorithm used to draw pseudo-random samples from a statistical distribution. The method is based on the observation that to sample a random variable one can sample uniformly from the region under the graph of its density function.
Suppose you want to sample some random variable X with distribution f(x). Suppose that the following is the graph of f(x). The height of f(x) corresponds to the likelihood at that point.
If you were to uniformly sample X, each value would have the same likelihood of being sampled, and your distribution would be of the form f(x)=y for some y value instead of some non-uniform function f(x). Instead of the original black line, your new distribution would look more like the blue line.
In order to sample X in a manner which will retain the distribution f(x), some sampling technique must be used which takes into account the varied likelihoods for each range of f(x).
Slice sampling is a Markov chain method and as such serves the same purpose as Gibbs sampling and Metropolis. Unlike Metropolis, there is no need to manually tune the candidate function or candidate standard deviation.
Recall that Metropolis is sensitive to step size. If the step size is too small random walk causes slow decorrelation. If the step size is too large there is great inefficiency due to a high rejection rate.
In contrast to Metropolis, slice sampling automatically adjusts the step size to match the local shape of the density function. Implementation is arguably easier and more efficient than Gibbs sampling or simple Metropolis updates.
Note that, in contrast to many available methods for generating random numbers from non-uniform distributions, random variates generated directly by this approach will exhibit serial statistical dependence. In other words, not all points have the same independent likelihood of selection. This is a desired behavior, as the sampling likelihood should follow the properties of the sampled distribution (i.e. x value ranges in f(x) with a greater area under the curve should have a higher likelihood of selection over value ranges with a lesser area under the curve).
Slice Sampling requires that the distribution to be sampled be evaluable. One way to relax this requirement is to substitute an evaluable distribution which is proportional to the true unevaluable distribution.
thumb|350pxFor a given sample x, a value for y is chosen from [0, f(x)], which defines a "slice" of the distribution (shown by the solid horizontal line). In this case, there are two slices separated by an area outside the range of the distribution. To sample a random variable X with density f(x) we introduce an auxiliary variable Y and iterate as follows:
Our auxiliary variable Y represents a horizontal “slice” of the distribution. The rest of each iteration is dedicated to sampling an x value from the slice which is representative of the density of the region being considered.
In practice, sampling from a horizontal slice of a multimodal distribution is difficult. There is a tension between obtaining a large sampling region and thereby making possible large moves in the distribution space, and obtaining a simpler sampling region to increase efficiency. One option for simplifying this process is regional expansion and contraction.
500px-slice.png Finding a sample given a set of slices (the slices are represented here as blue lines and correspond to the solid line slices in the previous graph of f(x) ). a) A width parameter w is set. b) A region of width w is identified around a given point $x_0$. c) The region is expanded by w until both endpoints are outside of the considered slice. d) $x_1$ is selected uniformly from the region. e) Since $x_1$ lies outside the considered slice, the region's left bound is adjusted to $x_1$. f) Another uniform sample $x$ is taken and accepted as the sample since it lies within the considered slice.
Single variable slice sampling can be used in the multivariate case by sampling each variable in turn repeatedly, as in Gibbs sampling. To do so requires that we can compute, for each component $x_i$ a function that is proportional to $p(x_i|x_0\ldotsx_n)$.
To prevent random walk behavior, overrelaxation methods can be used to update each variable in turn. Overrelaxation chooses a new value on the opposite side of the mode from the current value, as opposed to choosing a new independent value from the distribution as done in Gibbs.
This method adapts the univariate algorithm to the multivariate case by substituting a hyperrectangle for the one-dimensional w region used in the original. The hyperrectangle H is initialized to a random position over the slice. H is then shrunken as points from it are rejected.
Reflective slice sampling is a technique to suppress random walk behavior in which the successive candidate samples of distribution f(x) are kept within the bounds of the slice by “reflecting” the direction of sampling inward toward the slice once the boundary has been hit.
In this graphical representation of reflective sampling, the shape indicates the bounds of a sampling slice. The dots indicate start and stopping points of a sampling walk. When the samples hit the bounds of the slice, the direction of sampling is “reflected” back into the slice.
Let us consider a single variable example. Suppose our true distribution $g(x)~N(0,5)$. So: $f(x) = \frac{1}{\sqrt{2\pi*5^2}} * e^{ -\frac{(x-0)^2}{2*5^2} }$
Explain how a slice sampling algorithm would work. Assume the univariate case using an overrelaxation update method. Be explicit in how the overrelaxation method would work.