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.

  • $\begingroup$ Even verifying the $n=2$ case is nontrivial. $\endgroup$ – Aryeh Kontorovich Apr 5 '11 at 18:38
  • 1
    $\begingroup$ The conjecture fails if $t$ isn't forced to be an integer: $p=q=t-1=1/n=1/2$. Perhaps, though, it's true for nonintegral $t\geq2$. $\endgroup$ – Kevin O'Bryant Apr 5 '11 at 19:00

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.

  • $\begingroup$ This concave majorants trick is very nice. I will have to keep an eye out for where else I can use it. $\endgroup$ – David E Speyer Apr 7 '11 at 3:10

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.

  • 11
    $\begingroup$ I'm not sure I agree with your first sentence. Not everyone gets the same exposure to Olympiadity that all you Bears of Great Brain do... :) $\endgroup$ – Yemon Choi Apr 5 '11 at 19:29
  • 2
    $\begingroup$ That said, I really like the answer/solution/sketch you've given $\endgroup$ – Yemon Choi Apr 5 '11 at 20:08
  • 12
    $\begingroup$ -1 for the first sentence (I didn't actually vote down). Even if you think it's an easy question, what is the purpose of this sentence other than embarrassing the poster? $\endgroup$ – Ori Gurel-Gurevich Apr 5 '11 at 22:28

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.