# Is the CMF of a log-concave PMF also log-concave?

If a PDF is log-concave, then its CDF is also log-concave. The proof I know for this uses the derivative of the log function, see Proposition 1 in this paper.

Does this also hold for discrete probability measures? I wanted to prove that it does, starting with the definition of log-concavity: let $f$ be the log-concave PMF (such as the binomial distribution) and $F$ its CMF. We want to prove

$$F^2(n) \geq F(n-1)F(n+1).$$ Then, by the definition of $F$ and assuming $F(n)>0$ on its support, we can show that this is equivalent to

$$\frac{F(n)}{F(n-1)} \geq \frac{f(n+1)}{f(n)},$$

which doesn't seem to hold in general. Am I making a mistake somehere?

• How do you define log-concavity for discrete distributions, to start with? (the definition is a bit less straightforward than in the continuous case, to avoid corner cases -- see e.g. Definition 2.2 in this paper). (Also, I assume you meant "Assuming $F(n) > 0$ on its support," i.e. with a strict inequality?) – Clement C. Jul 28 '16 at 1:02
• @ClementC. Yes the definition in your paper is the one. Corrected the typo following your comment on the support, thanks. – eymen Jul 28 '16 at 1:58

Outline of the proof: (technically, one would have to check below that the corner cases with regard to the support of $f$ (which has to be a discrete interval) are alright. Log-concavity of discrete distributions has nice corner cases. Another view is -- what is below is assuming infinite support, the actual proof would have to be restricted to the contiguous range of the support.)

Hereafter, I use the definition of log-concavity of discrete distributions as in Definition 2.2 of [1], essentially paraphrased below (specifically, the requirement that the support be an interval).

Theorem. Assume $f$ is a discrete log-concave distribution, i.e. that its support is a contiguous interval and that for all $n$ in its support, $$f(n)^2 \geq f(n+1)f(n-1). \tag{1}$$ Then $F$ is log-concave. That is, for all $n$ in the support of $f$, $$F(n)^2 \geq F(n+1)F(n-1). \tag{2}$$ Proof of the theorem.

By assumption, $f$ is log-concave, so that for all $n$ $$\frac{f(n)}{f(n-1)}\geq \frac{f(n+1)}{f(n)}$$ and by induction the positive function $n\mapsto \frac{f(n+1)}{f(n)}$ is non-increasing. Call this $(\dagger)$.

Claim 1. For all $n$, $$\frac{F(n)}{F(n-1)} \geq \frac{f(n)}{f(n-1)}.$$ Proof. \begin{align} f(n-1)F(n) - f(n)F(n-1) &= f(n-1)\sum_{k=-\infty}^{n}f(k) - f(n)\sum_{k=-\infty}^{n-1}f(k)\\ &= \sum_{k=-\infty}^{n-1} f(n-1)f(k+1) - \sum_{k=-\infty}^{n-1}f(n)f(k)\\ &= \sum_{k=-\infty}^{n-1} \left(f(n-1)f(k+1) - f(n)f(k) \right)\\ &= \sum_{k=-\infty}^{n-1} f(k)f(n-1)\underbrace{\left(\frac{f(k+1)}{f(k)} - \frac{f(n)}{f(n-1)} \right)}_{\geq 0} \tag{\dagger}\\ &\geq 0 \end{align} proving the claim. $\blacksquare$

Claim 2. (2) is equivalent to the following: $$\frac{F(n)}{F(n-1)} \geq \frac{f(n+1)}{f(n)} \tag{3}$$ for all $n$ in the support of $f$.

Proof. $(2)$ is equivalent to proving that $\frac{F(n)}{F(n-1)} - \frac{F(n+1)}{F(n)}\geq 0$ for all such $n$. We can then rewrite \begin{align} \frac{F(n)}{F(n-1)} - \frac{F(n+1)}{F(n)} &= \frac{F(n-1)+f(n)}{F(n-1)} - \frac{F(n)+f(n+1)}{F(n)}\\ &= 1+\frac{f(n)}{F(n-1)} - 1-\frac{f(n+1)}{F(n)} \\ &= \frac{f(n)}{F(n-1)} - \frac{f(n+1)}{F(n)} \\ &= \frac{f(n)}{F(n)}\left(\frac{F(n)}{F(n-1)} - \frac{f(n+1)}{f(n)}\right) \\ \end{align} and the first expression is non-negative if, and only if, the parenthesis of the last one is. This shows that $(2)$ is equivalent to $(3)$. $\blacksquare$

Combining the two claims yields the proof of the theorem. Indeed, we have that for all $n$ in the support of $f$, $$\frac{F(n)}{F(n-1)} \operatorname*{\geq}_{\rm(Claim 1)} \frac{f(n)}{f(n-1)} \operatorname*{\geq}_{(1)} \frac{f(n+1)}{f(n)}$$ using for the second inequality the assumption that $f$ is log-concave. This establishes $(3)$, which by Claim 2 is equivalent to (2). $\blacksquare$

[1] C. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing Shape Restrictions of Discrete Distributions. In 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2016. arXiv:1507.03558

• It's a bit late, so double-checking may be a good idea. – Clement C. Jul 29 '16 at 5:42
• Thanks a lot mister! Apparently I was failing to see that I could reindex the summation terms from $f(k)$ to $f(k+1)$ in the proof of Claim 1. and I had pointed out claim 2, so thanks for writing it up clearly for reference, too. – eymen Jul 29 '16 at 6:14
• You're welcome! – Clement C. Jul 29 '16 at 13:56