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](https://mathoverflow.net/questions/60418/missing-mass-estimate); 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.



Missing mass conjecture
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. 


