Conditional Convergence

In this post I wanted to discuss an unintuitive fact related to infinite series which often leads to confusion among early students of Real Analysis.

Even if you have not seen the formal definition of a series before you may have seen examples of them, such as the harmonic series \sum_{n=1}^{\infty} \frac{1}{n} or the infinite geometric series \sum_{n=0}^{\infty} a^n, perhaps calling them “infinite sums”.

The notation using the greek letter sigma can be quite misleading, since series do not always behave as nicely as one might initially expect. We will discuss what strange things can happen if one is not careful.

Formally, given an infinite sequence (a_n), a series is nothing but another special sequence (s_n) where s_n := a_0 + ... + a_n \;\;\;\forall n\in\mathbb{N}.
This sequence is denoted \sum_{n=0}^{\infty} a_n and we call the s_n partial sums of the series.

Apart from obvious issues, such as divergence to infinity (i.e the fact that the sum can grow uncontrollably large in either direction), there are other more subtle issues where series may behave differently from honest sums.

Consider a permutation f:\mathbb{N} \rightarrow \mathbb{N} and a convergent series \sum_{n=0}^{\infty} a_n.
We may ask: Does \sum_{n=0}^{\infty} a_n converge to the same value as \sum_{n=0}^{\infty} a_{f(n)}\;?
Or to give a more concrete informal example:
Is 1-\frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \frac{1}{6} + \frac{1}{7} - ... +\frac{1}{n} - ... the same as (1 + \frac{1}{3}) - \frac{1}{2} + (\frac{1}{5} + \frac{1}{7}) - \frac{1}{4} + ... - \frac{1}{2n} + (\frac{1}{2n+3} + \frac{1}{2n+5}) - \frac{1}{2n+2} + ... \; ?

Perhaps surprisingly the answer is No in general.
The example I gave above was a rearrangement of the alternating harmonic series.
It is a well known fact that this series converges to ln 2 and one can show that the rearrangement converges to something different, namely \frac{3}{2}ln 2.
The diagram below shows the numeric value of the first 30 partial sums of either series.

AlternatingHarmonicSeries

It seems like our intuition about series as ordinary sums break down here.
In fact as we will show in the rest of this post, matters are even worse.
It turns out that you can rearrange this series (and other series like it) to converge to any real number you like! If you wish you can even make it diverge to infinity.

The defining property of series that converge in this way but are sensitive to rearrangement is called Conditional Convergence.
Usually this property is stated in another way, as a series which is convergent but not Absolutely Convergent.
A series \sum_{n=0}^{\infty} a_n is Absolutely Convergent if \sum_{n=0}^{\infty} |a_n| converges.
The true meaning of this property is somewhat hidden behind this definition.

As it happens,
convergent series which are insensitive to rearrangement are precisely those which are absolutely convergent.

Let’s prove this statement in one direction:

Proposition 1:

Let \sum_{n=0}^{\infty} a_n be an absolutely convergent series, converging to L.

Then \sum_{n=0}^{\infty} a_{f(n)} also converges to L for every permutation f:\mathbb{N} \rightarrow \mathbb{N}.

Informal Proof:
 
Let s_n = \sum_{k=0}^{n} a_k and r_n = \sum_{k=0}^{n} a_{f(k)}.

To show convergence our goal is to show that the quantity |r_n - L| can be made arbitrarily small for sufficiently large n, that is to say |r_n - L| \rightarrow 0 as n \rightarrow \infty.

Since (s_n) converges to L we know that |s_n - L| \rightarrow 0 as n \rightarrow \infty.
To understand if (r_n) also converges to L we should suggestively compare (r_n) with (s_n). For if (r_n) and (s_n) get very close to each other, knowing that (s_n) gets very close to L we ought to see that (r_n) gets very close to L as well for sufficiently large n.

This type of idea in analysis is usually expressed via the triangle inequality:

|r_n - L| = |r_n - L + s_n - s_n| \leq |r_n - s_n| + |s_n - L|\;\;\;(*)

We know how to manage the quantity |s_n - L|.
We want to know what happens to |r_n - s_n| as n grows large.

Consider a fixed N \in \mathbb{N}.
Since f:\mathbb{N} \rightarrow \mathbb{N} is a bijection (permutations are by definition bijections) \exists n_0,...,n_N \in \mathbb{N} s.t f(n_0) = 0, ..., f(n_N) = N.

Let M := max\{n_0,...,n_N\} \geq N and consider the set of subscripts D := \{1,...,M\} \setminus \{n_0,...,n_N\} that do not belong to \{1,...,N\} after applying f.

Then
|r_M - s_N| = |\sum_{k=0}^M a_{f(k)} - \sum_{k=0}^N a_{f(n_k)} | = |\sum_{k \in D} a_{f(k)}| \leq^{(\bigtriangleup-ineq)} \sum_{k \in D} |a_{f(k)}| \leq^{(more\;positive\;terms)} \sum_{k=N+1}^{\infty} |a_k|

This is where the hypothesis about absolute convergence kicks in.
Absolute convergence implies \sum_{k=N+1}^{\infty} |a_k| \rightarrow 0 as N \rightarrow \infty.
Thus since M \rightarrow \infty \; as \; N \rightarrow \infty we find that |r_n - s_n| \rightarrow 0 as n \rightarrow \infty.

In combination with |s_n - L| \rightarrow 0 as n \rightarrow \infty we get from (*) that |r_n - L| \rightarrow 0 as n \rightarrow \infty.

This shows that \sum_{n=0}^{\infty} a_{f(n)} converges to L.

 
To prove the converse we need to show that all convergent series that are not absolutely convergent (i.e conditionally convergent) are non-invariant under rearrangement.

From now on we will assume \sum a_n is conditionally convergent.

As I hinted initially something stronger holds true for conditionally convergent series.
Not only are the limits of these series sensitive to rearrangement, these series can be rearranged to converge to any real number. This result is commonly known as Riemann’s rearrangement theorem.

The idea behind the proof is essentially to construct a rearrangement by indefinitely adding positive and negative terms from the original series in order to oscillate around the chosen real value, and show that these oscillations get smaller and smaller.

Define a_n^+ = \begin{cases} a_n \;\; if\;\; a_n > 0 \\ 0 \;\;\;\;otherwise \end{cases} and a_n^- = \begin{cases} a_n \;\; if\;\; a_n < 0 \\ 0 \;\;\;\;otherwise \end{cases}

There are a few technical issues that need to be resolved before we can claim the construction idea is well defined.

  1. Are there infinitely many non-zero a_n^+, a_n^- so we can indefinitely add positive and negative terms?
  2. Is \sum a_n^+ unbounded above and \sum a_n^- unbounded below so we have a chance at getting close to any real value?
  3. Does a_n^+, a_n^- both converge to 0 so that we can make oscillations arbitrarily small?

Answer to all 3 questions need to be Yes for this construction to work.

To see (1) we could argue by contradiction and e.g assume there are only finitely many non-zero a_n^- (the a_n^+ case works similarly). In fact let’s assume something even weaker and just suppose that \sum a_n^- is convergent.

Then \sum |a_n| = \sum (a_{n}^{+} - a_{n}^{-})=\sum (a_{n}^{+} + a_{n}^{-})-2\sum a_n^-=\sum a_n -2\sum a_n^-

By assumption both series on the right hand side converge, implying \sum |a_n| is convergent. But we assumed \sum a_n was not absolutely convergent so this is a contradiction. Therefore \sum a_n^- cannot converge and in particular this means the number of negative terms are infinite.

From this we can also deduce (2) because \sum a_n^- is monotonically decreasing (being a series of non-positive terms) and if it was bounded below then a  standard result from real analysis (Monotone Convergence Theorem) says that \sum a_n^- needs to converge which we know it cannot. Hence \sum a_n^- cannot be bounded below.

A symmetrical argument establishes (1) and (2) for \sum a_n^+.

(3) follows directly from the fact that terms of convergent series necessarily tend to zero.
To see this just write a_n = \sum_{k=0}^n a_k -\sum_{k=0}^{n-1} a_k and notice that the right hand side converges to zero as n \rightarrow \infty since both series converge to the same value.

Hence we can answer all 3 questions in the affirmative.

Now let’s sketch a proof of Riemann’s Rearrangement Theorem

 

Riemann Rearrangement Theorem:
 
Let \sum_{k=0}^{\infty} a_k be a conditionally convergent series and let L \in \mathbb{R}.

Then there exists a permutation f:\mathbb{N} \rightarrow \mathbb{N} s.t \sum_{k=0}^{\infty} a_{f(k)} converges to L.

Proof (Sketch):
The proof is constructive (the best kind).

Let L \in \mathbb{R}.

By (2):

since \sum_{k=0}^{\infty} a_k^+ is unbounded above we can choose the smallest n_1 \in \mathbb{N} s.t
a_0^+...+a_{n_1}^+ > L.

since \sum_{k=0}^{\infty} a_k^- is unbounded below we can choose the smallest m_1 \in \mathbb{N} s.t
a_0^+...+a_{n_1}^++a_0^-...+a_{m_1}^- < L.

We can continue to choose the smallest n_{2}\; \textgreater \;n_{1} s.t a_0^+...+a_{n_1}^++a_0^-...+a_{m_1}^-+a_{n_1+1}^+...+a_{n_2}^+ \; \textgreater \; L etc..

Inductively if we denote P_i := a_{n_{i-1}+1}^+...+a_{n_i}^+ and N_i := a_{m_{i-1}+1}^-...+a_{m_i}^-
we obtain a rearrangement P_1 + N_1 + ... + P_k + N_k + ... of \sum_{k=0}^{\infty} a_k s.t
P_1 + N_1 + ... + P_k \; \textgreater \; L and P_1 + N_1 + ... + P_k + N_k \; \textless \; L \forall k \in \mathbb{N}.

We can make this definition since we have an infinite supply of positive and negative terms by (1).

An arbitrary partial sum in the rearrangement has one of below two forms:
s_{n} = P_1 + N_1 + ... + P_k + N_k + a_{n_k+1}^+ + ... + a_{n_k+r}^+ or
s_{n} = P_1 + N_1 + ... + P_k + a_{m_{k-1}+1}^- + ... + a_{m_{k-1}+r}^-.

We want to show |s_n - L| \rightarrow 0 as n \rightarrow \infty.

We clearly have P_1+N_1+...+P_k+N_k - L \leq s_n - L \leq P_1+N_1+...+P_k - L.

By construction,
P_1+N_1+...+P_k+N_k - a_{m_k}^- \geq L and
P_1+N_1+...+P_k - a_{n_k}^+ \leq L.

Therefore a_{m_k}^- \leq s_n - L \leq a_{n_k}^+

By (3) we know that a_{n_k}^+, a_{m_k}^- \rightarrow 0 as k \rightarrow \infty so s_n -L is being squeezed between two sequences converging to zero and is therefore forced to converge to zero as well by the so called Sandwich Theorem.

This shows that the rearranged series converges to L.
Since L was arbitrary the result follows.

 

To put back some intuition behind this phenomenon the proof tells us that conditionally convergent series are a result of two divergent series \sum a_k^+, \sum a_k^- cancelling out each other to allow for convergence.
In the cancelling race between the two series we can give one series an “infinite head start” by pushing terms from the other series further away into infinity. This way we can accumulate terms quicker in the partial sums from one of the series, at a pace we set, and thus have it converge to anything we like. I am being purposely vague here, but hopefully this makes some intuitive sense.

In a way one could think of the terms in a conditionally convergent series as being infinite streams of positive revenue and negative expenditure. By rearranging expenditures ahead in time we could alter our book balance (and in theory make infinite profit).
Funny enough this is the basic idea behind Ponzi schemes.
Of course in reality Ponzi schemes do not generate infinite profit.
It inevitably falls apart because the criminal cannot find sufficiently many revenue sources to sustain the expenditure commitments of the scheme, so when the scheme finally starts to collapse the criminal has to run away with the money.
The basic fallacy in applying this idea to real life is that things are usually not infinite even though people sometimes behave as if they are. Economic bubbles are a good real world example which behave very similar to Ponzi schemes but on a much larger scale. Eventually money is solely being made at expense of new investors entering the market, the profit being completely detached from the markets intrinsic value. Of course the number of investors nor their money is infinite, so sooner or later people are bound to lose money as the bubble implodes due to lack of new buying market participants (i.e there are only sellers left).

Exercise 1( Alternating Harmonic Series – Intermediate):
 
Prove that \sum_{n=1}^{\infty} (-1)^{n+1}\frac{1}{n} = ln(2).

(Hint: Look at the partial sums s_{2n} and express it as a Riemann sum like in the previous post YAPP)

 

Exercise 2( Conditional Divergence – Easy):
 
Prove that every conditionally convergent series can be rearranged to diverge to infinity.

 

Exercise 3( Huh? – Easy):

What is the fallacy in below argument?

0 = 0 + 0 + 0 + 0 + .... =
(1-1) + (1-1) + (1-1) + (1-1) + .... =
1 + (-1+1) + (-1+1) + (-1+1) + (-1+1) + .... =
1 + 0 + 0 + 0 + 0 + .... = 1

Advertisements
This entry was posted in Analysis, Uncategorized and tagged , , , , , , , , , , , . Bookmark the permalink.