Question

Let $n,t$ be positive integers and $p_1,p_2,\ldots,p_n$ positive numbers summing to 1. Conjecture: $$ \sum_{i=1}^n p_i (1-p_i)^t \le \frac{n(1-1/n)^n}{t} $$ always holds.

The motivation comes from my missing mass question; the quantity $\sum_{i=1}^n p_i (1-p_i)^t$ is precisely the expected unseen mass after $t$ draws from the distribution $(p_i)$ on $n$ objects.

Answer 1

Since the single-variable optimization that David mentions still requires some work, I will present another solution. Let $f(p) = p(1-p)^t$. Define the function $g$ that is equal to $f$ on $[0, 1/t]$, and on $[1/t, 1]$ is a linear interpolation between the points $(1/t, f(1/t))$ and $(1, 0)$. Then we can check that $g$ is concave on all of $[0, 1]$ and $g \ge f$ on all of $[0, 1]$. (I learned this concept of "concave majorants" or "convex minorants" from Steele's book called The Cauchy-Schwarz Master Class.) Applying Jensen's inequality, we have $\sum f(p_i) \le \sum g(p_i) \le n g(1/n)$.

We now split into two cases, $t \le n -1$ or $t \ge n$. First, suppose that $t \le n - 1$. Then $g(1/n) = f(1/n) = (1/n) (1 - 1/n)^t$. So we need to show that $(1 - 1/n)^t$ is at most $n (1 - 1/n)^n / t$. That's equivalent to showing $t(1 - 1/n)^t \le n (1 - 1/n)^n$. We can check that the left side is an increasing function of $t$ for $t \le n - 1$, and when $t = n - 1$ we have an equality. So we have established the inequality in this case.

Next suppose that $t \ge n$. Then by linear interpolation, we find $g(1/n) = (1 - 1/t)^{t-1} (1 - 1/n) / t$. So we need to show that $(1 - 1/t)^{t - 1} (n - 1) \le n(1 - 1/n)^n$. That's equivalent to $(1 - 1/t)^{t-1} \le (1 - 1/n)^{n - 1}$. By taking reciprocals, that's equivalent to $(1 + 1/(t - 1))^{t - 1} \ge (1 + 1/(n-1))^{n - 1}$. The left side is an increasing function of $t$, and we have an equality when $t = n$. So we have established the inequality in the second case too.

Answer 2

This question is borderline for appropriateness here, so I'll sketch how to proceed and omit the details. Let $f(p) = p(1-p)^t$. Notice that $$f''(p) = (1-p)^{t-2} (t(t-1) p + 2t (1-p))= t (1-p)^{t-2} ((1+t)p - 2) $$ So $f$ is concave on $[0,2/(1+t)]$ and convex on $[2/(1+t), 1]$.

Take any $(p_1, \ldots, p_n)$. If two of the $p_i$ are in the interval $(2/(1+t), 1)$, then push them apart while maintaining their sum until one of them hits the boundary of the interval. This will increase $f(p_i)$, as $f$ is convex on this interval.

Since their sum is $\leq 1$, the smaller $p_i$ will hit $2/(1+t)$ before the larger one hits $1$. Repeating this argument, we can continue to push $p_i$'s apart until at most one $p_i$ is in the interval $(2/(1+t), 1)$; call it $v$.

Now, take all the other $p_i$ besides $v$ and replace them all by their common average. Since $f$ is concave on $[0,2/(1+t)]$, this will increase $\sum f(p_i)$. (This is Jensen's inequality.) So we have reduced to one of two cases: Either there is one $p_i$, called $v$ in $[2/(1+t), 1]$, and all the others are equal to $(1-v)/(n-1)$, or else all the $p_i$ are in $[0,2/(1+t)]$, and they have value $1/n$.

You now have a single variable function to optimize, and also one other value to compare it to. I haven't done the work, but it should be tractable from here.

I learned this approach from Kiran Kedlaya's notes on inequalities. It's really a shame that there is no course in the standard curriculum which teaches this.