Negative dependence and the geometry of polynomials
Authors:
Julius Borcea, Petter Brändén and Thomas M. Liggett
Journal:
J. Amer. Math. Soc. 22 (2009), 521-567
MSC (2000):
Primary 62H20; Secondary 05B35, 15A15, 15A22, 15A48, 26C10, 30C15, 32A60, 60C05, 60D05, 60E05, 60E15, 60G55, 60K35, 82B31
DOI:
https://doi.org/10.1090/S0894-0347-08-00618-8
Published electronically:
September 19, 2008
MathSciNet review:
2476782
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: We introduce the class of strongly Rayleigh probability measures by means of geometric properties of their generating polynomials that amount to the stability of the latter. This class covers important models such as determinantal measures (e.g. product measures and uniform random spanning tree measures) and distributions for symmetric exclusion processes. We show that strongly Rayleigh measures enjoy all virtues of negative dependence, and we also prove a series of conjectures due to Liggett, Pemantle, and Wagner, respectively. Moreover, we extend Lyons’ recent results on determinantal measures, and we construct counterexamples to several conjectures of Pemantle and Wagner on negative dependence and ultra log-concave rank sequences.
- Michael Aissen, I. J. Schoenberg, and A. M. Whitney, On the generating functions of totally positive sequences. I, J. Analyse Math. 2 (1952), 93–103 (English, with Hebrew summary). MR 53174, DOI https://doi.org/10.1007/BF02786970
- Enrique D. Andjel, A correlation inequality for the symmetric exclusion process, Ann. Probab. 16 (1988), no. 2, 717–721. MR 929073
- M. F. Atiyah, R. Bott, and L. Gȧrding, Lacunas for hyperbolic differential operators with constant coefficients. I, Acta Math. 124 (1970), 109–189. MR 470499, DOI https://doi.org/10.1007/BF02394570
- Heinz H. Bauschke, Osman Güler, Adrian S. Lewis, and Hristo S. Sendov, Hyperbolic polynomials and convex analysis, Canad. J. Math. 53 (2001), no. 3, 470–488. MR 1827817, DOI https://doi.org/10.4153/CJM-2001-020-6
- J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206–229. MR 2216966, DOI https://doi.org/10.1214/154957806000000078
- Julius Borcea, Spectral order and isotonic differential operators of Laguerre-Pólya type, Ark. Mat. 44 (2006), no. 2, 211–240. MR 2292718, DOI https://doi.org/10.1007/s11512-006-0017-6 BBS J. Borcea, P. Brändén, Pólya-Schur master theorems for circular domains and their boundaries, to appear in Ann. of Math., http://annals.math.princeton.edu.
- Julius Borcea and Petter Brändén, Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products, Duke Math. J. 143 (2008), no. 2, 205–223. MR 2420507, DOI https://doi.org/10.1215/00127094-2008-018 BBS2 J. Borcea, P. Brändén, Multivariate Pólya-Schur classification problems in the Weyl algebra, arXiv:math/0606360. BB J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs I. Linear operators preserving stability, arXiv:0809.0401. BB-2 J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs II. Theory of stable polynomials and applications, preprint (2008). BBCV J. Borcea, P. Brändén, G. Csordas, V. Vinnikov, Pólya-Schur-Lax problems: hyperbolicity and stability preservers, http://www.aimath.org/pastworkshops/polyaschurlax.html.
- Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481–515. MR 1758751, DOI https://doi.org/10.1090/S0894-0347-00-00337-4
- Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), no. 1-2, 55–64. MR 1194785, DOI https://doi.org/10.1007/BF02808010
- Petter Brändén, Polynomials with the half-plane property and matroid theory, Adv. Math. 216 (2007), no. 1, 302–320. MR 2353258, DOI https://doi.org/10.1016/j.aim.2007.05.011
- Robert Burton and Robin Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab. 21 (1993), no. 3, 1329–1371. MR 1235419
- David Carlson, Weakly sign-symmetric matrices and some determinantal inequalities, Colloq. Math. 17 (1967), 123–129. MR 212041, DOI https://doi.org/10.4064/cm-17-1-123-129
- Seth Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 319–329. MR 666857, DOI https://doi.org/10.1137/0603033
- Young-Bin Choe, James G. Oxley, Alan D. Sokal, and David G. Wagner, Homogeneous multivariate polynomials with the half-plane property, Adv. in Appl. Math. 32 (2004), no. 1-2, 88–187. Special issue on the Tutte polynomial. MR 2037144, DOI https://doi.org/10.1016/S0196-8858%2803%2900078-2
- Youngbin Choe and David G. Wagner, Rayleigh matroids, Combin. Probab. Comput. 15 (2006), no. 5, 765–781. MR 2248326, DOI https://doi.org/10.1017/S0963548306007541
- J. Brian Conrey, The Riemann hypothesis, Notices Amer. Math. Soc. 50 (2003), no. 3, 341–353. MR 1954010
- Thomas Craven and George Csordas, Jensen polynomials and the Turán and Laguerre inequalities, Pacific J. Math. 136 (1989), no. 2, 241–260. MR 978613
- D. J. Daley and D. Vere-Jones, An introduction to the theory of point processes, Springer Series in Statistics, Springer-Verlag, New York, 1988. MR 950166
- Devdatt Dubhashi, Johan Jonasson, and Desh Ranjan, Positive influence and negative dependence, Combin. Probab. Comput. 16 (2007), no. 1, 29–41. MR 2286510, DOI https://doi.org/10.1017/S0963548306007772 DPR D. Dubhashi, V. Priebe, D. Ranjan, Negative Dependence Through the FKG Inequality, Technical Report RS-96-27, BRICS Report Series, Basic Research In Computer Science, Århus, Denmark, 1996; web version available at http://citeseer.ist.psu.edu/352490.html.
- Devdatt Dubhashi and Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures Algorithms 13 (1998), no. 2, 99–124. MR 1642566, DOI https://doi.org/10.1002/%28SICI%291098-2418%28199809%2913%3A2%3C99%3A%3AAID-RSA1%3E3.0.CO%3B2-M
- Stewart N. Ethier and Thomas G. Kurtz, Markov processes, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. Characterization and convergence. MR 838085
- Shaun M. Fallat and Charles R. Johnson, Determinantal inequalities: ancient history and recent advances, Algebra and its applications (Athens, OH, 1999) Contemp. Math., vol. 259, Amer. Math. Soc., Providence, RI, 2000, pp. 199–212. MR 1778502, DOI https://doi.org/10.1090/conm/259/04095 feder T. Feder, M. Mihail, Balanced matroids, in “Proceedings of the 24th Annual ACM (STOC)”, ACM Press, New York, 1992.
- C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre, Correlation inequalities on some partially ordered sets, Comm. Math. Phys. 22 (1971), 89–103. MR 309498 GK F. R. Gantmacher, M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, Gostechizdat, 1950. grace J. H. Grace, The zeros of a polynomial, Proc. Cambridge Philos. Soc. 11 (1902), 352–357.
- Geoffrey Grimmett, The random-cluster model, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. MR 2243761 Gu1 L. Gurvits, A proof of hyperbolic van der Waerden conjecture: the right generalization is the ultimate simplification, arXiv:math/0504397.
- Leonid Gurvits, Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 417–426. MR 2277167, DOI https://doi.org/10.1145/1132516.1132578
- Osman Güler, Hyperbolic polynomials and interior point methods for convex programming, Math. Oper. Res. 22 (1997), no. 2, 350–377. MR 1450796, DOI https://doi.org/10.1287/moor.22.2.350
- Lars Gȧrding, An inequality for hyperbolic polynomials, J. Math. Mech. 8 (1959), 957–965. MR 0113978, DOI https://doi.org/10.1512/iumj.1959.8.58061
- G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988. Reprint of the 1952 edition. MR 944909
- Olga Holtz, $M$-matrices satisfy Newton’s inequalities, Proc. Amer. Math. Soc. 133 (2005), no. 3, 711–717. MR 2113919, DOI https://doi.org/10.1090/S0002-9939-04-07576-8
- Olga Holtz and Hans Schneider, Open problems on GKK $\tau $-matrices, Linear Algebra Appl. 345 (2002), 263–267. MR 1883278, DOI https://doi.org/10.1016/S0024-3795%2801%2900492-X
- Olga Holtz and Bernd Sturmfels, Hyperdeterminantal relations among symmetric principal minors, J. Algebra 316 (2007), no. 2, 634–648. MR 2358606, DOI https://doi.org/10.1016/j.jalgebra.2007.01.039
- Olle Häggström, Random-cluster measures and uniform spanning trees, Stochastic Process. Appl. 59 (1995), no. 2, 267–275. MR 1357655, DOI https://doi.org/10.1016/0304-4149%2895%2900042-6
- Lars Hörmander, Notions of convexity, Progress in Mathematics, vol. 127, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1301332
- Gordon James, Charles Johnson, and Stephen Pierce, Generalized matrix function inequalities on $M$-matrices, J. London Math. Soc. (2) 57 (1998), no. 3, 562–582. MR 1659833, DOI https://doi.org/10.1112/S0024610798005870
- Kumar Joag-Dev and Frank Proschan, Negative association of random variables, with applications, Ann. Statist. 11 (1983), no. 1, 286–295. MR 684886, DOI https://doi.org/10.1214/aos/1176346079
- Kurt Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), no. 1, 259–296. MR 1826414, DOI https://doi.org/10.2307/2661375
- Kurt Johansson, Determinantal processes with number variance saturation, Comm. Math. Phys. 252 (2004), no. 1-3, 111–148. MR 2103906, DOI https://doi.org/10.1007/s00220-004-1186-4 KN J. Kahn, M. Neiman, Negative correlation and log-concavity, arXiv:math/0712.3507.
- Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif, 1968. MR 0230102
- B. Ja. Levin, Distribution of zeros of entire functions, Revised edition, Translations of Mathematical Monographs, vol. 5, American Mathematical Society, Providence, R.I., 1980. Translated from the Russian by R. P. Boas, J. M. Danskin, F. M. Goodspeed, J. Korevaar, A. L. Shields and H. P. Thielman. MR 589888
- Elliott H. Lieb and Alan D. Sokal, A general Lee-Yang theorem for one-component and multicomponent ferromagnets, Comm. Math. Phys. 80 (1981), no. 2, 153–179. MR 623156
- Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231
- Thomas M. Liggett, Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A 79 (1997), no. 2, 315–325. MR 1462561, DOI https://doi.org/10.1006/jcta.1997.2790
- Thomas M. Liggett, Stochastic interacting systems: contact, voter and exclusion processes, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 324, Springer-Verlag, Berlin, 1999. MR 1717346
- T. M. Liggett, Negative correlations and particle systems, Markov Process. Related Fields 8 (2002), no. 4, 547–564. MR 1957219 L3 T. M. Liggett, Distributional limits for the symmetric exclusion process, to appear in Stoch. Proc. Appl, arXiv:math/0710.3606.
- Russell Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167–212. MR 2031202, DOI https://doi.org/10.1007/s10240-003-0016-0 Lyons-Peres R. Lyons, Y. Peres, Probability on Trees and Networks. Book in progress, web version available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.
- Russell Lyons and Jeffrey E. Steif, Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120 (2003), no. 3, 515–575. MR 2030095, DOI https://doi.org/10.1215/S0012-7094-03-12032-3
- Klas Markström, Negative association does not imply log-concavity of the rank sequence, J. Appl. Probab. 44 (2007), no. 4, 1119–1121. MR 2382951, DOI https://doi.org/10.1239/jap/1197908830
- Albert W. Marshall and Ingram Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, vol. 143, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 552278
- J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), Inst. Math. Appl., Southend-on-Sea, 1972, pp. 207–220. MR 0349445
- C. M. Newman, Normal fluctuations and the FKG inequalities, Comm. Math. Phys. 74 (1980), no. 2, 119–128. MR 576267
- Andrei Okounkov and Nikolai Reshetikhin, Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram, J. Amer. Math. Soc. 16 (2003), no. 3, 581–603. MR 1969205, DOI https://doi.org/10.1090/S0894-0347-03-00425-9
- Robin Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (2000), no. 3, 1371–1390. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR 1757964, DOI https://doi.org/10.1063/1.533200
- Q. I. Rahman and G. Schmeisser, Analytic theory of polynomials, London Mathematical Society Monographs. New Series, vol. 26, The Clarendon Press, Oxford University Press, Oxford, 2002. MR 1954841 rota G.-C. Rota, D. Sharp, Mathematics, Philosophy, and Artificial Intelligence: a Dialogue with Gian-Carlo Rota and David Sharp, Los Alamos Science, Spring/Summer 1985. semple-welsh C. Semple, D. J. A. Welsh, Negative correlation in graphs and matroids, Combin. Prob. Comput. 15 (2006), 765–781.
- P. D. Seymour and D. J. A. Welsh, Combinatorial applications of an inequality from statistical mechanics, Math. Proc. Cambridge Philos. Soc. 77 (1975), 485–495. MR 376378, DOI https://doi.org/10.1017/S0305004100051306
- Alan D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 173–226. MR 2187739, DOI https://doi.org/10.1017/CBO9780511734885.009
- G. Szegö, Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen, Math. Z. 13 (1922), no. 1, 28–55 (German). MR 1544526, DOI https://doi.org/10.1007/BF01485280 W D. G. Wagner, Negatively correlated random variables and Mason’s conjecture for independent sets in matroids, Ann. Combin. 12 (2008), 211–239.
- David G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2004/06), no. 2, Article 1, 17. MR 2195432
- J. L. Walsh, On the location of the roots of certain types of polynomials, Trans. Amer. Math. Soc. 24 (1922), no. 3, 163–180. MR 1501220, DOI https://doi.org/10.1090/S0002-9947-1922-1501220-0
Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 62H20, 05B35, 15A15, 15A22, 15A48, 26C10, 30C15, 32A60, 60C05, 60D05, 60E05, 60E15, 60G55, 60K35, 82B31
Retrieve articles in all journals with MSC (2000): 62H20, 05B35, 15A15, 15A22, 15A48, 26C10, 30C15, 32A60, 60C05, 60D05, 60E05, 60E15, 60G55, 60K35, 82B31
Additional Information
Julius Borcea
Affiliation:
Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden
Email:
julius@math.su.se
Petter Brändén
Affiliation:
Department of Mathematics, Royal Institute of Technology, SE-100 44 Stockholm, Sweden
MR Author ID:
721471
Email:
pbranden@math.kth.se
Thomas M. Liggett
Affiliation:
Department of Mathematics, University of California, Los Angeles, California 90095-1555
Email:
tml@math.ucla.edu
Keywords:
Negative association,
stable polynomials,
hyperbolic polynomials,
determinants,
matrices,
spanning trees,
matroids,
probability measures,
stochastic domination,
interacting particle systems,
exclusion processes
Received by editor(s):
July 17, 2007
Published electronically:
September 19, 2008
Article copyright:
© Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.