Polynomial time perfect sampler for discretized dirichlet distribution

Tomomi Matsui, Shuji Kijima

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


In this paper, we propose a perfect (exact) sampling algorithm according to a discretized Dirichlet distribution. The Dirichlet distribution appears as prior and posterior distribution for the multinomial distribution in many statistical methods in bioinformatics. Our algorithm is a monotone coupling from the past algorithm, which is a Las Vegas type randomized algorithm.We propose a new Markov chain whose limit distribution is a discretized Dirichlet distribution. Our algorithm simulates transitions of the chain O(n3 lnΔ) times where n is the dimension (the number of parameters) and 1/Δ is the grid size for discretization. Thus the obtained bound does not depend on the magnitudes of parameters. In each transition, we need to sample a random variable according to a discretized beta distribution (2-dimensional Dirichlet distribution). To show the polynomiality, we employ the path coupling method carefully and show that our chain is rapidly mixing.

Original languageEnglish
Title of host publicationThe Grammar of Technology Development
PublisherKluwer Academic Publishers
Number of pages21
ISBN (Print)9784431752318
Publication statusPublished - 2008
Externally publishedYes
Event2005 Workshop on the Grammar of Technology Development - Tokyo, Japan
Duration: Jan 15 2005Jan 16 2005

Publication series

NameThe Grammar of Technology Development


Other2005 Workshop on the Grammar of Technology Development

All Science Journal Classification (ASJC) codes

  • Management of Technology and Innovation


Dive into the research topics of 'Polynomial time perfect sampler for discretized dirichlet distribution'. Together they form a unique fingerprint.

Cite this