Geometric series

Level FundamentalDifficulty ★★★★★Concept⌖ Open in the map

What is it?

$\sum_{k\ge0} r^k = \frac{1}{1 - r}$ for $|r| < 1$ . The one series everyone can sum in closed form — and the one behind dynamic arrays, divide-and-conquer recurrences and the discounted rewards of reinforcement learning.

Intuition

Multiply $S = 1 + r + r^2 + \dots$ by $r$ and subtract: everything cancels except the 1, so $S(1 - r) = 1$ . When $r = 1/2$ : $1 + \frac12 + \frac14 + \dots = 2$ — the total is dominated by the first terms, which is why the last level of a halving recursion costs as much as all the rest.

Formulas

$\sum_{k=0}^{n-1} r^k = \frac{1 - r^n}{1 - r}, \qquad \sum_{k=0}^{\infty} r^k = \frac{1}{1 - r}\ \ (|r| < 1)$; $G_t = \sum_{k=0}^{\infty}\gamma^k r_{t+k} \le \frac{r_{\max}}{1 - \gamma}$
discounted return in reinforcement learning

Example

A dynamic array doubles its capacity when full. Inserting $n$ elements copies at most $1 + 2 + 4 + \dots + n/2 < n$ elements in total — $O(1)$ amortized per insertion. With growth factor 1.5 the bound is $\frac{1}{1 - 2/3} = 3$ copies per element.

Where it shows up in computing

Algorithm analysis and complexity★★★★★fundamentalScientific computing and algorithms
Amortized analysis of dynamic arrays and the master theorem cases are geometric sums.
Queueing theory and performance★★★★★frequentOptimization and systems
In an M/M/1 queue the number of customers is geometric: $P(N = n) = (1 - \rho)\rho^n$ .

Where it shows up in AI

Reinforcement learning★★★★★fundamentalAI and machine learning
Discounting with $\gamma < 1$ makes the infinite return a convergent geometric-type series.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

What depends on it

Exercises

1AI

An agent gets reward 1 every step forever, with $\gamma = 0.99$ . What is the return? What is the "effective horizon"?

Solution

$\sum 0.99^k = \frac{1}{0.01} = 100$ . Rewards beyond about $\frac{1}{1-\gamma} = 100$ steps contribute little: the effective horizon is ~100 steps.