Show that the derivative of this function is positive

Question

Suppose that $n>1$, $g\in(0,1)$ and $f(g)\in(0,1)$. Suppose that $\frac{df(g)}{dg}\geq0$.

Define $B(g,n)$ as:

$B(g,n)=\sum _{k=1}^n \frac{n!}{k!(n-k)!}g^{n-k}(1-g)^{k-1}(1-(1-f(g))^k)$

Show that:

$\frac{dB(g,n)}{dg}>0$.

Some of these assumptions can be relaxed (for example the $\frac{df(g)}{dg}\geq0$ I suspect), but I am not especially interested in that.

What I have done:

1. I have shown that this is the case for $n=2$, $n=3$ and $n=4$, but did not find any pattern that helped me generalize to $n$.

2. I took the derivative with Mathematica and obtained that little monster: $ \frac{dB(g,n)}{dg}=-\frac{g^n \left(-n \left(\frac{(g-1) f(g)+1}{g}\right)^{n-1} \left(\frac{(g-1) f'(g)+f(g)}{g}-\frac{(g-1) f(g)+1}{g^2}\right)-n \left(\frac{1}{g}\right)^{n+1}\right)}{g-1}-\frac{n g^{n-1} \left(\left(\frac{1}{g}\right)^n-\left(\frac{(g-1) f(g)+1}{g}\right)^n\right)}{g-1}+\frac{g^n \left(\left(\frac{1}{g}\right)^n-\left(\frac{(g-1) f(g)+1}{g}\right)^n\right)}{(g-1)^2}$.

3. (Here I might be wrong) I think that the problem can be slightly simplified by assuming that $\frac{df(g)}{dg}=0$. Because assuming $\frac{df(g)}{dg}>0$ only "helps us" in proving the that the derivative is positive, then it suffices to show that our desired result holds when $\frac{df(g)}{dg}=0$.

Thanks in advance!

Answer 1

Thanks to all (including those who helped in Pure algebra: Show that this expression is positive) we have shown the result. I will summarize it for those who can be interested.

Note that $B(g,n)$ simplifies to

$B(g,n)=\sum _{k=1}^n \frac{n!}{k!(n-k)!}g^{n-k}(1-g)^{k-1}(1-(1-f(g))^k)=\frac{-1+(1-f(g)+gf(g))^n}{-1+g}$.

Hence

$\frac{dB(g,n)}{dg}=\frac{(g-1)n(g-(g-1)(1-f(g)))^{n-1}(f(g)+(g-1)f'(g))-((g-(g-1)(1-f(g)))^n-1)}{(g-1)^2}$.

Because $\frac{dB(g,n)}{dg}$ is increasing in $f'(g)$, and we have assumed that $f'(g)\geq0$, we can can now set $f'(g)=0$. This simplifies the previous derivative to

$\frac{dB(g,n)}{dg}=\frac{1-(1-g)nf(g)(1-(1-g)f(g))^{n-1}-(1-(1-g)f(g))^n}{(g-1)^2}.$

We want to show that this derivative is positive. To do so, set $t=1-(1-g)f(g)$ in the previous expression and eliminate the (positive) denominator. Now we need to show that

$f_n(t):= 1-n(1-t)t^{n-1}+t^n=1-nt^{n-1}+(n+1)t^n>0$.

Note that

$f'_n(t)=-n(n-1)t^{n-2}+n(n+1)t^{n-1}$,

where $t_0=0$ and $t_n=\frac{n-1}{n+1}$ make $f'_n(t)=0$. Since $f''_n(t_n)>0$, we conclude that $t_n$ is a minimum.

Now remains to show that $f_t(t_n)>0$.

$f_t(t_n)=1-n(\frac{n-1}{n+1})^{n-1}+(n+1)(\frac{n-1}{n+1})^{n}=1-(\frac{n-1}{n+1})^{n-1}>0$.

Thanks to everyone who contributed!

Answer 2

Note: I am in the process of simplifying and correcting this answer. I realized some more stuff was wrong.

$B(g,n)=\sum _{k=1}^n \frac{n!}{k!(n-k)!}g^{n-k}(1-g)^{k-1}(1-(1-f(g))^k) $

Now let $X_g(k) = 1 - (1 - f(g))^k$
$B(g,n)= (1-g)^{-1}\sum _{k=1}^n \frac{n!}{k!(n-k)!}g^{n}(1-g)^{k-1}X_g(k)$

$X_g(0) = 0$ so we can expand the summation limit to include $i=0$ $B(g,n) = (1-g)^{-1}\sum _{k=0}^n \frac{n!}{k!(n-k)!}g^{n}(1-g)^{k-1}X_g(k)$

Using $X_g(0) = 0$ we can include $0$ in the summation indices
$B(g,n) =(1-g)^{-1}\sum _{k=0}^n \frac{n!}{k!(n-k)!}g^{n-k}(1-g)^{k}X_g(k) $

Notation: Let the random variable $K_{a,b}$ be the result of tossing $b$ independent coins with $P(\text{heads}) = a$ and counting the number of heads. (This is called a binomial random variable with parameters $(a, b)$). Reinterpret $B(g,n)$ as an expression about expected value involving the binomial random variable $K_{1-g,n}$.

$B(g,n) =(1-g)^{-1}\mathbb{E}[X_g(K_{1-g,n})]$
$ =(1-g)^{-1}\mathbb{E}[1 - (1 - f(g))^{K_{1-g,n}}]$
$ =(1-g)^{-1}(\mathbb{E}[1] - \mathbb{E}[(1 - f(g))^{K_{1-g,n}}])$
$ =(1-g)^{-1}(1 - \mathbb{E}[(1 - f(g))^{K_{1-g,n}}])$

Now decompose $K_{1-g,n}$ as the sum of $n$ independent coin tosses $K_{1-g,n} = Y_{1-g}^{(1)} + Y_{1-g}^{(2)} + ... Y_{1-g}^{(n)}$ where $Y_{1-g}^{(i)}$ is the $i$th independent coin which takes $1$ with probability $1-g$ and $0$ with probability $g$.

$B(g,n) =(1-g)^{-1}(1 - \mathbb{E}[(1 - f(g))^{\sum_{i=1}^nY_{1-g}^{(i)}}])$
$ =(1-g)^{-1}(1 - \mathbb{E}[\prod_{i=1}^n(1 - f(g))^{Y_{1-g}^{(i)}}])$

Expectation distributes over products when random variables are independent. $B(g,n) =(1-g)^{-1}(1 - \prod_{i=1}^n\mathbb{E}[(1 - f(g))^{Y_{1-g}^{(i)}}])$
$ =(1-g)^{-1}(1 - \prod_{i=1}^n\mathbb{E}[(1 - f(g))^{Y_{1-g}^{(1)}}])$
$ =(1-g)^{-1}(1 - \mathbb{E}[(1 - f(g))^{Y_{1-g}^{(1)}}]^n)$

It is easy to calculate $\mathbb{E}[(1 - f(g))^{Y_{1-g}^{(1)}}]$ since the two cases are $Y_{1-g}^{(1)} = 0$ and $Y_{1-g}^{(1)} = 0$.
$\mathbb{E}[(1 - f(g))^{Y_{1-g}^{(1)}}] $ $= P(Y_{1-g}^{(1)} = 0)(1 - f(g))^0 + P(Y_{1-g}^{(1)} = 1)(1 - f(g))^1$
$ = g + (1-g)(1-f(g))$
$ = g + 1 - f(g) - g + gf(g)$
$ = 1 - f(g) + gf(g)$

Then substituting we have
$B(g,n) =(1-g)^{-1}(1 - (1 - f(g) + gf(g))^n)$

Remember that to prove $\frac{dB}{dg}(g,n) \ge 0$, we only need to show $B(g,n)$ is nondecreasing in $g$. Equivalently, we can show $\log B(g,n)$ is nondecreasing in $g$.

$\log B(g,n) = -\log(1-g) + \log(1 - (1-f(g) + gf(g))^n)$

We can use the power series expansion $-\log(1-x) = \sum_{j=1}^\infty x^j/j$ on both $\log$ terms. You can see there are no issues of divergence by verifying $g \in (0,1)$ and $(1-f(g) + gf(g))^n \in (0,1)$

$\log B(g,n) = \sum_{j=1}^\infty g^j/j - \sum_{j=1}^\infty(1-f(g) + gf(g))^{nj}/j$
$= \sum_{j=1}^\infty \frac{[ g^j - (1-f(g) + gf(g))^{nj}]}{j}$

Answer 3

This is not a full solution, but some possibly helpful thoughts too long to fit a comment.

Notice that

$$B(g,n) = \sum _{k=1} ^n \frac {n!} {k!(n-k)!} g^{n-k} (1-g)^{k-1} - \sum _{k=1} ^n \frac {n!} {k!(n-k)!} g^{n-k} (1-g)^{k-1} (1-f(g))^k = \\ \frac 1 {1-g} \sum _{k=1} ^n \frac {n!} {k!(n-k)!} g^{n-k} (1-g)^k - \frac 1 {1-g} \sum _{k=1} ^n \frac {n!} {k!(n-k)!} g^{n-k} (1-g)^k (1-f(g))^k = \\ \frac 1 {1-g} \{ [g + (1-g)]^n - 1 \} - \frac 1 {1-g} \{ [g + (1-g)(1-f(g))]^n - 1 \} = \\ \frac 1 {g-1} \{ [g - (g-1)(1-f(g))]^n - 1 \} \ ,$$

whence

$$\frac {\Bbb d B(g,n)} {\Bbb d g} = \frac { \{n [g - (g-1)(1-f(g))]^{n-1} [1 - (1-f(g)) + (g-1) f'(g)] \} (g-1)} {(g-1)^2} - \frac {\{ [g - (g-1)(1-f(g))]^n - 1 \}} {(g-1)^2} = \\ \frac {\Bbb d B(g,n)} {\Bbb d g} = \frac { \{n [g - (g-1)(1-f(g))]^{n-1} [f(g) + (g-1) f'(g)] \} (g-1)} {(g-1)^2} - \frac {\{ [g - (g-1)(1-f(g))]^n - 1 \}} {(g-1)^2} \ .$$

Since the denominator is positive, you have then to show that

$$\{n [g - (g-1)(1-f(g))]^{n-1} [f(g) + (g-1) f'(g)] \} (g-1) - \{ [g - (g-1)(1-f(g))]^n - 1 \} \ge 0 \ .$$

Notice that

$$g - (g-1)(1-f(g)) = 1 + (g-1)f(g) < 1 \ ,$$

whence it follows that

$$- \{ [g - (g-1)(1-f(g))]^n - 1 \} \ge 0 \ .$$

and that

$$n [g - (g-1)(1-f(g))]^{n-1} \to 0 \ ,$$

so that $\lim \limits _{n \to \infty} \dfrac {\Bbb d B} {\Bbb d g} \ge 0$. Unfortunately, it is not clear whether this limit is uniform.

It also follows that a sufficient (but not necessary) condition to get the desired conclusion is $f + (g-1)f' \le 0$.