1
$\begingroup$

I need to show that

$\sum_{i=k^*}^K\binom{K}{i}a^{i-1}(1-a)^{K-i-1}(i-aK)>0$

given $K\geq k^*$, $0 and $K$, $k^*\in\mathbb{Z^+/1}$.

I did some computer simulation and saw that it seems correct but analytically how can I show it?

1 Answers 1

1

Us $i\binom{K}{i} = K\binom{K-1}{i-1}$ to rewrite this expression as:

$\sum_{i=k^*}^KK\binom{K-1}{i-1}a^{i-1}(1-a)^{K-i-1} - \sum_{i=k^*}^KK\binom{K}{i}a^{i}(1-a)^{K-i-1}$

Divide by the positive value $\frac{K}{1-a}$ and you want to show:

$\sum_{i=k^*}^K\binom{K-1}{i-1}a^{i-1}(1-a)^{K-i} > \sum_{i=k^*}^K\binom{K}{i}a^{i}(1-a)^{K-i}$

Now, given a coin with probability $a$ of coming up heads, the left hand side is the probability that, when tossing $K-1$ such coins, you will get at least $k^*-1$ heads.

The right hand side is the probability, if you toss $K$ such coins, that you will get at least $k^*$ heads.

But the only way to get at least $k^*$ heads in $K$ tosses is to get at least $k^*-1$ heads in the first $K-1$ tosses, so the odds of getting $k^*$ heads in $K$ tosses cannot be more than the odds of getting $k^*-1$ heads in $K-1$ tosses.

You get strict inequality because if they were equal, that means that every time you got exactly $k^*-1$ heads in the first $K-1$ tosses, you'd get a heads on the next toss. That would only be true if $a=1$ or if it was impossible to get exactly $k^*-1$ heads (in which case $a=0$ or $a=1$.)

Note, this inequality still works if $k^*=1$.

For a more explicit proof, write $\binom{K}{i} = \binom{K-1}{i-1} + \binom{K-1}{i}$. So:

$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} = \sum_{i=k^*}^K\binom{K-1}{i-1}a^i(1-a)^{K-i} + \sum_{i=k^*}^K\binom{K-1}{i}a^i(1-a)^{K-i}$

In the second sum, the term is zero when $i=K$, and therefore we get that:

$\sum_{i=k^*}^K\binom{K-1}{i}a^i(1-a)^{K-i} = \sum_{i=k^*}^{K-1}\binom{K-1}{i}a^i(1-a)^{K-i} < \sum_{i=k^*-1}^{K-1}\binom{K-1}{i}a^i(1-a)^{K-i}$

Changing variables $j=i+1$, this is:

$\sum_{j=k^*}^K\binom{K-1}{j-1}a^{j-1}(1-a)^{K-j+1} $

So we know that:

$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} < \sum_{i=k^*}^K\binom{K-1}{i-1}a^i(1-a)^{K-i} + \sum_{j=k^*}^K\binom{K-1}{j-1}a^{j-1}(1-a)^{K-j+1}$

But $a^i(1-a)^{K-i} + a^{i-1}(1-a)^{K-i+1} = a^{i-1}a^{K-i}(a + 1-a) = a^{i-1}a^{K-i}$

So we get that:

$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} < \sum_{i=k^*}^K\binom{K-1}{i-1} a^{i-1}(1-a)^{K-i}$

Which is what was to be proven. Notice, the inequality comes because we added the $i=k^*-1$ term to the sum, so that term is necessarily the difference.

  • 0
    Ah, I see it. Fixed.2012-05-01