Fast perfect sampling from linear extensions. (English) Zbl 1090.60064
Summary: We study the problem of sampling (exactly) uniformly from the set of linear extensions of an arbitrary partial order. Previous Markov chain techniques have yielded algorithms that generate approximately uniform samples. Here, we create a bounding chain for one such Markov chain, and by using a non-Markovian coupling together with a modified form of coupling from the past, we build an algorithm for perfectly generating samples. The expected running time of the procedure is \(O(n^{3} \ln n)\), making the technique as fast as the mixing time of the Karzanov-Khachiyan chain [A. Karzanov and L. Khachiyan, Order 8, No. 1, 7–15 (1991; Zbl 0736.06002)] upon which it is based.
MSC:
| 60J22 | Computational methods in Markov chains |
| 06A06 | Partial orders, general |
| 65C05 | Monte Carlo methods |
Citations:
Zbl 0736.06002References:
| [1] | Aldous, D., Some inequalities for reversible Markov chains, J. London Math. Soc., 25, 2, 561-576 (1982) · Zbl 0489.60077 |
| [2] | Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 3, 225-242 (1991) · Zbl 0759.06001 |
| [3] | R. Bubley, M. Dyer, Path coupling: a technique for proving rapid mixing in Markov chains, in: 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 223-231.; R. Bubley, M. Dyer, Path coupling: a technique for proving rapid mixing in Markov chains, in: 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 223-231. |
| [4] | Bubley, R.; Dyer, M., Faster random generation of linear extensions, Discrete Math., 201, 81-88 (1999) · Zbl 0934.65005 |
| [5] | Doeblin, W., Exposé de la théorie des chains simples constantes de Markov à un nombre fini d’états, Rev. Math. de l’Union Interbalkanique, 2, 77-105 (1933) · JFM 64.0538.01 |
| [6] | Dyer, M.; Frieze, A.; Kannan, R., A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach., 38, 1, 1-17 (1991) · Zbl 0799.68107 |
| [7] | S. Felsner, L. Wernisch, Markov chains for linear extensions, the two-dimensional case, in: Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, 1997, pp. 239-247.; S. Felsner, L. Wernisch, Markov chains for linear extensions, the two-dimensional case, in: Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, 1997, pp. 239-247. · Zbl 1321.68369 |
| [8] | Fill, J. A.; Machida, M.; Murdoch, D. J.; Rosenthal, J. S., Extension of fill’s perfect rejection sampling algorithm to general chains, Random Structures Algorithms, 17, 290-316 (2000) · Zbl 1122.60310 |
| [9] | Häggström, O.; Nelander, K., On exact simulation from Markov random fields using coupling from the past, Scand. J. Statist., 26, 3, 395-411 (1999) · Zbl 0944.60059 |
| [10] | M.L. Huber, Exact sampling and approximate counting techniques, in: Proceedings of the 30th Symposium on the Theory of Computing, 1998, pp. 31-40.; M.L. Huber, Exact sampling and approximate counting techniques, in: Proceedings of the 30th Symposium on the Theory of Computing, 1998, pp. 31-40. · Zbl 1028.68218 |
| [11] | M.L. Huber, Perfect sampling with bounding chains, Ph.D. Thesis, Cornell University, 1999.; M.L. Huber, Perfect sampling with bounding chains, Ph.D. Thesis, Cornell University, 1999. · Zbl 1052.60057 |
| [12] | Jerrum, M.; Valiant, L.; Vazirani, V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., 43, 169-188 (1986) · Zbl 0597.68056 |
| [13] | Karzanov, A.; Khachiyan, L., On the conductance of order Markov chains, Order, 8, 1, 7-15 (1991) · Zbl 0736.06002 |
| [14] | Mathews, P., Generating a random linear extension of a partial order, Ann. Probab., 19, 3, 1367-1392 (1991) · Zbl 0728.60009 |
| [15] | Propp, J. G.; Wilson, D. B., Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures Algorithms, 9, 1-2, 223-252 (1996) · Zbl 0859.60067 |
| [16] | Wilson, D. B., Mixing times of lozenge tiling and card shuffling Markov chains, Ann. Appl. Probab., 14, 1, 274-325 (2004) · Zbl 1040.60063 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
