Behavior of $\sum_i^n (1-\frac{1}{i})^s$ as a function of $s$?

Question

I'm interested in behavior of the following sum as a function of $s$

$$\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s$$

For $n=1000$ and $s\in (1,10000)$, this seems almost linear on a log-plot (notebook), any tips how to model this analytically?

Answer 1

I assume you are interested in asymptotics. It seems you are interested in both large $s$ and large $n$. The answer will be different depending on whether $s \ll n$ or $n \ll s$.

For $s \ll n$:

Since you are taking an average of an arbitrarily large sum, asymptotically any finite number of terms will not matter. This is enough to assume that $1/i \ll 1$. This allows you to use the approximation

$$(1+x)^s \approx 1+sx$$ which is valid for small $x$. This is the tangent line approximation.

This gives

\begin{align*} \frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s &\approx \frac{1}{n}\sum_{i=1}^n \left(1-\frac{s}{i}\right) \\ &= 1 - \frac{1}{n}\sum_{i=1}^n \frac{s}{i} \end{align*}

Now use the further asymptotic approximation for the harmonic series:

$$\sum_{i=1}^n \frac{1}{i} \approx \log n$$

to get

\begin{align*} 1 - \frac{1}{n}\sum_{i=1}^n \left(\frac{s}{i}\right) &\approx 1 - \frac{s\log n}{n}. \end{align*}

For $n \ll s$:

In this case, assuming we are considering $s$ to be arbitrarily large while $n$ is fixed, we eventually have

$$(1-1/2)^s \ll (1-1/3)^s \ll (1-1/4)^s \ll \cdots \ll (1-1/n)^s.$$

In this case the first $n-1$ terms become negligible and only the last term is dominant. Then we get

$$\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s \approx \frac{1}{n} \left(1-\frac{1}{n}\right)^s$$

as $s\rightarrow \infty$.

For $0 \ll s \approx n$:

Of this I am not sure. You may need to specify more carefully the relation between $s$ and $n$.

Answer 2

Since $\forall 1\leq i\leq n,\forall s\geq0, (1-{1\over i})^s\leq (1-{1\over n})^s$, so $\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s\leq\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{n}\right)^s=(1-{1\over n})^s$, which is exponential and so will be linear on a log plot. Similarly, $(1-{1\over 2})^s\leq (1-{1\over i})^s$, so $\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s\geq \frac{1}{n}\sum_{i=2}^n \left(\frac{1}{2}\right)^s={n-1\over n}({1\over 2})^s$. Since $n$ is a constant, this is also just an exponential, so it must also be linear on a log plot. I believe that, since it is bounded between two functions that are of exponential order, that it also must be exponential order, so it also must be linear on a log plot.

This final assumption may be wrong, but I believe that it at least shows how one could model it well. Using desmos, I found the approximation $\exp(-\frac{s}{n}-\frac{\ln^{2} s}{\ln n})$, which is $O\Big(e^{s\over n}\Big)$ and only differs by about 12 for large $s$.

Answer 3

It suffices to analyze

$$ S_n=\sum_{k=2}^n\left(1-\frac1k\right)^s $$

Using generalized binomial theorem, we have

$$ S_n=\sum_{k=2}^n\left\{1-\frac sk+\mathcal O_s\left(1\over k^2\right)\right\} $$

Rearranging the terms, we get

$$ S_n=n-s\log n+\mathcal O_s(1) $$

Consequently we have

$$ \frac1n\sum_{k=1}^n\left(1-\frac1k\right)^s=1-{s\log n\over n}+\mathcal O_s\left(\frac1n\right) $$

Answer 4

I shall scale $s$ with $n$ and write $s=\alpha n$ with some $\alpha>0$. It will be assumed that $\alpha>0$ is bounded and $n$ is large. First, from the monotonicity properties of the integrand, \begin{align*} \int_1^n {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} \le \sum\limits_{i = 1}^n {\left( {1 - \frac{1}{i}} \right)^{\alpha n} } & \le \int_1^{n + 1} {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} \\ & \le \int_1^n {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} + \left( {1 - \frac{1}{{n + 1}}} \right)^{\alpha n} , \end{align*} i.e., $$ \mathop {\lim }\limits_{n \to + \infty } \frac{1}{n}\sum\limits_{i = 1}^n {\left( {1 - \frac{1}{i}} \right)^{\alpha n} } = \mathop {\lim }\limits_{n \to + \infty } \frac{1}{n}\int_1^n {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} . $$ Now we write \begin{align*} &\int_1^n {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} = \int_{1/n}^1 {\exp \left( { - \alpha n\log \left( {\frac{1}{{1 - t}}} \right)} \right)\frac{{dt}}{{t^2 }}} \\ & = \int_{1/n}^{1/n^{2/3} } {\exp \left( { - \alpha n\log \left( {\frac{1}{{1 - t}}} \right)} \right)\frac{{dt}}{{t^2 }}} + \int_{1/n^{2/3} }^1 {\exp \left( { - \alpha n\log \left( {\frac{1}{{1 - t}}} \right)} \right)\frac{{dt}}{{t^2 }}} . \end{align*} Here $$ \int_{1/n^{2/3} }^1 {\exp \left( { - \alpha n\log \left( {\frac{1}{{1 - t}}} \right)} \right)\frac{{dt}}{{t^2 }}} \le n^{2/3} \exp \left( {\alpha n\log \left( {1 - \frac{1}{{n^{2/3} }}} \right)} \right) \le n^{2/3} e^{ - \alpha n^{1/3} } , $$ and \begin{align*} & \int_{1/n}^{1/n^{2/3} } {\exp \left( { - \alpha n\log \left( {\frac{1}{{1 - t}}} \right)} \right)\frac{{dt}}{{t^2 }}} = \int_{1/n}^{1/n^{2/3} } {\exp \left( { - \alpha nt - \alpha n\mathcal{O}(t^2 )} \right)\frac{{dt}}{{t^2 }}} \\ & = \int_{1/n}^{1/n^{2/3} } {\exp \left( { - \alpha nt} \right)\frac{{dt}}{{t^2 }}} \left( {1 +\mathcal{O}\!\left( {\frac{1}{{n^{1/3} }}} \right)} \right) = n\alpha \int_\alpha ^{\alpha n^{1/3} } {e^{ - s} \frac{{ds}}{{s^2 }}} \left( {1 + \mathcal{O}\!\left( {\frac{1}{{n^{1/3} }}} \right)} \right) \end{align*} for any fixed $\alpha>0$. Consequently, $$ \mathop {\lim }\limits_{n \to + \infty } \frac{1}{n}\int_1^n {\left( {1 - \frac{1}{x}} \right)^{\alpha n} dx} = \alpha \int_\alpha ^{ + \infty } {e^{ - s} \frac{{ds}}{{s^2 }}} = \alpha \Gamma ( - 1,\alpha ) $$ for any fixed $\alpha>0$. Here $\Gamma(a,z)$ is the upper incomplete gamma function. Finally, $$\boxed{ \mathop {\lim }\limits_{n \to + \infty } \frac{1}{n}\sum\limits_{i = 1}^n {\left( {1 - \frac{1}{i}} \right)^{\alpha n} } = \alpha \Gamma ( - 1,\alpha ) }$$ for any fixed $\alpha>0$. Note that in terms of the exponential integral, $\alpha \Gamma ( - 1,\alpha ) = e^{ - \alpha } - \alpha E_1 (\alpha )$.

Try to plot, for example, $$ \frac{1}{{1000}}\sum\limits_{i = 1}^{1000} {\left( {1 - \frac{1}{{i}}} \right)^s } \;\; \text{ and } \;\; \frac{s}{{1000}}\Gamma\! \left( { - 1,\frac{s}{{1000}}} \right) $$ against each other on the range $1\leq s\leq 10000$.