14
$\begingroup$

Consider the known harmonic series $\sum_{n=1}^\infty \frac{1}{n}$ and modify it as follows

$$\sum_{n=1}^\infty a_n\frac{1}{n}$$ where $$a_n \sim \operatorname{Bern} \left({\frac{1}{2}}\right)$$ i.e. each $a_n$ is $0$ or $1$ with probability $\frac{1}{2}$ (basically what one is doing here is removing randomly an infinite number of terms of this series)

Is it possible to know that this series is almost always convergent? Meaning that it converges with probability $1$?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ This may be helpful: en.wikipedia.org/wiki/Kolmogorov%27s_three-series_theorem $\endgroup$ – user940 Jun 14 '16 at 14:50
  • 2
    $\begingroup$ I wonder what would happen if $a_n \sim \text{Bern}(f(n))$, where $f(x) \in [0,1]$. What consequences changing $f(n)$ could have for convergence. $\endgroup$ – mathreadler Jun 14 '16 at 19:34
  • 2
    $\begingroup$ The accepted answer is faulty. $\endgroup$ – Did Jun 15 '16 at 5:00
  • $\begingroup$ Yup, the accepted answer looks just plain wrong, but the argument (by the same person) in comments to another answer -- appealing to the Kolmogorov 0-1 law -- seems sound and rather nice. $\endgroup$ – Gareth McCaughan Jun 15 '16 at 14:35
  • $\begingroup$ Added rigor. What's wrong with the answer? I claimed that the partial sums had converging variances and diverging means, and that this implies that the sequence of partial sums diverges with probability $1$. $\endgroup$ – mjqxxxx Jun 15 '16 at 16:43
47
$\begingroup$

For any such sequence $(a_n)$, the corresponding sequence $(b_n)$ given by $b_n=1-a_n$ is just as likely. So according to your intuition, the series $$\sum_{n=1}^\infty b_n\frac{1}{n}$$ should converge almost surely. But then $$\sum_{n=1}^\infty \frac{1}{n} = \sum_{n=1}^\infty a_n\frac{1}{n} + \sum_{n=1}^\infty b_n\frac{1}{n}$$ would converge too!

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ +1 Nice way to show that more often than not you have a divergent series thus destroying my original intuition! $\endgroup$ – gota Jun 14 '16 at 14:56
  • 8
    $\begingroup$ from The Book. :) $\endgroup$ – jwg Jun 14 '16 at 15:21
  • 3
    $\begingroup$ Note that the series diverging is a tail event, so by the Kolmogorov zero-one law, it occurs with probability $0$ or $1$. This argument shows that it doesn't occur with probability $1$; so it must occur with probability $0$. $\endgroup$ – mjqxxxx Jun 15 '16 at 7:12
  • 1
    $\begingroup$ @mjqxxxx: I think you mean "converging", not "diverging". $\endgroup$ – TonyK Jun 15 '16 at 10:11
  • 2
    $\begingroup$ Oops, switch my zero and one. "Note that the series diverging is a tail event, so by the Kolmogorov one-zero law, it occurs with probability $1$ or $0$. This argument shows that it doesn't occur with probability $0$; so it must occur with probability $1$." $\endgroup$ – mjqxxxx Jun 15 '16 at 15:12
12
$\begingroup$

Your series is almost surely divergent (i.e., it diverges with probability $1$). Let $X_n = a_n/n$ be the $n$th term. Then $$ E[X_n]=\frac{1}{2n} $$ and $$ {\text{Var}}[X_n]=E[X_n^2]-E[X_n]^2=\frac{1}{4n^2}. $$ The variance of the partial sums is therefore $$ {\text{Var}}\left[\sum_{i=1}^{n}X_i\right]=\frac{1}{4}\sum_{i=1}^{n}\frac{1}{i^2}\rightarrow\frac{\pi^2}{24}; $$ the expectation value of the partial sums, on the other hand, is $$ E\left[\sum_{i=1}^{n}X_i\right]=\frac{1}{2}\sum_{i=1}^{n}\frac{1}{i}=\frac{1}{2}H_n \sim \frac{1}{2}\log n. $$ So the sequence of partial sums diverges logarithmically with probability $1$.

As I'm getting some down votes, I wanted to add a few steps to show that this argument is sound. I've got random variables $S_n$ such that $\mu_n = E[S_n]\rightarrow\infty$ and $\sigma_n^2={\text{Var}}[S_n]\rightarrow \sigma^2 < \infty$. I claim that $S_n$ is unbounded with probability $1$. If $S_n$ is bounded, then for some $x\in\mathbb{R}$ and some $N\in\mathbb{N}$, $S_n \le x$ for all $n\ge N$. In particular, for any sequence of indices $n_i\rightarrow\infty$ and sequence of bounds $A_i\rightarrow\infty$, $$ S_n {\text { bounded}} \implies S_{n_1} < A_1 \vee S_{n_2} < A_2 \vee \ldots, $$ and hence $$ {\text{Pr}}[S_n{\text { bounded}}] \le {\text{Pr}}[S_{n_1}<A_1] + {\text{Pr}}[S_{n_2}<A_2] + \ldots. $$ Let $M>0$ be a fixed, large number. Because $\mu_n\rightarrow\infty$ and $\sigma^2_n\rightarrow\sigma^2$, we can choose $n_i$ large enough that $\mu_{n_i} > 2^{i/2+1} M \sigma_{n_i}$ and $n_i\rightarrow\infty$; and choose $A_i=\mu_{n_i} - 2^{i/2} M\sigma_{n_{i-1}}$. But $$ {\text{Pr}}[S_{n_i} < \mu_{n_i} - 2^{i/2} M\sigma_{n_{i-1}}] \le {\text{Pr}}\left[\frac{(S_{n_i}-\mu_{n_i})^2}{\sigma^2_{n_{i-1}}} > 2^{i} M^2\right] \le \frac{1}{2^{i}M^2}, $$ so $$ {\text{Pr}}[S_n{\text { bounded}}] \le \sum_{i=1}^{\infty}\frac{1}{2^{i}M^2} = \frac{1}{M^2}. $$ Since $M$ was arbitrary, we can choose it to be as large as we like; we conclude that ${\text{Pr}}[S_n{\text { bounded}}]=0$, and hence that $S_n$ converges with probability $0$ as well. In our case, we need only the additional fact that $S_n$ is monotonically increasing to conclude that $S_n$ a.s. diverges to infinity (since that's the only other option).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It is interesting to note that despite probability 1, if Bern() is replaced with Bmalice() (that is to say the RNG hates your guts) it might converge. $\endgroup$ – Joshua Jun 14 '16 at 16:33
  • $\begingroup$ @Joshua: Definitely. An event that occurs with probability $1$ just occurs a.s. ("almost surely"), not "surely". $\endgroup$ – mjqxxxx Jun 14 '16 at 18:49
  • $\begingroup$ $mjqxxxx: Is that the same idea as a.e. "almost everywhere"? $\endgroup$ – mathreadler Jun 14 '16 at 19:28
  • $\begingroup$ @mathreadler Yes. "almost surely" is the probability version of "almost everywhere". $\endgroup$ – Teepeemm Jun 14 '16 at 21:49
  • 4
    $\begingroup$ This argument is off. You can have horrible things like $E[X_n] = \infty$ for all $n$, but $E[\lim_{n \to \infty} X_n] = 0$ and $P(X_n \text{ converges}) = 1$. (e.g. let $X_0$ be drawn from any distribution with infinite expectation and $X_i = \frac{1}{2} X_{i-1}$) $\endgroup$ – Excluded and Offended Jun 15 '16 at 0:11
9
$\begingroup$

Why would it ever converge ?

Taking the expectation,

$$E\left(\sum_{n=1}^\infty a_n\frac{1}{n}\right)=\sum_{n=1}^\infty E(a_n)\frac{1}{n}=\frac12\sum_{n=1}^\infty \frac{1}{n}.$$

Even if the argument isn't rigorous because none of these series converge, it should be enough to shed doubt.

In the harmonic series, removing all but every millionth term is not enough to restore convergence, because $\sum\frac1{1000000n}=\frac1{1000000}\sum\frac1n$.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Does taking the expectation make any sense? even if only 10% of the resulting series remain divergent the expectation would always be infinity. Masking the fact that now the majority of the resulting series would converge $\endgroup$ – gota Jun 14 '16 at 13:55
  • 2
    $\begingroup$ @NunoCalaim: the Kempner series converges because the remaining terms are sparser and sparser (their indexs grow superlinearly). This is not the case with a random drawing. $\endgroup$ – Yves Daoust Jun 14 '16 at 13:57
  • 1
    $\begingroup$ Clearly there are specific choices of $a_n$ that make the resulting series divergent ($a_n=1$) and convergent (Kemper Series). I was trying to understand if more often than not we have divergent or convergent $\endgroup$ – gota Jun 14 '16 at 13:57
  • 4
    $\begingroup$ @NunoCalaim I bet your series is almost surely divergent. $\endgroup$ – Yves Daoust Jun 14 '16 at 13:58
  • 1
    $\begingroup$ thanks! I would love to see a rigorous proof of this, do you have any idea where to start? $\endgroup$ – gota Jun 14 '16 at 14:01
5
$\begingroup$

This answer combines and elaborates on two comments to the OP's post. Let

$$a_n \sim \operatorname{Bern} \left({f(n)}\right),\;\;\; f(n) \in (0,1)$$

set $X_n \equiv n^{-1}a_n$ and consider

$$\sum_{i=1}^\infty X_i $$

with the random variables assumed independent.

Checking the conditions of Kolmogorov's Three-series Theorem, set $A > 1$. Then

$$\Pr(|X_n|\geq A)=0 \implies \sum_{i=1}^{\infty} \Pr(|X_i|\geq A) =0 \tag{1}$$

converges (this is just a special case that holds in general for any random variable with support bounded from above).

Also $I_{\{|X_n|\leq A\}} =1\;\; \forall\, n$, so

$$\sum_{i=1}^{\infty}E[X_i\cdot I_{\{|X_i|\leq A\}}] = \sum_{i=1}^{\infty}E[X_i] =\sum_{i=1}^{\infty}\frac {f(i)}{i} \tag{2}$$

A choice for $f(n)$ for this to converge is $f(n) = n^{-\alpha},\, \alpha >0$, since this will give a hyperharmoninc series, which converges.

Finally,

$$\sum_{i=1}^{\infty}\text{Var}[X_i\cdot I_{\{|X_i|\leq A\}}] = \sum_{i=1}^{\infty}\text{Var}[X_i] =\sum_{i=1}^{\infty}\frac {f(i)[1-f(i)]}{i^2} \tag {3}$$

which converges for all and any $f(i) \in (0,1)$, since it is strictly smaller than $\sum_{i=1}^{\infty}i^{-2} = \pi^2/6$.

So the critical condition, is the convergence of the sum of the expected values (condition $2$), since it is this condition that imposes restrictions on the form of $f(n)$ in order to obtain convergence.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

This post directly proves that

$$ P\left( \sum_{n=1}^{\infty} \frac{a_n}{n} = \infty \right) = 1$$

rather than study about different quantities so as to make a heuristic argument that helps convince that the result is plausible.

The method is

  • Decompose the sum into a sequence of independent, disjoint partial sums with rapidly decreasing variance
  • Find a lower bound on the probability that each partial sum is greater than $0.01$
  • Find a lower bound on the probability that infinitely many of the partial sums are all greater than $0.01$ (and thus the sum diverges)
  • Deduce from the form of the final result that the probability of divergence is $1$

Borrowing the methods of the other answer,

Let $X_n = a_n / n$ be the $n$-th term.

Define a new sequence of independent random variables

$$ S_n = \sum_{i=2^n}^{2^{n+1} - 1} X_n $$

so that the total sum is

$$ \sum_{i=1}^{\infty} \frac{a_i}{i} = \sum_{n=0}^{\infty} S_n $$

We have

$$ E[S_n] = \sum_{i=2^n}^{2^{n+1} - 1} E[X_n ] = \frac{1}{2} (H_{2^{n+1} - 1} - H_{2^n - 1} ) \approx \frac{1}{2} \ln(2)$$

where $H_n$ is the $n$-th harmonic number. We also have the variance

$$ Var[S_n] = \sum_{i=2^n}^{2^{n+1} - 1} \frac{1}{4i^2} < 2^{-n} $$

(we can prove a slightly stronger bound, but I'm lazy!)

Chebyshev's inequality then says that, for any positive $k$,

$$ P\left(\left|S_n - \frac{1}{2} \ln 2\right| < k 2^{-n/2} \right) \geq 1 - \frac{1}{k^2} $$

For sufficiently large $k$, I claim that

$$ \exp(-2/k^2) = 1 - \frac{2}{k^2} + \frac{2}{k^4} - \ldots \leq 1 - \frac{1}{k^2} $$

and therefore,

$$ P\left(\left|S_n - \frac{1}{2} \ln 2\right| < \frac{1}{4} \right) \geq 1 - \frac{1}{2^{n-4}} \geq \exp\left(-\frac{1}{2^{n-5}} \right) $$

These events are jointly independent, so we have

$$ P\left(\forall n \geq m: \left|S_n - \frac{1}{2} \ln 2\right| < \frac{1}{4} \right) \geq \exp\left(-\sum_{n = m}^{\infty} \frac{1}{2^{n-5}} \right) = \exp(-2^{6-m}) $$

In particular, this means

$$ P(\forall n \geq m: S_n > 0.01) \geq \exp(-2^{6-m}) $$

from which it follows

$$ P\left( \sum_{n=0}^{\infty} S_n = \infty \right) \geq \exp(-2^{6-m}) $$

by taking the limit as $m \to \infty$, we get

$$ P\left( \sum_{n=0}^{\infty} S_n = \infty \right) \geq 1 $$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nearly every step could be done more carefully to try and get accurate estimates for things -- but very loose bounds are enough to arrive at the result, so I opted to do something I could reason quickly. $\endgroup$ – Excluded and Offended Jun 15 '16 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.