Aldous, David (ed.) et al., Discrete probability and algorithms. Proceedings of the workshops “Probability and algorithms” and “The finite Markov chain renaissance” held at IMA, University of Minnesota, Minneapolis, MN, USA, 1993. New York, NY: Springer-Verlag. IMA Vol. Math. Appl. 72, 15-41 (1995).
This is an elegant survey article about the number of rectangular arrays of nonnegative integers with given row and column sums and its importance in various combinatorial and statistical applications. The combinatorial problems include magical squares, enumeration of permutations by descents, enumeration of double cosets, the description of tensor product decompositions, Young tableaux and Kostka numbers. The statistical applications focus on tests for independence in contingency tables with given margins. Several exact and approximative methods for determining the array numbers are described. The computational complexity is discussed. The authors also present Monte Carlo techniques based on Markov chains on the set of arrays with prespecified margins.
|05A15||Exact enumeration problems, generating functions|
|60G50||Sums of independent random variables; random walks|
|60J10||Markov chains (discrete-time Markov processes on discrete state spaces)|
|62H17||Contingency tables (statistics)|
|65C05||Monte Carlo methods|
|05B15||Orthogonal arrays, Latin squares, Room squares|