×

zbMATH — the first resource for mathematics

Negative dependence and the geometry of polynomials. (English) Zbl 1206.62096
Summary: 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.

MSC:
62H05 Characterization and structure theory for multivariate probability distributions; copulas
62H20 Measures of association (correlation, canonical correlation, etc.)
60E05 Probability distributions: general theory
60K35 Interacting random processes; statistical mechanics type models; percolation theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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). · Zbl 0049.17201
[2] Enrique D. Andjel, A correlation inequality for the symmetric exclusion process, Ann. Probab. 16 (1988), no. 2, 717 – 721. · Zbl 0642.60105
[3] M. F. Atiyah, R. Bott, and L. Gȧrding, Lacunas for hyperbolic differential operators with constant coefficients. I, Acta Math. 124 (1970), 109 – 189. , https://doi.org/10.1007/BF02394570 M. F. Atiyah, R. Bott, and L. Gȧrding, Lacunas for hyperbolic differential operators with constant coefficients. II, Acta Math. 131 (1973), 145 – 206. · Zbl 0266.35045
[4] 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. · Zbl 0974.90015
[5] J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206 – 229. · Zbl 1189.60101
[6] Julius Borcea, Spectral order and isotonic differential operators of Laguerre-Pólya type, Ark. Mat. 44 (2006), no. 2, 211 – 240. · Zbl 1161.30004
[7] 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. · Zbl 1184.30004
[8] 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. · Zbl 1151.15013
[9] J. Borcea, P. Brändén, Multivariate Pólya-Schur classification problems in the Weyl algebra, arXiv:math/0606360. · Zbl 1196.47028
[10] J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs I. Linear operators preserving stability, arXiv:0809.0401. · Zbl 1175.47032
[11] J. Borcea, P. Brändén, The Lee-Yang and Pólya-Schur programs II. Theory of stable polynomials and applications, preprint (2008). · Zbl 1177.47041
[12] 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.
[13] Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481 – 515. · Zbl 0938.05061
[14] 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. · Zbl 0771.60002
[15] Petter Brändén, Polynomials with the half-plane property and matroid theory, Adv. Math. 216 (2007), no. 1, 302 – 320. · Zbl 1128.05014
[16] 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. · Zbl 0785.60007
[17] David Carlson, Weakly sign-symmetric matrices and some determinantal inequalities, Colloq. Math. 17 (1967), 123 – 129. · Zbl 0147.27502
[18] Seth Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 319 – 329. · Zbl 0495.05018
[19] 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. · Zbl 1054.05024
[20] Youngbin Choe and David G. Wagner, Rayleigh matroids, Combin. Probab. Comput. 15 (2006), no. 5, 765 – 781. · Zbl 1107.05023
[21] J. Brian Conrey, The Riemann hypothesis, Notices Amer. Math. Soc. 50 (2003), no. 3, 341 – 353. · Zbl 1160.11341
[22] Thomas Craven and George Csordas, Jensen polynomials and the Turán and Laguerre inequalities, Pacific J. Math. 136 (1989), no. 2, 241 – 260. · Zbl 0699.30007
[23] D. J. Daley and D. Vere-Jones, An introduction to the theory of point processes, Springer Series in Statistics, Springer-Verlag, New York, 1988. · Zbl 0657.60069
[24] Devdatt Dubhashi, Johan Jonasson, and Desh Ranjan, Positive influence and negative dependence, Combin. Probab. Comput. 16 (2007), no. 1, 29 – 41. · Zbl 1107.62041
[25] 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.
[26] Devdatt Dubhashi and Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures Algorithms 13 (1998), no. 2, 99 – 124. , https://doi.org/10.1002/(SICI)1098-2418(199809)13:23.0.CO;2-M · Zbl 0964.60503
[27] 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. · Zbl 0592.60049
[28] 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. · Zbl 0965.15022
[29] T. Feder, M. Mihail, Balanced matroids, in “Proceedings of the 24th Annual ACM (STOC)”, ACM Press, New York, 1992.
[30] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre, Correlation inequalities on some partially ordered sets, Comm. Math. Phys. 22 (1971), 89 – 103. · Zbl 0346.06011
[31] F. R. Gantmacher, M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, Gostechizdat, 1950. · Zbl 0088.25103
[32] J. H. Grace, The zeros of a polynomial, Proc. Cambridge Philos. Soc. 11 (1902), 352-357. · JFM 33.0121.04
[33] Geoffrey Grimmett, The random-cluster model, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. · Zbl 1122.60087
[34] L. Gurvits, A proof of hyperbolic van der Waerden conjecture: the right generalization is the ultimate simplification, arXiv:math/0504397.
[35] 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. · Zbl 1301.90071
[36] Osman Güler, Hyperbolic polynomials and interior point methods for convex programming, Math. Oper. Res. 22 (1997), no. 2, 350 – 377. · Zbl 0883.90099
[37] Lars Gȧrding, An inequality for hyperbolic polynomials, J. Math. Mech. 8 (1959), 957 – 965. · Zbl 0090.01603
[38] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988. Reprint of the 1952 edition. · Zbl 0634.26008
[39] Olga Holtz, \?-matrices satisfy Newton’s inequalities, Proc. Amer. Math. Soc. 133 (2005), no. 3, 711 – 717. · Zbl 1067.15018
[40] Olga Holtz and Hans Schneider, Open problems on GKK \?-matrices, Linear Algebra Appl. 345 (2002), 263 – 267. · Zbl 1160.15305
[41] Olga Holtz and Bernd Sturmfels, Hyperdeterminantal relations among symmetric principal minors, J. Algebra 316 (2007), no. 2, 634 – 648. · Zbl 1130.15005
[42] Olle Häggström, Random-cluster measures and uniform spanning trees, Stochastic Process. Appl. 59 (1995), no. 2, 267 – 275. · Zbl 0840.60089
[43] Lars Hörmander, Notions of convexity, Progress in Mathematics, vol. 127, Birkhäuser Boston, Inc., Boston, MA, 1994. · Zbl 0835.32001
[44] Gordon James, Charles Johnson, and Stephen Pierce, Generalized matrix function inequalities on \?-matrices, J. London Math. Soc. (2) 57 (1998), no. 3, 562 – 582. · Zbl 0930.15022
[45] Kumar Joag-Dev and Frank Proschan, Negative association of random variables, with applications, Ann. Statist. 11 (1983), no. 1, 286 – 295. · Zbl 0508.62041
[46] Kurt Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), no. 1, 259 – 296. · Zbl 0984.15020
[47] Kurt Johansson, Determinantal processes with number variance saturation, Comm. Math. Phys. 252 (2004), no. 1-3, 111 – 148. · Zbl 1112.82036
[48] J. Kahn, M. Neiman, Negative correlation and log-concavity, arXiv:math/0712.3507. · Zbl 1211.62098
[49] Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif, 1968.
[50] 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.
[51] 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.
[52] Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. · Zbl 0559.60078
[53] Thomas M. Liggett, Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A 79 (1997), no. 2, 315 – 325. · Zbl 0888.60013
[54] 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. · Zbl 0949.60006
[55] T. M. Liggett, Negative correlations and particle systems, Markov Process. Related Fields 8 (2002), no. 4, 547 – 564. · Zbl 1021.60084
[56] T. M. Liggett, Distributional limits for the symmetric exclusion process, to appear in Stoch. Proc. Appl, arXiv:math/0710.3606. · Zbl 1172.60031
[57] Russell Lyons, Determinantal probability measures, Publ. Math. Inst. Hautes Études Sci. 98 (2003), 167 – 212. · Zbl 1055.60003
[58] R. Lyons, Y. Peres, Probability on Trees and Networks. Book in progress, web version available at http://mypage.iu.edu/ rdlyons/prbtree/prbtree.html. · Zbl 1376.05002
[59] Russell Lyons and Jeffrey E. Steif, Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J. 120 (2003), no. 3, 515 – 575. · Zbl 1068.82010
[60] Klas Markström, Negative association does not imply log-concavity of the rank sequence, J. Appl. Probab. 44 (2007), no. 4, 1119 – 1121. · Zbl 1133.62332
[61] 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. · Zbl 0437.26007
[62] 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.
[63] C. M. Newman, Normal fluctuations and the FKG inequalities, Comm. Math. Phys. 74 (1980), no. 2, 119 – 128. · Zbl 0429.60096
[64] 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. · Zbl 1009.05134
[65] 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. · Zbl 1052.62518
[66] 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. · Zbl 1072.30006
[67] 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.
[68] C. Semple, D. J. A. Welsh, Negative correlation in graphs and matroids, Combin. Prob. Comput. 15 (2006), 765-781.
[69] 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. · Zbl 0345.05004
[70] 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. · Zbl 1110.05020
[71] G. Szegö, Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen, Math. Z. 13 (1922), no. 1, 28 – 55 (German). · JFM 48.0082.02
[72] D. G. Wagner, Negatively correlated random variables and Mason’s conjecture for independent sets in matroids, Ann. Combin. 12 (2008), 211-239. · Zbl 1145.05003
[73] David G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2004/06), no. 2, Article 1, 17. · Zbl 1060.05016
[74] J. L. Walsh, On the location of the roots of certain types of polynomials, Trans. Amer. Math. Soc. 24 (1922), no. 3, 163 – 180.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.