Premium
Generating uniformly distributed random latin squares
Author(s) -
Jacobson Mark T.,
Matthews Peter
Publication year - 1996
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/(sici)1520-6610(1996)4:6<405::aid-jcd3>3.0.co;2-j
Subject(s) - mathematics , combinatorics , markov chain , bounded function , latin square , stationary distribution , discrete mathematics , ergodic theory , distribution (mathematics) , statistics , pure mathematics , mathematical analysis , rumen , fermentation , chemistry , food science
By simulating an ergodic Markov chain whose stationary distribution is uniform over the space of n × n Latin squares, we can obtain squares that are (approximately) uniformly distributed; we offer two such chains. The central issue is the construction of “moves” that connect the squares. Our first approach uses the fact that an n × n Latin square is equivalent to an n × n × n contingency table in which each line sum equals 1. We relax the nonnegativity condition on the table's cells, allowing “improper” tables that have a single—1‐cell. A simple set of moves connects this expanded space of tables [the diameter of the associated graph is bounded by 2( n − 1) 3 ], and suggests a Markov chain whose subchain of proper tables has the desired uniform stationary distribution (with an average of approximately n steps between proper tables). By grouping these moves appropriately, we derive a class of moves that stay within the space of proper Latin squares [with graph diameter bounded by 4( n − 1) 2 ]; these may also be used to form a suitable Markov chain. © 1996 John Wiley & Sons, Inc.