Loading [MathJax]/jax/output/HTML-CSS/jax.js

Shuji Kijima ; Tomomi Matsui - Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex

dmtcs:3374 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3374
Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplexConference paper

Authors: Shuji Kijima 1; Tomomi Matsui 1

  • 1 Department of Mathematical Informatics [Tokyo]

In this paper, we are concerned with random sampling of an n dimensional integral point on an (n1) 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 <i>alternating inequalities </i> and show that a <i>logarithmic separable concave</i> function satisfies the alternating inequalities. If a probability function satisfies alternating inequalities, then our chain for approximate sampling mixes in O(n2ln(Kɛ1)), namely (1/2)n(n1)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(n3ln(Kn)).


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Markov chain,Mixing time,Path coupling,Coupling from the past,Log-concave function.,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 230 times.
This article's PDF has been downloaded 201 times.