Markov bases for noncommutative Fourier analysis of ranked data

Simple item page
dc.creatorDiaconis, Persi
dc.creatorEriksson, Nicholas
dc.date2004-05-04
dc.date2005-03-09
dc.date.accessioned2026-07-07T08:06:16Z
dc.date.available2026-07-07T08:06:16Z
dc.descriptionTo calibrate Fourier analysis of $S_5$ ranking data by Markov chain Monte Carlo techniques, a set of moves (Markov basis) is needed. We calculate this basis, and use it to provide a new statistical analysis of two data sets. The calculation involves a large Gröbner basis computation (45825 generators), but reduction to a minimal basis and reduction by natural symmetries leads to a remarkably small basis (14 elements). Although the Gröbner basis calculation is infeasible for $S_6$, we exploit the symmetry of the problem to calculate a Markov basis for $S_6$ with 7,113,390 elements in 58 symmetry classes. We improve a bound on the degree of the generators for a Markov basis for $S_n$ and conjecture that this ideal is generated in degree 3.
dc.description16 pages, 2 figures. To appear in the Journal of Symbolic Computation, special issue on Computational Algebraic Statistics. Minor edits, some small corrections for the S_6 numbers, added download location for code
dc.identifierhttps://arxiv.org/abs/math/0405060
dc.identifierhttp://arxiv.org/abs/math/0405060
dc.identifierJournal of Symbolic Computation, Volume 41, Issue 2, February 2006, Pages 182-195
dc.identifierdoi:10.1016/j.jsc.2005.04.009
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/130547
dc.subjectCommutative Algebra
dc.subjectCombinatorics
dc.titleMarkov bases for noncommutative Fourier analysis of ranked data
dc.typetext

Files

Collections

arXiv