Abstract
We prove conditional negative association for random variables xj = 1**math-image** (j∈[n]:= {1…n}), where σ(1)…σ(m) are i.i.d. from [n]. (The σ(i) 's are thought of as the locations of balls dropped independently into urns 1…n according to some common distribution, so that, for some threshold tj, xj is the indicator of the event that at least tj balls land in urn j.) We mostly deal with the more general situation in which the σ(i) 's need not be identically distributed, proving results which imply conditional negative association in the i.i.d. case. Some of the results—particularly Lemma 8 on graph orientations—are thought to be of independent interest. We also give a counterexample to a negative correlation conjecture of D. Welsh, a strong version of a (still open) conjecture of G. Farr. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.
References
[1]
J. Borcea, P. Brändén, T. M. Liggett, Negative dependence and the geometry of polynomials, J Am Math Soc 22 (2009), 521–567.
[2]
F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: An update, Contemporary Math 178 (1994), 71–89.
[3]
Y. Choe, D. Wagner, Rayleigh Matroids, Combin Probab Comput 15 (2006), 765–781.
[4]
P. Doyle, J. L. Snell, Random walks and electric networks, Carus Mathematical Monographs 22 (1984).
[5]
D. Dubhashi, D. Ranjan, Balls and bins: A study in negative dependence, Random Struct & Algorithms 13 (1998), 99––124.
[6]
T. Feder, M. Mihail, Balanced matroids, In Proceedings of the 24th STOC, ACM, Victoria, BC, 1992, pp. 26–38.
[7]
G. H. Hardy, J. E. Littlewood, G. Pólya, Inequalities, 2nd edition, Cambridge University Press, Cambridge, 1952.
[8]
O. J. Heilman, E. H. Lieb, Monomers and dimers, Phys Rev Lett 24 (1970), 1412–1414.
[9]
O. J. Heilman, E. H. Lieb, Theory of monomer-dimer systems, Comm Math Phys 25 (1972), 190–232.
[10]
J. Kahn, M. Neiman, Negative correlation and log-concavity, Random Struct Algorithms, (in press).
[11]
J. Kahn, M. Neiman, A strong log-concavity property for measures on Boolean algebras, J Combinatorial Th (A) 118 (2011), 1749–1760.
[12]
H. Kunz, Location of the zeros of the partition function for some classical lattice systems, Phys Lett (A) 32A (1970), 311–312.
[13]
L. Lovász, M. D. Plummer, Matching theory, North Holland, Amsterdam, 1986.
[14]
M. Neiman, Negative Correlation and Log-concavity, Ph.D. Thesis, Rutgers University, 2009.
[15]
R. Pemantle, Towards a theory of negative dependence, J Math Phys 41 (2000), 1371–1390.
[16]
R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986), Ann New York Acad Sci 576 (1986), 500–535.
[17]
D. Wagner, Negatively correlated random variables and Mason's conjecture for independent sets in matroids, Ann Comb 12 (2008), 211–239.
[18]
D. Welsh, Harris's inequality and its descendents, Lecture at Isaac Newton Institute (June 2008). Available at
Recommendations
Negative correlation and log-concavity
We give counterexamples and a few positive results related to several conjectures of R. Pemantle (Pemantle, J Math Phys 41 (2000), 1371–1390) and D. Wagner (Wagner, Ann Combin 12 (2008), 211–239) concerning negative correlation and log-concavity ...
A generalized Conway-Maxwell-Poisson distribution which includes the negative binomial distribution
The Conway-Maxwell-Poisson (COM-Poisson) distribution with two parameters was originally developed as a solution to handling queueing systems with state-dependent arrival or service rates. This distribution generalizes the Poisson distribution by adding ...
Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures
Sufficient conditions are developed, under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. Recently, one of the authors [O.T. Johnson, Log-concavity and the maximum ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 September 2012
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Dec 2024