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?

  • $\begingroup$ 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?) $\endgroup$ – Clement C. Jul 28 '16 at 1:02
  • $\begingroup$ @ClementC. Yes the definition in your paper is the one. Corrected the typo following your comment on the support, thanks. $\endgroup$ – 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

  • $\begingroup$ It's a bit late, so double-checking may be a good idea. $\endgroup$ – Clement C. Jul 29 '16 at 5:42
  • $\begingroup$ 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. $\endgroup$ – eymen Jul 29 '16 at 6:14
  • $\begingroup$ You're welcome! $\endgroup$ – Clement C. Jul 29 '16 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.