Averaged geometric series with floor function

Question

Given a value $p\in[0,1]$ (a probability of occurrence), I would like to bound the following expression:

$$ s\frac{1-(1-p)^{k+1}}{p(k+1)} + (1-s)\frac{1-(1-p)^{k}}{pk},\ \ \ \text{where $k=\lfloor 1/p \rfloor$ and $s=1/p-k$}.$$

I would like to prove that the latter is bigger than $1-e^{-1}$.

I already know that in each interval where $k$ is constant ($p\in (\frac{1}{k+1},\frac{1}{k}]$), when $p$ approaches to $1/(k+1)$, the expression is bounded by $1-e^{-1}$ from below. Therefore, if I could prove that in such interval the function is increasing in $p$, I would be done.

I've struggling a while trying to prove this (and I have also tried to prove the inequality directly), but I have failed so far.

I think this kind of expressions are not that ''unnatural'' to come out, so maybe somebody else has already studied them. However, I don't know where to look. All this work is in the context of approximation theory and optimization; I have not found similar expressions though.

Any ideas on how I could keep the work or where I should look for similar results? Thanks!

Answer 1

For a given natural $k$, let $f(p)$ denote the expression in question. We need to show that $f(p)$ is increasing in $p$. Everywhere here $p\in[\frac1{k+1},\frac1k]$. Let $$f_1(p):= f'(p) k (1 + k) (1 - p) p^3,\quad f_2(p):= f_1'(p),\quad f_3(p):= f_2'(p),$$ $$f_4(p):= \frac{f_3'(p)}{k (1 + k) (1 - p)^{k-3}} =1 + 2 k - 3 (1 + k + 4 k^2) p + (2 + k + 16 k^2 + 8 k^3) p^2 - k^2 (6 + 5 k + k^2) p^3.$$ Since $f_4(p)$ is a polynomial in $k,p$, it is not hard to see (using a computer algebra package or otherwise -- e.g., by observing that $f_4(p)$ is convex in $p$ for $k\ge2$) that $f_4(p)<0$ for all real $k\ge2$, and $f_4(p)<0$ for $k=1$ unless $p=1$. So, $f_3$ is decreasing, with \begin{equation} f_3\Big(\frac1{k+1}\Big)\frac{(1 + k)^{1 + k}}{k^k}=(1+1/k)^k (2 + 6 k + 4 k^2 ) - (3 + 9 k + 10 k^2 + 2 k^3) <e(2 + 6 k + 4 k^2 ) - (3 + 9 k + 10 k^2 + 2 k^3)<0 \end{equation} for $k\ge3$, whereas trivially $f_3(\frac1{k+1})\le0$ for $k=1,2$.

So, $f_3<0$ on $(\frac1{k+1},\frac1k]$, whence $f_2=f_1'$ is decreasing and hence its sign pattern is $+$ or $-$ or $+-$ on $[\frac1{k+1},\frac1k]$. So, $f_1(p)\ge f_1(\frac1{k+1})\wedge f_1(\frac1k)$.

But $f_1(\frac1k)k^2= (1 - 1/k)^k (3 k - 1) - (k - 1)$, so that $f_1(1/k)$ equals $g(k):=\ln[(1 - 1/k)^k]-\ln\frac{k-1}{3k-1}$ in sign. Since $g''(k)=\frac{3 k+1}{(3k-1)^2 (k-1) k}>0$ for $k>1$, the function $g$ is convex. Moreover, $g(\infty-)=\ln\frac3e\in(0,\infty)$ and hence $g'(\infty-)=0$. So, $g>0$ and hence $f_1(1/k)>0$.

Similarly, $f_1(\frac1{k + 1})\frac{(k+1)^3}k= k+1 - (2 k+1)(\frac k{k+1})^k$, so that $f_1(\frac1{k + 1})$ equals $h(k):=\ln\frac{k+1}{2k+1}-\ln[(\frac k{k+1})^k]$ in sign. Since $h''(k)=-\frac1{k (k+1) (2 k+1)^2)}<0$, the function $h$ is concave. Moreover, $h(1)=\ln\frac43>0$ and $h(\infty-)=\ln\frac e2>0$. So, $h>0$ and hence $f_1(\frac1{k + 1})>0$.

Thus, $f_1\ge f_1(\frac1{k+1})\wedge f_1(\frac1k)>0$ and $f'>0$ on $(\frac1{k+1},\frac1k)$, and hence $f$ is indeed increasing.