Random sampling of Latin squares via binary contingency tables and probabilistic divide-and-conquer

2017/03/24 by Stephen DeSalvo, DeSalvo, Stephen
Mathematics · #Advanced Combinatorial Mathematics #Computation (stat.CO) #FOS: Computer and information sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.1703.08627

openalex publication_date 2017/03/24 · openalex created_date 2017/04/07 · openalex updated_date 2026/07/28

Abstract

We demonstrate a novel approach for the random sampling of Latin squares of order~n via probabilistic divide-and-conquer. The algorithm divides the entries of the table modulo powers of 2, and samples a corresponding binary contingency table at each level. The sampling distribution is based on the Boltzmann sampling heuristic, along with probabilistic divide-and-conquer.

Citations

• Algebraic algorithms for sampling from conditional distributions
• Random Latin squares and Sudoku designs generation

Related

• Exact sampling algorithms for Latin squares and Sudoku matrices via\n probabilistic divide-and-conquer
• Random Sampling of Contingency Tables via Probabilistic Divide-and-Conquer
• Random Latin squares and Sudoku designs generation
• Parities in random Latin squares
• Probabilistic divide-and-conquer: deterministic second half