A Fresh Look at the Running Time Analysis for the Gibbs Sampler

As the Gibbs sampler has become one of the standard tools in computing, the practice of burn-in is almost the default option. Because it takes a certain number of iterations for the initial distribution to reach stationarity, supporters of burn-in will throw away an initial segment of the samples and argue that such a practice ensures unbiasedness. Running time analysis studies the question of how many samples to be thrown away. Basically, it equates the number of iterations to stationarity with the number of initial samples to be discarded. However, many practitioners have found that burn-in wastes potentially useful samples and the practice is inefficient, and thus unnecessary. For the example considered, a single chain without burn-in offers both efficiency and accuracy superior to multiple chains with burn-in. We show that the Gibbs sampler uses odds to generate samples. Because the correct odds are used from the onset of the iterative process, the observations generated by the Gibbs sampler are identically distributed as the target distribution; thus throwing away those valid samples is wasteful. When the chain of distributions and the trajectory (sample path) of the chain are considered based on their separate merits, the disagreement can be settled. We advocate carefully choosing the initial state, but without burn-in to quicken the formation of the stationary distribution.