# Show that $\frac{1}{n}\sum_{j=1}^\infty \left( 1 - (1-p_j)^n\right) \to 0$ as $n \to \infty$

Given $$p_j \geq 0$$ for all $$j \geq 1$$ and $$\sum_{j=1}^\infty p_j = 1$$, I am asked to show that $$\frac{1}{n}\sum_{j=1}^\infty \left( 1 - (1-p_j)^n\right) \to 0 ~~ \textrm{as} ~~ n \to \infty.$$ Unfortunately, using only the fact that $$(1-p_j)^n \geq 1 - np_j$$ will not be enough, as this inequality only gives us $$\frac{1}{n}\sum_{j=1}^\infty \left( 1 - (1-p_j)^n\right) \leq \frac{1}{n}\sum_{j=1}^\infty np_j = 1.$$ Can anyone provide a hint towards the proof?

Remark: This problem is related to exercise 3.8 in this monograph.

• @KentaS I don't think so by a quick try... If you could do it can you show me the details...? For someone who voted "close", may I know the reason? Dec 23, 2021 at 3:56
• I did not vote to close, but the reason given was lack of context.
– robjohn
Dec 23, 2021 at 8:33
• If you provide some context, other answers will most likely be posted. Furthermore, it should prevent more close votes and the probable delete votes following. I think this is a good question, it just needs to be expanded to meet the site requirements. Where did you get the problem? Did this come up in a course/book; if so which course/book? What tools are being discussed in the course/book? etc.
– robjohn
Dec 23, 2021 at 16:54
• Even if, in your question, you just showed that $(1-p_j)^n \ge1-np_j$, as is, only seems to show that $\lim\limits_{n\to\infty}\frac1n\sum\limits_{j=1}^\infty\left(1-(1-p_j)^n\right)\le\sum\limits_{j=1}^\infty p_j=1$, that would add more context.
– robjohn
Dec 24, 2021 at 13:40
• @robjohn I have taken care of your suggestions and the original post has been modified~ Merry Christmas! Dec 25, 2021 at 1:12

I think your bound suffices! In fact, we have that $$\frac{1}{n} \sum_{j=k+1}^\infty (1-(1-p_j)^n) \leq \frac{1}{n} \sum_{j=k+1}^\infty n p_j = \sum_{j=k+1}^\infty p_j.$$ This way, for each $$k$$ we can bound the total sum as \begin{align*} \frac{1}{n}\sum_{j=1}^\infty (1-(1-p_j)^n) &= \frac{1}{n} \sum_{j=1}^k (1-(1-p_j)^n) + \frac{1}{n}\sum_{j=k+1}^\infty (1-(1-p_j)^n) \\ &\leq \frac{1}{n}\sum_{j=1}^k 1+\sum_{j=k+1}^\infty p_j \\ &= \frac{k}{n} +\sum_{j=k+1}^\infty p_j. \end{align*} Now, the result follows by truncating. Fix $$\varepsilon>0$$. Take $$k>0$$ such that the sum $$\sum_{j=k+1}^\infty p_j$$ is less than $$\varepsilon/2$$, and then take $$n>2k/\varepsilon$$. The computation from above shows that $$\frac{1}{n}\sum_{j=1}^\infty (1-(1-p_j)^n) \leq \frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon,$$ which proves the statement.

• (+1) Nice solution! I posted another solution that is inspired by your approach. Dec 23, 2021 at 6:31
• This solution is just so NICE! Dec 23, 2021 at 21:59

From the inequality that OP observed, we get $$(1-p_j)^n \geq \max\{1 - np_j, 0\}$$ and hence

$$1 - (1-p_j)^n \leq \min\{np_j, 1\},$$

From this, we get

$$\frac{1}{n} \sum_{j=1}^{\infty} (1 - (1-p_j)^n) \leq \sum_{j=1}^{\infty} \min\{p_j, 1/n\}.$$

Since the $$j$$th summand of the last sum is always bounded by $$p_j$$ and $$\sum_{j=1}^{\infty} p_j$$ converges, by the dominated convergence theorem

$$\lim_{n\to\infty} \sum_{j=1}^{\infty} \min\{p_j, 1/n\} = \sum_{j=1}^{\infty} \lim_{n\to\infty} \min\{p_j, 1/n\} = \sum_{j=1}^{\infty} \min\{p_j, 0\} = 0.$$

So by the squeezing theorem,

$$\lim_{n\to\infty} \frac{1}{n} \sum_{j=1}^{n} (1 - (1-p_j)^n) = 0.$$

Applying the Stolz-Cesaro theorem, we have to compute $$\lim_{n\to\infty}\left[\sum_{j=1}^{\infty}\left(1-(1-p_j)^{n+1}\right)-\sum_{j=1}^{\infty}\left(1-(1-p_j)^{n}\right)\right] \\=\lim_{n\to\infty}\sum_{j=1}^{\infty}p_j(1-p_j)^n$$ From the given sum it follows that $$p_j\le 1$$. Thus, $$0\le p_j(1-p_j)^n\le p_j$$, and we know $$\sum_{j=1}^{\infty}p_j$$ converges. This implies that we can switch the limit and the summation in the previous line. $$\lim_{n\to\infty}p_j(1-p_j)^n=0 \\ \Rightarrow \lim_{n\to\infty}\sum_{j=1}^{\infty}p_j(1-p_j)^n=\sum_{j=1}^{\infty}0=0$$

Here is another approach to splitting the sum at a strategic point.

Dominated Convergence says that $$\lim_{k\to\infty}\sum_{j=1}^\infty(1-p_j)^kp_j=0\tag1$$ Thus, for any $$\epsilon\gt0$$, there is a $$k_\epsilon$$ so that for all $$k\ge k_\epsilon$$ $$\sum_{j=1}^\infty(1-p_j)^kp_j\le\epsilon\tag2$$ Therefore, for $$n\ge k_\epsilon$$, \begin{align} \frac1n\sum_{j=1}^\infty\left(1-(1-p_j)^n\right) &=\frac1n\sum_{j=1}^\infty\frac{1-(1-p_j)^n}{1-(1-p_j)}p_j\tag{3a}\\ &=\frac1n\sum_{j=1}^\infty\sum_{k=0}^{n-1}(1-p_j)^kp_j\tag{3b}\\ &=\frac1n\sum_{k=0}^{n-1}\sum_{j=1}^\infty(1-p_j)^kp_j\tag{3c}\\ &=\frac1n\sum_{k=0}^{k_\epsilon-1}\sum_{j=1}^\infty(1-p_j)^kp_j+\frac1n\sum_{k=k_\epsilon}^{n-1}\sum_{j=1}^\infty(1-p_j)^kp_j\tag{3d}\\ &\le\frac1n\ \underbrace{\sum_{k=0}^{k_\epsilon-1}\sum_{j=1}^\infty(1-p_j)^kp_j}_\text{constant in n}+\underbrace{\ \frac{n-k_\epsilon}{n}\ \vphantom{\sum_j^1}}_{\le1}\ \epsilon\tag{3e} \end{align} Explanation:
$$\text{(3a)}$$: $$1-(1-p_j)=p_j$$
$$\text{(3b)}$$: $$\frac{1-x^n}{1-x}=\sum\limits_{k=0}^{n-1}x^k$$
$$\text{(3c)}$$: swap order of summation
$$\text{(3d)}$$: split the outer sum at $$k_\epsilon$$
$$\text{(3e)}$$: apply $$(2)$$

Taking the limit of $$(3)$$, $$\lim_{n\to\infty}\frac1n\sum_{j=1}^\infty\left(1-(1-p_j)^n\right) \le\epsilon\tag4$$ Since $$\epsilon\gt0$$ was arbitrary, $$(4)$$ means $$\lim_{n\to\infty}\frac1n\sum_{j=1}^\infty\left(1-(1-p_j)^n\right)=0\tag5$$

I came to know this $$\epsilon$$-$$N$$ argument from the elementary proof of Tannery theorem [1].
(I used Tannery theorem to prove that $$\lim_{n \to \infty} \int^1_0 f(x) |\sin(n \pi x)|\,\mathrm{d}x = \frac{2}{\pi} \int^1_0 f(x)\,\mathrm{d}x$$ Proving $\lim_{n \to \infty} \int^1_0 f(x) |\sin(n \pi x)|\,dx = \frac{2}{\pi} \int^1_0 f(x)\,dx$ .)

Denote $$m = \lfloor \sqrt{n}\rfloor$$ where $$\lfloor \cdot \rfloor$$ is the floor function. We have \begin{align*} &1 - (1 - p_j)^n\\ =\,& p_j\Big(1 + (1 - p_j) + (1 - p_j)^2 + \cdots + (1 - p_j)^{n - 1}\Big)\\ \le\,& p_j \Big(1 + (1 - p_j) + (1 - p_j)^2 + \cdots + (1 - p_j)^{m - 1} + n (1 - p_j)^m\Big)\\ \le\,& p_j \Big(m + n(1 - p_j)^m\Big). \end{align*} Thus, $$\frac{1}{n}[1 - (1 - p_j)^n] \le \frac{m}{n} p_j + p_j(1 - p_j)^m.$$

It suffices to prove that $$\lim_{m\to \infty} \sum_{j=1}^\infty p_j(1 - p_j)^m = 0.$$

$$\epsilon$$-$$N$$ argument:

For any given $$\epsilon > 0$$, there is an $$N$$ such that $$\sum_{j > N} p_j(1 - p_j)^m \le \sum_{j > N} p_j < \frac{\epsilon}{2}$$.
Clearly, for each $$j$$, there is an $$M_j$$ such that $$p_j(1 - p_j)^m < \frac{\epsilon}{2N}$$ for all $$m > M_j$$.
Let $$M = \max(M_1, M_2, \cdots, M_N)$$. We have $$\sum_{j=1}^\infty p_j(1 - p_j)^m = \sum_{j\le N} p_j(1 - p_j)^m + \sum_{j > N} p_j(1 - p_j)^m < N \cdot \frac{\epsilon}{2N} + \frac{\epsilon}{2} = \epsilon$$ for all $$m > M$$.

Reference:

[1] Josef Hofbauer, "A simple proof of 1 + 1/22 + 1/32 + ... = PI2/6 and related identities", American Mathematical Monthly 109 (February 2002), 196-200. https://homepage.univie.ac.at/josef.hofbauer/piq6.htm