0
$\begingroup$

Is there any reasonable upper bound for the following quantity $$ \sum_{k=1}^T \frac{1}{k (1+a)^{T-k}} $$

where $a>0$ with respect to $T$ and $a$ (something like $\mathcal{O}(\frac{\log (T)}{aT}$)? I tried to compute integral $$ \int_{0}^T \frac{1}{x (1+a)^{T-x}}dx, $$ which should be upper bound on this sum as $f(x) = \frac{1}{x (1+a)^{T-x}}$ is decreasing on $(0, T)$, but I did not achieve to get reasonable expression.

$\endgroup$

2 Answers 2

4
$\begingroup$

Changing variables to $n=T-k$, and letting $x=1+a$, we can write the sum as $$ S=\sum_{n=0}^{T-1}\frac{x^{-n}}{T-n}=\frac{1}{T}+\frac{x^{-1}}{T-1}+\frac{x^{-2}}{T-2}+\cdots+\frac{x^{1-T}}{1}. $$ Recognizing that the right side of $$ Sx^T=x+\frac{x^2}{2}+\cdots +\frac{x^T}{T} $$ would be the $T^{th}$ Taylor polynomial of $-\log(1-x)$, except for the annoying fact that $x>1$ so the Taylor series does not converge here.

Instead, the series behavior geometrically and is dominated by its last few terms. One way to obtain a somewhat reasonable and explicit upperbound is by keeping the last term and decreasing the denominators of all other terms to $1$, then summing the geometric series to obtain $$ Sx^T\leq x+x^2+\cdots+x^{T-1}+\frac{x^T}{T}=\frac{x^T-1}{x-1}-1+\frac{x^T}{T}, $$ showing that $$ S\leq \frac{1}{a}(1-(1+a)^{-T})-1+\frac{1}{T}. $$ To gauge how tight of an upper bound this is would require knowing how $a$ compares to $1$, and different procedures could be used in the regimes when $a$ is very close to $0$ vs when $a$ is much larger than $1$.

$\endgroup$
2
$\begingroup$

Here is a fairly loose upper bound. (I wrote this for the cross validated posting and am copying it here since that one was deleted.)

$$ \begin{aligned} \sum_{k=1}^T\frac{1}{k(1+a)^{T-k}} &= (1+a)^{-T} \sum_{k=1}^T\frac{(1+a)^k}{k} \\ &\le (1+a)^{-T} \sum_{k=1}^T(1+a)^k \\ &= (1+a)^{-T} \frac{(1-(1+a)^{T+1})}{1-(1+a)}\\ &= \frac{1}{a}(1+a)^{-T} \left((1+a)^{T+1}-1\right)\\ &= \frac{1}{a}\left((1+a)-(1+a)^{-T}\right)\\ \end{aligned} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .