Negative dependence and the geometry of polynomials

Borcea, Julius; Brändén, Petter; Liggett, Thomas

doi:10.1090/S0894-0347-08-00618-8

Negative dependence and the geometry of polynomials
HTML articles powered by AMS MathViewer

by Julius Borcea, Petter Brändén and Thomas M. Liggett

J. Amer. Math. Soc. 22 (2009), 521-567

DOI: https://doi.org/10.1090/S0894-0347-08-00618-8

Published electronically: September 19, 2008

PDF | Request permission

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.

References

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 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 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 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 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 10.1007/s11512-006-0017-6

Pólya-Schur master theorems for circular domains and their boundaries

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 10.1215/00127094-2008-018

Multivariate Pólya-Schur classification problems in the Weyl algebra

The Lee-Yang and Pólya-Schur programs I. Linear operators preserving stability

The Lee-Yang and Pólya-Schur programs II. Theory of stable polynomials and applications

Pólya-Schur-Lax problems: hyperbolicity and stability preservers

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 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 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 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 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 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 10.1016/S0196-8858(03)00078-2
Youngbin Choe and David G. Wagner, Rayleigh matroids, Combin. Probab. Comput. 15 (2006), no. 5, 765–781. MR 2248326, DOI 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, DOI 10.2140/pjm.1989.136.241
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 10.1017/S0963548306007772

Negative Dependence Through the FKG Inequality

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 10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-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, DOI 10.1002/9780470316658
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 10.1090/conm/259/04095

Balanced matroids

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, DOI 10.1007/BF01651330

Oscillation matrices and kernels and small vibrations of mechanical systems

The zeros of a polynomial

11

Geoffrey Grimmett, The random-cluster model, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. MR 2243761, DOI 10.1007/978-3-540-32891-9

A proof of hyperbolic van der Waerden conjecture: the right generalization is the ultimate simplification

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 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 10.1287/moor.22.2.350
Lars Gȧrding, An inequality for hyperbolic polynomials, J. Math. Mech. 8 (1959), 957–965. MR 0113978, DOI 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 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 10.1016/S0024-3795(01)00492-X
Olga Holtz and Bernd Sturmfels, Hyperdeterminantal relations among symmetric principal minors, J. Algebra 316 (2007), no. 2, 634–648. MR 2358606, DOI 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 10.1016/0304-4149(95)00042-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 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 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 10.2307/2661375
Kurt Johansson, Determinantal processes with number variance saturation, Comm. Math. Phys. 252 (2004), no. 1-3, 111–148. MR 2103906, DOI 10.1007/s00220-004-1186-4

Negative correlation and log-concavity

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, DOI 10.1007/BF01213009
Thomas M. Liggett, Interacting particle systems, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231, DOI 10.1007/978-1-4613-8542-4
Thomas M. Liggett, Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A 79 (1997), no. 2, 315–325. MR 1462561, DOI 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, DOI 10.1007/978-3-662-03990-8
T. M. Liggett, Negative correlations and particle systems, Markov Process. Related Fields 8 (2002), no. 4, 547–564. MR 1957219

Distributional limits for the symmetric exclusion process

Russell Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167–212. MR 2031202, DOI 10.1007/s10240-003-0016-0

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 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 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, DOI 10.1007/BF01197754
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 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 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

Mathematics, Philosophy, and Artificial Intelligence: a Dialogue with Gian-Carlo Rota and David Sharp

Negative correlation in graphs and matroids

15

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 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 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 10.1007/BF01485280

Negatively correlated random variables and Mason’s conjecture for independent sets in matroids

12

David G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2004/06), no. 2, Article 1, 17. MR 2195432, DOI 10.37236/1893
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 10.1090/S0002-9947-1922-1501220-0