Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex
Shuji Kijima, Tomomi Matsui
Abstract
In this paper, we are concerned with random sampling of an n dimensional integral point on an (n-1) dimensional simplex according to a multivariate discrete distribution. We employ sampling via Markov chain and propose two ``hit-and-run'' chains, one is for approximate sampling and the other is for perfect sampling. We introduce an idea of alternating inequalities and show that a logarithmic separable concave function satisfies the alternating inequalities. If a probability function satisfies alternating inequalities, then our chain for approximate sampling mixes in O(n2 ln(Kɛ-1)), namely (1/2)n(n-1) ln(K ɛ-1), where K is the side length of the simplex and ɛ (0<ɛ<1) is an error rate. On the same condition, we design another chain and a perfect sampler based on monotone CFTP (Coupling from the Past). We discuss a condition that the expected number of total transitions of the chain in the perfect sampler is bounded by O(n3 ln(Kn)).
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page