Slice sampling

Slice sampling is a type of Markov chain Monte Carlo algorithm for pseudo-random number sampling, i.e. for drawing random samples from a statistical distribution. The method is based on the fact that to sample a random variable one can sample uniformly from the region under the graph of its density function.

Motivation Sampling a random variable x {\displaystyle x} from a given probability density function f ( x ) {\displaystyle f(x)} is a common task in statistics. The figure (below left) sketches the graph of f ( x ) {\displaystyle f(x)} , where the height at x {\displaystyle x} corresponds to the likelihood at that point. In the case of uniform distribution, each value of x {\displaystyle x} would have the same likelihood of being sampled, and the corresponding function would be f ( x ) = y {\displaystyle f(x)=y} for some constant y {\displaystyle y} . Instead of the original black line, a uniform distribution is denoted by the blue line in the second figure (below right). In order to sample x {\displaystyle x} in a manner which will retain the distribution f ( x ) {\displaystyle f(x)} , a sampling technique that takes into account the varied likelihoods for each range of f ( x ) {\displaystyle f(x)} must be used.

Method Slice sampling, in its simplest form, samples uniformly from underneath the curve f ( x ) {\displaystyle f(x)} without the need to reject any points, as follows:

Choose a starting value x 0 {\displaystyle x_{0}} for which f ( x 0 ) > 0 {\displaystyle f(x_{0})>0}

Sample a y {\displaystyle y} value uniformly between 0 {\displaystyle 0} and f ( x 0 ) {\displaystyle f(x_{0})} . Draw a horizontal line across the curve at this y {\displaystyle y} position. Sample a point ( x , y ) {\displaystyle (x,y)} from the line segments within the curve. Repeat from step 2 using the new x {\displaystyle x} value. The motivation here is that one way to sample a point uniformly from within an arbitrary curve is first to draw thin uniform-height horizontal slices across the whole curve. Then, we can sample a point within the curve by randomly selecting a slice that falls at or below the curve at the x {\displaystyle x} -position from the previous iteration, then randomly picking an x {\displaystyle x} -position somewhere along the slice. By using the x {\displaystyle x} -position from the previous iteration of the algorithm, in the long run we select slices with probabilities proportional to the lengths of their segments within the curve. The most difficult part of this algorithm is finding the bounds of the horizontal slice, which involves inverting the function describing the distribution being sampled from. This is especially problematic for multi-modal distributions, where the slice may consist of multiple discontinuous parts. It is often possible to use a form of rejection sampling to overcome this, where we sample from a larger slice that is known to include the desired slice in question, and then discard points outside of the desired slice. This algorithm can be used to sample from the area under any curve, regardless of whether the function integrates to 1. In fact, scaling a function by a constant has no effect on the sampled x {\displaystyle x} -positions. This means that the algorithm can be used to sample from a distribution whose probability density function is only known up to a constant (i.e. whose normalizing constant is unknown), which is common in computational statistics.

… excerpt ends here. Continue reading the full article.