Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematical Informatics [Tokyo]

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 <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 $\textit{O}(n^2 \textit{ln}(Kɛ^{-1}))$, namely $(1/2)n(n-1) \textit{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 $\textit{O}(n^3 \textit{ln}(Kn))$.

Source: HAL:hal-01184209v1

Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: Log-concave function.,Coupling from the past,Markov chain,Mixing time,Path coupling,[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]

This page has been seen 152 times.

This article's PDF has been downloaded 147 times.