An Efficient MCMC Algorithm to Sample Binary Matrices with Fixed Marginals

Autor/in	Verhelst, Norman D.
Titel	An Efficient MCMC Algorithm to Sample Binary Matrices with Fixed Marginals
Quelle	In: Psychometrika, 73 (2008) 4, S.705-728 (24 Seiten) PDF als Volltext Verfügbarkeit
Sprache	englisch
Dokumenttyp	gedruckt; online; Zeitschriftenaufsatz
ISSN	0033-3123
DOI	10.1007/s11336-008-9062-3
Schlagwörter	Markov Processes; Sampling; Geometric Concepts; Social Networks; Mathematics; Problem Solving + Suchen Sie Ihr Suchwort? Markowscher Prozess; Elementare Geometrie; Social network; Soziales Netzwerk; Mathematik; Problemlösen
Abstract	Uniform sampling of binary matrices with fixed margins is known as a difficult problem. Two classes of algorithms to sample from a distribution not too different from the uniform are studied in the literature: importance sampling and Markov chain Monte Carlo (MCMC). Existing MCMC algorithms converge slowly, require a long burn-in period and yield highly dependent samples. Chen et al. developed an importance sampling algorithm that is highly efficient for relatively small tables. For larger but still moderate sized tables (300x30) Chen et al.'s algorithm is less efficient. This article develops a new MCMC algorithm that converges much faster than the existing ones and that is more efficient than Chen's algorithm for large problems. Its stationary distribution is uniform. The algorithm is extended to the case of square matrices with fixed diagonal for applications in social network theory. (As Provided).
Anmerkungen	Springer. 233 Spring Street, New York, NY 10013. Tel: 800-777-4643; Tel: 212-460-1500; Fax: 212-348-4505; e-mail: service-ny@springer.com; Web site: http://www.springerlink.com
Erfasst von	ERIC (Education Resources Information Center), Washington, DC
Update	2017/4/10