# Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex

1 Department of Mathematical Informatics Tokyo

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 $\textit{O}n^2 \textit{ln}Kɛ^{-1}$, namely $1-2nn-1 \textit{ln}K ɛ^{-1}$, where $K$ is the side length of the simplex and \$ɛ 0

Author: Shuji Kijima - Tomomi Matsui -

Source: https://hal.archives-ouvertes.fr/