An Efficient MCMC Algorithm to Sample Binary Matrices with Fixed Marginals

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...

Full description

Saved in:
Bibliographic Details
Published in:Psychometrika 2008-12, Vol.73 (4), p.705-728
Main Author: Verhelst, Norman D.
Format: Article
Language:English
Subjects:
Algorithms
Assessment
Behavioral Science and Psychology
Biological and medical sciences
Educational evaluation
Educational tests & measurements
Fundamental and applied biological sciences. Psychology
Geometric Concepts
Humanities
Law
Markov analysis
Markov Processes
Mathematics
Measurement Techniques
Nonparametric statistics
Probability
Problem Solving
Psychology
Psychology. Psychoanalysis. Psychiatry
Psychology. Psychophysiology
Psychometrics
Psychometrics. Statistics. Methodology
Rasch model
Sample size
Sampling
Social Networks
Statistical Theory and Methods
Statistics for Social Sciences
Statistics. Mathematics
Testing and Evaluation
Theory and Methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (300×30) 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.
ISSN:0033-3123
1860-0980
DOI:10.1007/s11336-008-9062-3