# Reference on (discrete) log-concave probability distributions

A discrete distribution $p$ over $\mathbb{N}$ is said to be log-concave if it satisfies the following conditions:

1. The support of $p$ is a contiguous interval, i.e. $\exists a \leq b$ s.t. $p_i > 0$ iff $a\leq i \leq b$.
2. for all $i\in\mathbb{N}$, $p_i^2 \geq p_{i-1}p_{i+1}$.

(in the literature, condition (1) is sometimes forgotten). This is the discrete analogue of continuous log-concave densities, and includes many families of usual discrete distributions.

What I am looking for is a set of lecture notes, papers or more generally references that provides an exhaustive (or as comprehensive as possible) list of theorems and properties of discrete log-concave distributions. As for now, I am aware of Devroye '87 and (part of) An '97, but not much more.

• I should mention I am also interested in approximation results: e.g., if I know the support $\{a,\dots,b\}$ of an otherwise arbitrary distribution $D$, is there a "small" family of log-concave distributions $\mathcal{L}_{\epsilon,a,b}$ that is guaranteed to "cover" $D$? (in the sense that at least one element of $\mathcal{L}_{\epsilon,a,b}$ will be a good approximation of $D$ in statistical distance) I know such cover (here, proper cover) results exist for some other classes of distributions, but am not aware of any for this particular class. – Clement C. Mar 10 '15 at 15:52
• Not exhaustive in any real sense, but have you looked at J. Keilson and H. Gerber, Some Results for Discrete Unimodality, J. Amer. Stat. Assoc., vol. 66, no. 334, 386-389. – cardinal Mar 15 '15 at 16:37

There is a 67 page review from last year, Log-concavity and strong log-concavity: a review, A. Saumard, J.A. Wellner (2014):

We review and formulate results concerning log-concavity and strong-log-concavity in both discrete and continuous settings. We show how preservation of log-concavity and strongly log-concavity on $\mathbb{R}$ under convolution follows from a fundamental monotonicity result of Efron (1969). We provide a new proof of Efron’s theorem using the recent asymmetric Brascamp-Lieb inequality due to Otto and Menz (2013). Along the way we review connections between log-concavity and other areas of mathematics and statistics, including concentration of measure, log-Sobolev inequalities, convex geometry, MCMC algorithms, Laplace approximations, and machine learning.

This review contains many references, including some to older reviews and monographs. A few references are listed here, with hyperlinks:

1. A universal generator for discrete log-concave distributions, W Hörmann (1994).

2. Preservation of log-concavity on summation, O. Johnson, C. Goldschmidt (2005).

3. On the entropy and log-concavity of compound Poisson measures, O. Johnson, I. Kontoyiannis, M. Madiman (2008).

4. Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures, O. Johnson, I. Kontoyiannis, M. Madiman (2009).

5. Strong log-concavity is preserved by convolution, J.A. Wellner (2010).

6. Asymptotics of the discrete log‐concave maximum likelihood estimator and related applications, F. Balabdaoui, H. Jankowski, K. Rufibach, M. Pavlides, (2011).

• Thanks! Sadly, the actual part of the monograph that deals with the discrete setting is only 3-page long (I'm browsing the references you mention to see if there is more "meat" there). – Clement C. Mar 13 '15 at 18:29

There is a very nice 36-page review on log-concavity and unimodality in the discrete setting by Richard Stanley, published in 1989. It is titled "Log-concave and unimodal sequences in algebra, combinatorics, and geometry" and available online here: http://onlinelibrary.wiley.com/doi/10.1111/j.1749-6632.1989.tb16434.x/abstract

As one might expect from the title, this survey does not focus as much on log-concave probability distributions on the positive integers; however, there are many useful things that one can learn here in any case (imposing the requirement of the sum of the sequence being 1 if necessary).

There is also the notion of ultra-log-concavity (discussed briefly in the Saumard-Wellner survey mentioned in the previous answer); this has beautiful connections not just to probability (where it can be interpreted as relative log-concavity with respect to binomial or Poisson distributions), but also to combinatorics. For recent papers that utilize this notion, see for example: Kahn and Neiman: "A strong log-concavity property for measures on Boolean algebras", JCT(A), 2011. and Nayar and Oleszkiewicz: "Khinchine type inequalities with optimal constants via ultra log-concavity", Positivity, 2012.

J Pitman's 1997 article, https://www.stat.berkeley.edu/~pitman/453.pdf, deals with a condition slightly stronger than log concave, PF (Polya frequency), and has a lot of fascinating results and estimates.