×

Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures. (English) Zbl 1282.60016

Summary: 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, the first author [Stochastic Processes Appl. 117, No. 6, 791–802 (2007; Zbl 1115.60012)] used a semigroup approach to show that the Poisson has maximal entropy among all ultra-log-concave distributions with fixed mean.
We show via a non-trivial extension of this semigroup approach that the natural analog of the Poisson maximum entropy property remains valid if the compound Poisson distributions under consideration are log-concave, but that it fails in general. A parallel maximum entropy result is established for the family of compound binomial measures. Sufficient conditions for compound distributions to be log-concave are discussed and applications to combinatorics are examined; new bounds are derived on the entropy of the cardinality of a random independent set in a claw-free graph, and a connection is drawn to Mason’s conjecture for matroids. The present results are primarily motivated by the desire to provide an information-theoretic foundation for compound Poisson approximation and associated limit theorems, analogous to the corresponding developments for the central limit theorem and for the Poisson approximation.
Our results also demonstrate new links between some probabilistic methods and the combinatorial notions of log-concavity and ultra-log-concavity, and they add to the growing body of work exploring the applications of maximum entropy characterizations to problems in discrete mathematics.

MSC:

60E05 Probability distributions: general theory

Citations:

Zbl 1115.60012
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adelson, R. M., Compound poisson distributions, Oper. Res. Quart., 17, 73-75 (1966)
[2] Artstein, S.; Ball, K. M.; Barthe, F.; Naor, A., Solution of Shannon’s problem on the monotonicity of entropy, J. Amer. Math. Soc., 17, 4, 975-982 (2004), (electronic) · Zbl 1062.94006
[3] Barbour, A.; Chen, L.; Loh, W.-L., Compound poisson approximation for nonnegative random variables via Stein’s method, Ann. Probab., 20, 4, 1843-1866 (1992) · Zbl 0765.60015
[4] Barbour, A. D.; Johnson, O.; Kontoyiannis, I.; Madiman, M., Compound poisson approximation via information functionals, Electron. J. Probab., 15, 42, 1344-1368 (2010) · Zbl 1225.60037
[5] Barron, A. R., Entropy and the central limit theorem, Ann. Probab., 14, 1, 336-342 (1986) · Zbl 0599.60024
[6] Bobkov, S. G.; Madiman, M., The entropy per coordinate of a random vector is highly constrained under convexity conditions, IEEE Trans. Inform. Theory, 57, 8, 4940-4954 (2011) · Zbl 1365.94135
[7] Borcea, J.; Brändén, P.; Liggett, T. M., Negative dependence and the geometry of polynomials, J. Amer. Math. Soc., 22, 2, 521-567 (2009) · Zbl 1206.62096
[8] Brenti, F., Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc., 81, 413, viii+106 (1989) · Zbl 0697.05011
[9] Brightwell, G.; Tetali, P., The number of linear extensions of the boolean lattice, Order, 20, 333-345 (2003) · Zbl 1061.06001
[10] Cai, J.; Willmot, G. E., Monotonicity and aging properties of random sums, Statist. Probab. Lett., 73, 4, 381-392 (2005) · Zbl 1076.60034
[11] Chafaï, D., Binomial-poisson entropic inequalities and the \(M / M / \infty\) queue, ESAIM Probab. Statist., 10, 317-339 (2006) · Zbl 1188.60047
[13] Chudnovsky, M.; Seymour, P., The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B, 97, 3, 350-357 (2007) · Zbl 1119.05075
[14] Cover, T. M.; Thomas, J. A., (Elements of Information Theory (2006), Wiley-Interscience, John Wiley & Sons: Wiley-Interscience, John Wiley & Sons Hoboken, NJ) · Zbl 1140.94001
[15] Cover, T. M.; Zhang, Z., On the maximum entropy of the sum of two dependent random variables, IEEE Trans. Inform. Theory, 40, 4, 1244-1246 (1994) · Zbl 0811.94016
[16] de Pril, N., Recursions for convolutions of arithmetic distributions, ASTIN Bull., 15, 2, 135-139 (1985)
[17] Flajolet, P., Singularity analysis and asymptotics of Bernoulli sums, Theoret. Comput. Sci., 215, 1-2, 371-381 (1999) · Zbl 0913.68098
[18] Fortuin, C. M.; Kasteleyn, P. W.; Ginibre, J., Correlation inequalities on some partially ordered sets, Comm. Math. Phys., 22, 89-103 (1971) · Zbl 0346.06011
[19] Gnedenko, B. V.; Korolev, V. Y., Random Summation: Limit Theorems and Applications (1996), CRC Press: CRC Press Boca Raton, Florida · Zbl 0857.60002
[20] Gurvits, L., A short proof, based on mixed volumes, of Liggett’s theorem on the convolution of ultra-logconcave sequences, Electron. J. Combin., 16, 1, 5 (2009), Note: 5 · Zbl 1159.05054
[21] Hamidoune, Y. O., On the numbers of independent \(k\)-sets in a claw free graph, J. Combin. Theory Ser. B, 50, 2, 241-244 (1990) · Zbl 0743.05029
[22] Hansen, B. G., On log-concave and log-convex infinitely divisible sequences and densities, Ann. Probab., 16, 4, 1832-1839 (1988) · Zbl 0659.60030
[23] Harremoës, P., Binomial and poisson distributions as maximum entropy distributions, IEEE Trans. Inform. Theory, 47, 5, 2039-2041 (2001) · Zbl 0999.94012
[25] Harris, T. E., A lower bound for the critical probability in a certain percolation process, Proc. Cambridge Philos. Soc., 56, 13-20 (1960) · Zbl 0122.36403
[27] Jacquet, P.; Szpankowski, W., Entropy computations via analytic de-poissonization, IEEE Trans. Inform. Theory, 45, 4, 1072-1081 (1999) · Zbl 0959.94009
[28] Johnson, O. T., Information Theory and the Central Limit Theorem (2004), Imperial College Press: Imperial College Press London
[29] Johnson, O. T., Log-concavity and the maximum entropy property of the poisson distribution, Stochastic Process. Appl., 117, 6, 791-802 (2007) · Zbl 1115.60012
[30] Johnson, O. T.; Goldschmidt, C. A., Preservation of log-concavity on summation, ESAIM Probab. Statist., 10, 206-215 (2006) · Zbl 1185.60016
[32] Kahn, J., Entropy, independent sets and antichains: a new approach to Dedekind’s problem, Proc. Amer. Math. Soc., 130, 2, 371-378 (2001) · Zbl 0982.05014
[33] Kahn, J.; Neiman, M., Negative correlation and log-concavity, Random Struct. Algorithms, 37, 3, 367-388 (2010) · Zbl 1211.62098
[34] Kahn, J.; Neiman, M., A strong log-concavity property for measures on Boolean algebras, J. Combin. Theory Ser. A, 118, 6, 1749-1760 (2011) · Zbl 1227.60005
[35] Karlin, S., Total Positivity., vol. I (1968), Stanford University Press: Stanford University Press Stanford, Calif · Zbl 0219.47030
[36] Katti, S. K., Infinite divisibility of integer-valued random variables, Ann. Math. Statist., 38, 1306-1308 (1967) · Zbl 0158.17004
[37] Keilson, J.; Gerber, H., Some results for discrete unimodality, J. Amer. Statist. Assoc., 66, 334, 386-389 (1971) · Zbl 0236.60017
[38] Keilson, J.; Sumita, U., Uniform stochastic ordering and related inequalities, Canad. J. Statist., 10, 3, 181-198 (1982) · Zbl 0516.60063
[39] Kleitman, D. J., Families of non-disjoint subsets, J. Combin. Theory, 1, 153-155 (1966) · Zbl 0141.00801
[40] Kleitman, D.; Markowsky, G., On Dedekind’s problem: the number of isotone Boolean functions. II, Trans. Amer. Math. Soc., 213, 373-390 (1975) · Zbl 0321.05010
[41] Knessl, C., Integral representations and asymptotic expansions for Shannon and Renyi entropies, Appl. Math. Lett., 11, 2, 69-74 (1998) · Zbl 1337.94007
[42] Kontoyiannis, I.; Harremoës, P.; Johnson, O. T., Entropy and the law of small numbers, IEEE Trans. Inform. Theory, 51, 2, 466-472 (2005) · Zbl 1297.94016
[44] Liggett, T. M., Ultra logconcave sequences and negative dependence, J. Combin. Theory Ser. A, 79, 2, 315-325 (1997) · Zbl 0888.60013
[45] Madiman, M.; Barron, A., Generalized entropy power inequalities and monotonicity properties of information, IEEE Trans. Inform. Theory, 53, 7, 2317-2329 (2007) · Zbl 1326.94034
[47] Mason, J. H., Matroids: unimodal conjectures and Motzkin’s theorem, (Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) (1972), Inst. Math. Appl.: Inst. Math. Appl. Southend), 207-220
[48] Mateev, P., The entropy of the multinomial distribution, Teor. Verojatnost. i Primenen., 23, 1, 196-198 (1978) · Zbl 0388.60015
[49] Panjer, H. H., Recursive evaluation of a family of compound distributions, Astin Bull., 12, 1, 22-26 (1981)
[50] Pemantle, R., Towards a theory of negative dependence, J. Math. Phys., 41, 3, 1371-1390 (2000) · Zbl 1052.62518
[51] Penrose, M., (Random Geometric Graphs. Random Geometric Graphs, Oxford Studies in Probability, vol. 5 (2003), Oxford University Press: Oxford University Press Oxford) · Zbl 1029.60007
[52] Radhakrishnan, J., An entropy proof of Bregman’s theorem, J. Combin. Theory, Ser. A, 77, 161-164 (1997) · Zbl 0894.15007
[53] Sha, J. C.; Kleitman, D. J., The number of linear extensions of subset ordering, Ordered Sets (Oberwolfach, 1985). Ordered Sets (Oberwolfach, 1985), Discrete Math., 63, 2-3, 271-278 (1987), (special issue) · Zbl 0647.05003
[54] Shepp, L. A.; Olkin, I., Entropy of the sum of independent Bernoulli random variables and of the multinomial distribution, (Contributions to Probability (1981), Academic Press: Academic Press New York), 201-206 · Zbl 0534.60020
[55] Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, (Graph Theory and its Applications: East and West (Jinan, 1986). Graph Theory and its Applications: East and West (Jinan, 1986), Ann. New York Acad. Sci., vol. 576 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 500-535 · Zbl 0792.05008
[56] Steutel, F. W.; van Harn, K., Discrete analogues of self-decomposability and stability, Ann. Probab., 7, 5, 893-899 (1979) · Zbl 0418.60020
[57] Tulino, A.; Verdú, S., Monotonic decrease of the non-Gaussianness of the sum of independent random variables: a simple proof, IEEE Trans. Inform. Theory, 52, 9, 4295-4297 (2006) · Zbl 1320.60111
[58] Wagner, D. G., Negatively correlated random variables and Mason’s conjecture for independent sets in matroids, Ann. Comb., 12, 2, 211-239 (2008) · Zbl 1145.05003
[59] Wang, Y.; Yeh, Y.-N., Log-concavity and LC-positivity, J. Combin. Theory Ser. A, 114, 2, 195-210 (2007) · Zbl 1109.11019
[60] Yu, Y., On the entropy of compound distributions on nonnegative integers, IEEE Trans. Inform. Theory, 55, 8, 3645-3650 (2009) · Zbl 1367.94142
[61] Zhao, C. K., A conjecture on matroids, Neimenggu Daxue Xuebao, 16, 3, 321-326 (1985) · Zbl 1333.05070
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.