2
$\begingroup$

I would like to prove that the following function, for an arbitrary integer $n$: \begin{equation} \begin{split} f(x) & =x\cdot E \ \log(1+\text{Binomial(n,x)}) \\ & = x \cdot \sum_{k=0}^{n} \log(1+k) {n \choose k}x^k (1-x)^{n-k} \end{split} \end{equation} Is convex over $[0,1]$. I was able to show that for $n=1$ and $n=2$ by double differentiation but not in the general case. I visualized the function for various $n$ and it seems convex.

Things that I've tried unsuccessfully:

  1. Proof by induction over $n$.
  2. Second derivative - it gets messy.
  3. Expressing $f$ as a polynomial with positive coefficients - not true, for example when $n=2$ the coefficient of $x^3$ is negative.
$\endgroup$
2
  • $\begingroup$ We can write $f(x)=x\log(n+1) + E\overline{X}\log \overline{X}$, with $\overline{X} =S/(n+1)$, $S\sim B(n+1,x)$. Of course, the linear term does not affect the convexity (or lack of it). This is circumstantial evidence that your conjecture is true since at least for large $n$, the CLT shows that the second term is $\simeq x\log x$, which is a convex function. $\endgroup$ Commented Mar 13 at 21:57
  • $\begingroup$ Thank you for the answer @IosifPinelis. Great solution! $\endgroup$
    – RotemBZ
    Commented Mar 16 at 22:42

1 Answer 1

2
$\begingroup$

$\newcommand\Z{\mathbb Z}\newcommand\R{\mathbb R}\newcommand\De{\Delta}$We have $$\frac{f''(x)}n=\sum_{k=0}^{n-1} h(k)\binom{n-1}k x^k(1-x)^{n-1-k}, \tag{10}\label{10}$$ where $$h(y):=y g(y-1)-2 (y+1) g(y)+(y+2) g(y+1)$$ and $g(y):=\ln(1+\max(0,y))$, so that $$h(k)\ge0 \tag{20}\label{20}$$ for all integers $k\ge0$. So, $f''\ge0$ on $[0,1]$. $\quad\Box$

Clearly, this argument will work for any function $g$ such that $k g(k-1)$ is convex in integral $k\ge0$.


Details on \eqref{10}: For all $x\in[0,1]$, $$f(x)=x(B_n g)(x),$$ where $$(B_n g)(x):=\sum_{k\in\Z} g(k)\binom nk x^k(1-x)^{n-k};$$ of course, $\binom nk=0$ and hence $g(k)\binom nk=0$ unless $k\in\{0,\dots,n\}$.

Using the identities $\binom nk k=n\binom{n-1}{k-1}$ and $\binom n{n-k}(n-k) k=n\binom{n-1}k$, for any function $g\colon\R\to\R$ and any natural $n$ we have \begin{align} (B_n g)'(x)&=\sum_{k\in\Z} g(k)\binom nk kx^{k-1}(1-x)^{n-k} \\ &-\sum_{k\in\Z} g(k)\binom nk(n-k)x^k(1-x)^{n-k-1} \\ &=n\sum_{j\in\Z} g(j+1)\binom{n-1}j x^j(1-x)^{n-1-j} \\ &-n\sum_{k\in\Z} g(k)\binom{n-1}kx^k(1-x)^{n-1-k} \\ &=n\sum_{k\in\Z} [g(k+1)-g(k)]\binom{n-1}k x^k(1-x)^{n-1-k} \\ &=n (B_{n-1}\De g)(x), \end{align} where $(\De g)(y):=g(y+1)-g(y)$. So, $(B_n g)''=n(n-1)B_{n-2}\De^2 g$ and hence \begin{align} f''(x)&=2(B_n g)'(x)+x(B_n g)''(x) \\ &=2n(B_{n-1}\De g)(x)+n(n-1)x(B_{n-2}\De^2 g)(x) \\ &=2n\sum_{k\in\Z} (\De g)(k)\binom{n-1}k x^k(1-x)^{n-1-k} \\ &+n(n-1)\sum_{j\in\Z} (\De^2 g)(j)\binom{n-2}j x^{j+1}(1-x)^{n-2-j} \\ &=2n\sum_{k\in\Z} (\De g)(k)\binom{n-1}k x^k(1-x)^{n-1-k} \\ &+n\sum_{k\in\Z} (\De^2 g)(k-1)\binom{n-1}k k x^k(1-x)^{n-1-k}, \end{align} so that \eqref{10} holds; at the last step here, we used the identity $(n-1)\binom{n-2}{k-1}=\binom{n-1}{k} k$.

Details on \eqref{20}: We have $h(0)=2\ln2>0$ and $$h(y)=y \ln y-2 (y+1) \ln(y+1)+(y+2) \ln(y+2)>0$$ for real $y\ge1$, because $t\ln t$ is convex in $t>0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .