Slice sampling: Difference between revisions

Revision as of 16:38, 29 August 2013

Revision as of 16:49, 17 September 2013

Line 18:

To visualize this motivation, imagine printing out a simple bell curve and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now take off all of the darts that are outside the curve (i.e. perform [[rejection sampling]]). The x-positions of the remaining darts will be distributed according to the bell curve. This is because there is the most room for the darts to land where curve is highest and thus the probability density is greatest.

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

#Choose a starting value x₀ for which f(x₀)>0.

#Compute the maximum value of the distribution (i.e. its maximum y-position).

#Sample a y value uniformly between 0 and this maximum y-positionf(x₀).

#Draw a horizontal line across the curve at this y position.

#Sample uniformlya alongpoint the(x,y) portionsfrom of thisthe line segments within the curve.

#Repeat from step 2 using the new 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 first randomly pickingselecting onea ofslice that falls at or below the slicescurve at the x-position from the previous iteration, then randomly picking an x-position somewhere along the slice. By using the 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.

Generally, the trickiest 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 discontiguous 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.