  We analyze the convergence rate of a simplified version of a popular Gibbs
sampling method used for statistical discovery of gene regulatory binding
motifs in DNA sequences. This sampler satisfies a very strong form of
ergodicity (uniform). However, we show that, due to multimodality of the
posterior distribution, the rate of convergence often decreases exponentially
as a function of the length of the DNA sequence. Specifically, we show that
this occurs whenever there is more than one true repeating pattern in the data.
In practice there are typically multiple such patterns in biological data, the
goal being to detect the most well-conserved and frequently-occurring of these.
Our findings match empirical results, in which the motif-discovery Gibbs
sampler has exhibited such poor convergence that it is used only for finding
modes of the posterior distribution (candidate motifs) rather than for
obtaining samples from that distribution. Ours are some of the first meaningful
bounds on the convergence rate of a Markov chain method for sampling from a
multimodal posterior distribution, as a function of statistical quantities like
the number of observations.
