Geodesic
Markov bases of conditional independence models for permutations
Kybernetika, Tome 45 (2009) no. 2, pp. 249-260 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

The L-decomposable and the bi-decomposable models are two families of distributions on the set $S_n$ of all permutations of the first $n$ positive integers. Both of these models are characterized by collections of conditional independence relations. We first compute a Markov basis for the L-decomposable model, then give partial results about the Markov basis of the bi-decomposable model. Using these Markov bases, we show that not all bi-decomposable distributions can be approximated arbitrarily well by strictly positive bi-decomposable distributions.
The L-decomposable and the bi-decomposable models are two families of distributions on the set $S_n$ of all permutations of the first $n$ positive integers. Both of these models are characterized by collections of conditional independence relations. We first compute a Markov basis for the L-decomposable model, then give partial results about the Markov basis of the bi-decomposable model. Using these Markov bases, we show that not all bi-decomposable distributions can be approximated arbitrarily well by strictly positive bi-decomposable distributions.
Classification : 60C05, 60J99, 62E10, 62H05
Keywords: conditional independence; Markov basis; closure of exponential family; permutation; L-decomposable 
@article{KYB_2009_45_2_a3,
     author = {Csisz\'ar, Vill\H{o}},
     title = {Markov bases of conditional independence models for permutations},
     journal = {Kybernetika},
     pages = {249--260},
     year = {2009},
     volume = {45},
     number = {2},
     mrnumber = {2518150},
     zbl = {1165.62007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2009_45_2_a3/}
}
TY  - JOUR
AU  - Csiszár, Villő
TI  - Markov bases of conditional independence models for permutations
JO  - Kybernetika
PY  - 2009
SP  - 249
EP  - 260
VL  - 45
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2009_45_2_a3/
LA  - en
ID  - KYB_2009_45_2_a3
ER  - 
%0 Journal Article
%A Csiszár, Villő
%T Markov bases of conditional independence models for permutations
%J Kybernetika
%D 2009
%P 249-260
%V 45
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2009_45_2_a3/
%G en
%F KYB_2009_45_2_a3
Csiszár, Villő. Markov bases of conditional independence models for permutations. Kybernetika, Tome 45 (2009) no. 2, pp. 249-260. http://geodesic.mathdoc.fr/item/KYB_2009_45_2_a3/

[1] D. Cox, J. Little, and D. O’Shea: Ideals, Varieties, and Algorithms. Springer, New York 1992. | MR

[2] D. E. Critchlow, M. A. Fligner, and J. S. Verducci: Probability models on rankings. J. Math. Psych. 35 (1991), 294–318. | MR

[3] V. Csiszár: Conditional independence relations and log-linear models for random matchings. Acta Math. Hungar. (2008), Online First. | MR

[4] P. Diaconis and N. Eriksson: Markov bases for noncommutative Fourier analysis of ranked data. J. Symbolic Comput. 41 (2006), 173–181. | MR

[5] P. Diaconis and B. Sturmfels: Algebraic algorithms for sampling from conditional distributions. Ann. Statist. 26 (1998), 363–397. | MR

[6] A. Dobra: Markov bases for decomposable graphical models. Bernoulli 9 (2003), 1093–1108. | MR | Zbl

[7] M. A. Fligner and J. S. Verducci (eds.): Probability Models and Statistical Analyses for Ranking Data. Springer, New York 1993. | MR

[8] 4ti2 team: 4ti2 – A software package for algebraic, geometric and combinatorial problems on linear spaces. Available at www.4ti2.de.

[9] D. Geiger, C. Meek, and B. Sturmfels: On the toric algebra of graphical models. Ann. Statist. 34 (2006), 1463–1492. | MR

[10] R. D. Luce: Individual Choice Behavior. Wiley, New York 1959. | MR | Zbl

[11] J. I. Marden: Analyzing and Modelling Rank Data. Chapman and Hall, London 1995. | MR

[12] G. Pistone, E. Riccomagno, and H. P. Wynn: Algebraic Statistics. Chapman and Hall/CRC, Bocan Raton 2000. | MR

[13] F. Rapallo: Toric statistical models: parametric and binomial representations. Ann. Inst. Statist. Math. 59 (2007), 727–740. | MR | Zbl

[14] B. Sturmfels: Gröbner bases and convex polytopes. Amer. Math. Soc., Providence RI 1996. | MR | Zbl

[15] S. Sullivant: Toric Ideals in Algebraic Statistics. Ph.D. Thesis, University of California, Berkeley 2005. | MR

[16] A. Takemura and S. Aoki: Some characterizations of minimal Markov basis for sampling from discrete conditional distributions. Ann. Inst. Statist. Math. 56 (2004), 1–17. | MR