Series Convergence via Comparison Tests

Series pop up all over the place when we try to work with unbounded random variables.

For example, suppose that $X \in \{1,2,3,4,...,\infty\}$ with $\text{PMF}(x) = p(x)$ for some function $p$ . Then each of the following are defined by a series:

Survival Function: $\text{Pr}(X > x) = \sum_{n = x+1}^{\infty} p(n).$
Expected Value: $\mathbb{E}[X] = \sum_{n = 1}^{\infty} n p(n).$
Variance: $\text{Var}[X = \mathbb{E}[X^2] - \mathbb{E}[X]^2$ where $\mathbb{E}[X^2] = \sum_{n = 1}^{\infty} n^2 p(n).$

In each case we need to evaluate a series.

In Section 5.1 we saw that not all series converge, even if the entries of the corresponding sequence converges to zero. We set up a contrast between two cases:

Sequence Name	Formula	Series	Series Value	Convergence
Geometric	$r^n$	$\sum_{n=0}^{\infty} r^n$	$\frac{1}{1 - r}$	if $-1 < r < 1$
Harmonic	$n^{-1}$	$\sum_{n=1}^{\infty} n^{-1}$	$\infty$	diverges

Before we learn how to evaluate the value of series, we should learn how to determine whether they converge. This chapter will introduce three convergence tests. They all work by comparing a series of interest to a series (or integral) whose behavior we already understand.

Integral Comparison Test¶

Our first test is the test we used to show that the Harmonic series diverges.

To use this test, check that the sequence $\{a(1),a(2),a(3),...\}$ can be expressed as sample values of a smooth, nonnegative, decreasing function (e.g. $x^{-1}$ ), then:

Compute the integral $\int_{x = 1}^{\infty} f(x) dx$ .
Determine convergence:
- If the integral converges, then the series converges.
- If the integral diverges, then the series diverges.

This test also works if $a(n) = f(n)$ for all $n \geq k$ for some $k$ , or if $a(n)$ converges to $f(n)$ as $n$ diverges.

Proof

To see why the test works, first plot the sequence $\{a(n)\}_{n=1}^{\infty}$ as a bar plot with bars of width 1. Set the bar for $a(n)$ to start at $n$ and end at $n+1$ . Then its left endpoint marks $a(n)$ . Overlay the function $f(x)$ .

The example below shows the harmonic series $a(n) = 1/n$ (bars) against the function $f(x)= x^{-1}$ (gold curve).

Since the bars have width one, the blue shaded area equals the series $\sum_{n=1}^{\infty} a(n)$ . The area under the gold curve is the integral $\int_{x = 0}^{\infty} f(x) dx$ . Since the curve is beneath the barplot, the area under the curve must be less than the area of the barplot. So:

\int_{x = 1}^{\infty} f(x) dx \leq \sum_{n = 1}^{\infty} a(n).

(2)

It follows that, if the integral diverges, then the series must also diverge.

Our choice to start each bar at $n$ and end it at $n+1$ was arbitrary. We could have, just as well, started each bar at $n - 1$ and ended it at $n$ . Then our picture would have been:

Now the barplot lies beneath the curve, so the value of the series is bounded above by the integral:

\sum_{n = 1}^{\infty} a(n) \leq \int_{x = 0}^{\infty} f(x) dx.

(3)

This is a bit awkward since we’ve changed the lower bound of the integral to start at zero. To keep the lower bound the same as before, write:

\sum_{n = 1}^{\infty} a(n) = a(1) + \sum_{n = 2}^{\infty} a(n)

(4)

then apply the integral upper bound to the sum starting from $n = 2$ :

\sum_{n = 1}^{\infty} a(n) = a(1) + \sum_{n = 2}^{\infty} a(n) \leq a(1) + \int_{x = 1}^{\infty} f(x) dx.

(5)

So, the series is bounded, from both sides, by the integral:

\int_{x = 1}^{\infty} f(x) dx \leq \sum_{n = 1}^{\infty} a(n) \leq a(1) + \int_{x = 1}^{\infty} f(x) dx.

(6)

If the integral converges, then the upper bound is finite, so the series converges. If the integral diverges then the lower bound is infinite, so the series diverges. $\square$

Just apply the integral test:

\int_{x = 1}^{\infty} x^{-\gamma} dx = \begin{cases} \frac{1}{1 - \gamma} x^{1 - \gamma}|_{x = 1}^{\infty} & \text{ if } 0 < \gamma < 1 \\ \log(x)|_{x = 1}^{\infty} & \text{ if } \gamma = 1 \\ -\frac{1}{(\gamma - 1)} x^{-(\gamma - 1)}|_{x = 1}^{\infty} & \text{ if } \gamma > 1 \\\end{cases}

(7)

When $\gamma \leq 1$ , the integral diverges since $\lim_{x \rightarrow \infty} x^{1 - \gamma}$ diverges if $\gamma < 1$ , and $\lim_{x \rightarrow \infty} \log(x)$ diverges.

In contrast, fi $\gamma > 1$ , then $x^{-(\gamma - 1)}$ is $x$ to a negative power, so $-\frac{1}{(\gamma - 1)} x^{-(\gamma - 1)}|_{x = 1}^{\infty} = \frac{1}{\gamma - 1}(1 - 0) = \frac{1}{\gamma - 1}$ . In this case the integral converges, so the series converges as well.

So, we can add all power laws to the list of series that we can sort by convergence. Any power law that decays faster than harmonic produces a convergent series.

Direct and Limit Comparison Tests¶

Often, we can prove convergence (or divergence) of a series, by comparing to a series we know converges (or diverges).

For example, knowing that the series $\sum_{n=1}^{\infty} n^{-2}$ converges establishes that $\sum_{n=1}^{\infty} n^{-3}$ converges since the sequence $n^{-3}$ converges to zero faster than the sequence $n^{-2}$ . This is an example of a comparison test:

These rules are common sense. If a sequence converges faster than a convergent series, then it defines a convergent series. If it converges slower than a diverging series, then it also defines a diverging series.

We can compare rates directly, or via a limit. Each produces a different variant of the same general test.

In a direct comparison we look to bound the sequence of interest, $\{a(n)\}_{n=1}^{\infty}$ directly with a reference sequence $\{b(n)\}_{n=1}^{\infty}$ . For example, the series $\sum_{n = 1}^{\infty} (n^3 + 2 n^2)^{-1}$ must converge since $(n^3 + 2 n^2)^{-1} \leq n^{-3}$ and the series $\sum_{n=1}^{\infty} n^{-3}$ converges by the integral comparison test.

Alternately, the sequence $1/n! \leq (n \times (n-1))^{-2}$ for all $n > 2$ . The series $\sum_{n=2}^{\infty} (n \times (n - 1))^{-2}$ will converge since $(n \times (n - 1))^{-2} = \mathcal{O}(n^{-2})$ , and we already know that the series $\sum_{n = 2}^{\infty} n^{-2}$ converges. The latter argument based on order of convergence is an example of a limit comparison test:

Limit Comparison Test

Given two nonnegative sequences, $\{a(n)\}_{n=1}^{\infty}$ , and $\{b(n)\}_{n=1}^{\infty}$ , compute the limit:

L = \lim_{n \rightarrow \infty} \frac{a(n)}{b(n)}

(8)

If $L < \infty$ and the series $\sum_{n=1}^{\infty} b(n)$ converges, then the series $\sum_{n=1}^{\infty} a(n)$ also converges.
If $L > 0$ and the series $\sum_{n=1}^{\infty} b(n)$ diverges, then the series $\sum_{n=1}^{\infty} a(n)$ also diverges.

In the first case the sequence $a(n)$ converges faster than, or as fast as $b(n)$ , so $a(n) = \mathcal{O}(b(n))$ . In the second case, $a(n)$ converges slower than, or as slowly as $b(n)$ .

The limit comparison test is often easier to use than the direct comparison test since it does not require an inequality, only matching orders of convergence.

Example¶

Suppose that $X \in \{1,2,3,4,...,\infty\}$ and $\text{PMF}(x) \propto g(x) = (1 + \frac{1}{2} x^2)^{-1.5}$ .

Is this a valid distribution? To check, try to normalize it:
$\sum_{x = 1}^{\infty} \left(1 + \frac{1}{2} x^2 \right)^{-1.5} = \text{ ?}$
(9)
We can normalize the distribtion as long as the series converges.
To show it converges, we could use either a direct, or a limit, comparison test.
- Direct Comparison: $(1 + \frac{1}{2} x^2)^{-1.5} \leq (\frac{1}{2} x^2)^{-1.5} = 2^{1.5} x^{-3}$ . The series $\sum_{x = 1}^{\infty} x^{-3}$ converges, so the series $\sum_{x = 1}^{\infty} (1 + \frac{1}{2} x^2)^{-1.5}$ must also converge.
- Limit Comparison: We saw, above, that $g(x)$ is bounded above by a multiple of $x^{-3}$ , so $g(x) = \mathcal{O}(x^{-3})$ . Try the comparison:
  $L = \lim_{x \rightarrow \infty} \frac{(1 + \frac{1}{2} x^2)^{-1.5}}{x^{-3}} = \lim_{x \rightarrow \infty} \frac{x^3}{(\frac{1}{2} x^2 + 1)^{1.5}}$
  (10)
  When $x$ is large, $x^2$ is very large, so will dominate the added +1 in the denominator. So stripping out all but the leading terms:
  $L = \lim_{x \rightarrow \infty} \frac{x^3}{(\frac{1}{2} x^2)^{1.5}} = 2^{1.5} \lim_{x \rightarrow \infty} \frac{x^3}{(x^2)^{1.5}} = 2^{1.5} \lim_{x \rightarrow \infty} \frac{x^3}{x^3} = 2^{1.5} < \infty.$
  (11)
  So, since $\sum_{x = 1}^{\infty} x^{-3}$ converges, our original series converges.
Does it admit a finite expectation? The expectation is finite if the series:
$\sum_{x = 1}^{\infty} x \left(1 + \frac{1}{2} x^2 \right)^{-1.5}$
(12)
converges. The function:
$\frac{x}{(1 + \frac{1}{2} x^2)^{1.5}} = \mathcal{O}(x \times x^{-3}) = \mathcal{O}(x^{-2})$
(13)
So, a limit comparison test against $x^{-2}$ would show that the expectation is a finite number.
Does it have finite variance? The variance is finite if the series:
$\sum_{x = 1}^{\infty} x^2 \left(1 + \frac{1}{2} x^2 \right)^{-1.5}$
(14)
converges. This time the sequence behaves like $x^{-1}$ for large $x$ , so we should expect it to diverge.
To show that it diverges, adopt a limit comparison test:
$L = \lim_{x \rightarrow \infty} \frac{x^2 (1 + \frac{1}{2} x^2)^{-1.5}}{x^{-1}} = \lim_{x \rightarrow \infty} \frac{x^3}{(\frac{1}{2} x^2 + 1)^{1.5}} = 2^{1.5} \lim_{x \rightarrow \infty} \frac{x^3}{x^3} = 2^{1.5}.$
(15)
Since the limit is finite, the sequence of interest converges as slowly as a harmonic sequence, so it diverges.

This is an example of a heavy-tailed discrete distribution. It is well-defined since its PMF is nonnegative and can be normalized, and has a finite expectation, but its standard deviation is infinite.

Ratio Tests¶

So far we’ve mostly focused on tests that compare to power laws. We can also compare to geometric series.

To compare to a geometric series, it is enough to show that $a(n+1)$ converges to some fixed multiple of $a(n)$ .

If $a(n+1) = r a(n)$ then $a(n + 2) = r^2 a(n)$ and $a(n+k) = r^k a(n)$ . So, if $a(n+1)$ approaches a fixed multiple of $a(n)$ , as $n$ diverges, then the sequence behaves like a geometric/exponential sequence for large $n$ . If it behaves like a geometric sequence, then it will obey the same convergence rules; converge if $|r| < 1$ , diverge if $|r| > 1$ .

To see whether $a(n+1)$ approaches a fixed multiple of $a(n)$ , evaluate the limiting ratio:

r = \lim_{n \rightarrow \infty} \frac{|a(n+1)|}{|a(n)|}.

(16)

If the limit exists, then the sequence $\{|a(n)|\}_{n=1}^{\infty}$ behaves like a geometric sequence with base $r$ for large $n$ .

The ratio test is most useful for sequences that involve products of factorials and exponentials. In the next chapter we will study series of the kind:

\sum_{n=0}^{\infty} \frac{1}{n!} t^n

(18)

as functions of $t$ . These series converge for all $t$ since they pass the ratio test:

r = \lim_{n \rightarrow \infty} \frac{\frac{1}{(n+1)!}t^{n+1}}{\frac{1}{n!}t^n} = \lim_{n \rightarrow \infty} \frac{n!}{(n+1)!} t = \lim_{n \rightarrow \infty} \frac{t}{n+1} = 0 < 1.

(19)

5.3 Series Convergence via Comparison Tests

Integral Comparison Test¶

Direct and Limit Comparison Tests¶

Example¶

Ratio Tests¶