A Markov chain for certain triple systems

34 mins 22 secs, 475.50 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Cameron, PJ (London) Tuesday 25 March 2008, 14:35-15:05 Markov-chain Monte Carlo Methods

Created:

2008-03-27 11:32

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Cameron, PJ

Language:

eng (English)

Credits:

Author:

Cameron, PJ


Abstract:	In 1996, M. T. Jacobson and P. Matthews constructed a Markov chain whose limiting distribution is uniform on Latin squares. This has been a useful tool for exploring the properties of random Latin squares. However, very little is known about the rate of convergence of the Markov chain; more information about this would greatly enhance its value. A feature of the Jacobson-Matthews Markov chain is that it enlarges the search space by adding "improper" Latin squares which have one "fault"; when we move from an improper Latin square we must fix that fault but may create another one. The method has been extended to other classes of combinatorial structures (Steiner triple systems and 1-factorizations of complete graphs), and to more general versions of these (corresponding to the generalization from Steiner triple systems to BIBDs with an arbitrary value of lambda. Unfortunately, except in the case of orthogonal arrays (the generalization of Latin squares), the connectedness of the Markov chain is conjectured, but not known to hold. If the conjecture is true, then the limiting distribution in each of these cases will be uniform. Preprint of paper on the generalisation * http://www.maths.qmul.ac.uk/~pjc/preprints/gendesdm.pdf -

Abstract:

In 1996, M. T. Jacobson and P. Matthews constructed a Markov chain whose limiting distribution is uniform on Latin squares. This has been a useful tool for exploring the properties of random Latin squares. However, very little is known about the rate of convergence of the Markov chain; more information about this would greatly enhance its value.

A feature of the Jacobson-Matthews Markov chain is that it enlarges the search space by adding "improper" Latin squares which have one "fault"; when we move from an improper Latin square we must fix that fault but may create another one.

The method has been extended to other classes of combinatorial structures (Steiner triple systems and 1-factorizations of complete graphs), and to more general versions of these (corresponding to the generalization from Steiner triple systems to BIBDs with an arbitrary value of lambda. Unfortunately, except in the case of orthogonal arrays (the generalization of Latin squares), the connectedness of the Markov chain is conjectured, but not known to hold. If the conjecture is true, then the limiting distribution in each of these cases will be uniform.

Preprint of paper on the generalisation
* http://www.maths.qmul.ac.uk/~pjc/preprints/gendesdm.pdf -

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	475.50 MB	View	Download
Flash Video	480x360	803.84 kbits/sec	202.92 MB	View	Download
iPod Video	480x360	505.14 kbits/sec	127.52 MB	View	Download
Windows Media Video (for download)	480x360	476.03 kbits/sec	120.17 MB	View	Download
Windows Media Video (for streaming)	480x360	447.16 kbits/sec	112.88 MB	View	Download	Stream
RealMedia	480x360	878.25 kbits/sec	221.71 MB	View	Download	Stream
QuickTime (for download)	384x288	847.86 kbits/sec	214.04 MB	View	Download
QuickTime (for streaming)	480x360	906.95 kbits/sec	228.95 MB	View	Download
MP3	44100 Hz	125.01 kbits/sec	31.35 MB	Listen	Download