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

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/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))$.
Keywords :
Type de document :
Communication dans un congrès
Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.371-382, 2005, DMTCS Proceedings
Domaine :

Littérature citée [19 références]

https://hal.inria.fr/hal-01184209
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:34:21
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:21:57

### Fichier

Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184209, version 1

### Citation

Shuji Kijima, Tomomi Matsui. Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex. Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.371-382, 2005, DMTCS Proceedings. 〈hal-01184209〉

### Métriques

Consultations de la notice

## 72

Téléchargements de fichiers