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

279 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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