Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex
| Autor: | Shuji Kijima, Tomomi Matsui |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2005 |
| Předmět: |
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] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AD,..., Iss Proceedings (2005) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3374 |
| Popis: | 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 |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|