Solving Geometric Series

I can never remember the closed-form solution for the sum of an infinite geometric series,

$a + ar + ar^2 + ar^3 + \dots \tag{1}$

However, there is actually a rather elegant way to quickly re-derive this result, which I discovered while working on probability puzzles in (Joshi et al., 2013). Let $s$ be the infinite sum in Equation $1$. Now subtract $rs$ from $s$:

$\begin{aligned} s &= a + ar + ar^2 + ar^3 + \dots \\ rs &= ar + ar^2 + ar^3 + ar^4 + \dots \\ &\Downarrow \\ s - rs &= a. \end{aligned} \tag{2}$

That’s it. All the terms cancel except for $a$, and we’re left with

$s = \frac{a}{1 - r}. \tag{3}$

Of course, this logic still applies when the series is finite:

$\begin{aligned} s &= a + ar + ar^2 + ar^3 + \dots + ar^{n} \\ rs &= ar + ar^2 + ar^3 + ar^4 + \dots + ar^{n+1} \\ &\Downarrow \\ s(1 - r) &= a(1 - r^{n+1}), \end{aligned} \tag{4}$

which gives us the standard result:

$s = \frac{a(1 - r^{n+1})}{(1 - r)}. \tag{5}$

Let’s look at a few applications of this trick.

Geometric distribution

When I discovered this well-known result, I was trying to re-derive the variance of a geometric random variable, since I could not remember it. In fact, computing both the mean and variance of a geometric random variable can be done using the same trick to construct the closed-form expression in Equation $3$.

Let’s setup the problem. Imagine I flip a coin with bias $p$ until I get a heads. Let $q \triangleq 1 - p$, and let $N$ denote the number of tosses until I get a heads. Then $N$ is a geometric random variable with parameter $p$. Let’s derive $\mathbb{E}[N]$ and $\mathbb{V}[N]$ without relying on basic properties of the geometric distribution, i.e. let’s use the trick in Equation $2$.

Mean

To compute the expectation, we write down all possible outcomes, weighted by their probabilities. The probability of flipping a heads in $N = 1$ flips is $p$; the probability of flipping a heads in $N=2$ flips is $q p$; and so forth. This gives us

$\mathbb{E}[N] = p + qp 2 + q^2 p 3 + q^3 p 4 + \dots \tag{6}$

Now let’s apply the above trick, subtracting $q \mathbb{E}[N]$ from the series:

$\begin{aligned} q \mathbb{E}[N] &= qp + q^2 p 2 + q^3 p 3 + q^4 p 4 + \dots \\ &\Downarrow \\ \mathbb{E}[N](1-q) &= p + qp + q^2 p + q^3 p + q^4 p + \dots \\ &\Downarrow \\ \mathbb{E}[N] &= 1 + q + q^2 + q^3 + q^4 + \dots \end{aligned} \tag{7}$

This is promising. We’ve greatly simplified Equation $4$. Now let’s just apply our trick again: $\begin{aligned} \mathbb{E}[N] &= 1 + q + q^2 + q^3 + q^4 + \dots \\ q \mathbb{E}[N] &= q + q^2 + q^3 + q^4 + q^5 + \dots \\ &\Downarrow \\ \mathbb{E}[N](1-q) &= 1 \\ &\Downarrow \\ \mathbb{E}[N] &= \frac{1}{p}. \end{aligned} \tag{8}$

And we’re done.

Variance

To compute the variance, $\mathbb{V}[N]$, we just need to compute the second moment $\mathbb{E}[N^2]$ since

$\mathbb{V}[N] = \mathbb{E}[N^2] - (\mathbb{E}[N])^2. \tag{9}$

Let’s apply the same trick as before:

$\begin{aligned} \mathbb{E}[N^2] &= p + qp 2^2 + q^2 p 3^2 + q^3 p 4^2 + \dots \\ q \mathbb{E}[N^2] &= qp + q^2 p 2^2 + q^3 p 3^2 + q^4 p 4^2 + \dots \\ &\Downarrow \\ \mathbb{E}[N^2] (1 - q) &= p + qp (2^2 - 1) + q^2 p (3^2 - 2^2) + q^3 p (4^2 - 3^2) + \dots \end{aligned} \tag{10}$

Since $a^2 - b^2 = (a + b)(a - b)$, we can simplify the squared differences as just $a + b$ since $a - b = 1$ when $a = b - 1$, as in Equation $10$. So the last line of Equation $10$ can be written as

$\begin{aligned} \mathbb{E}[N^2] (1 - q) &= p + qp 3 + q^2 p 5 + q^3 p 7 + \dots \\ &\Downarrow \\ \mathbb{E}[N^2] &= 1 + q 3 + q^2 5 + q^3 7 + \dots \end{aligned} \tag{11}$

This looks simpler. Again, we apply the trick:

$\begin{aligned} q \mathbb{E}[N^2] &= q + q^2 3 + q^3 5 + q^4 7 + \dots \\ &\Downarrow \\ \mathbb{E}[N^2](1 - q) &= 1 + q 2 + q^2 2 + q^3 2 + q^4 2 + \dots \\ &\Downarrow \\ \mathbb{E}[N^2] &= \frac{1}{p} + \frac{q 2}{p} + \frac{q^2 2}{p} + \frac{q^3 2}{p} + \dots \end{aligned} \tag{12}$

We’re almost done. Let’s apply the trick a third time!

$\begin{aligned} \mathbb{E}[N^2] &= \frac{1}{p} + \frac{q 2}{p} + \frac{q^2 2}{p} + \frac{q^3 2}{p} + \dots \\ q \mathbb{E}[N^2] &= \frac{q}{p} + \frac{q^2 2}{p} + \frac{q^3 2}{p} + \frac{q^4 2}{p} + \dots \\ &\Downarrow \\ \mathbb{E}[N^2] (1 - q) &= \frac{1}{p} + \frac{q}{p} \\ &\Downarrow \\ \mathbb{E}[N^2] &= \frac{1 + q}{p^2}. \end{aligned} \tag{13}$

Finally, we just plug this second moment into the equation for variance (Equation $9$), and simplify:

$\begin{aligned} \mathbb{V}[N] &= \mathbb{E}[N^2] - (\mathbb{E}[N])^2 \\ &= \frac{1 + q}{p^2} - \frac{1}{p^2} \\ &= \frac{1 - p}{p^2}. \end{aligned} \tag{14}$

And we’re done.

Note that if you do remember Equation $3$ but do not remember the mean or variance of the geometric distribution, you can use Equation $3$ after one application of the trick for the mean (Equation $7$) or after two applications of the trick for the variance (Equation $12$). The mean calculation is straightforward. To compute the variance, you simply add $2/p$ to both sides of the equation to get a series of the form in Equation $1$:

$\mathbb{E}[N^2] - \frac{1}{p} + \frac{2}{p} = \overbrace{\frac{2}{p} + \frac{2}{p} q + \frac{2}{p} q^2 + \frac{2}{p} q^3 + \dots}^{2/p^2} \tag{15}$

This can be easily solved to derive the last line of Equation $13$.

Die rolling game

Let’s look at another example. Imagine that Alice and Bob play a simple dice game. They take turns rolling a fair die, with Alice going first. Whoever rolls a $6$ first wins. What is the probability that Bob wins? We can express this probability as an infinite series, and use our trick to re-write it as a geometric series.

The probability that Bob wins on the first roll is the probability that Alice does not roll a $6$, but then Bob does. The probability that Bob wins on the second roll is the probability that neither Alice nor Bob win on the first round, Alice does not roll a $6$ on the second round, but then Bob does. And so forth. We can express this probability, call it $p$, as

$p = \left( \frac{5}{6} \right) \frac{1}{6} + \left( \frac{5}{6} \right)^3 \frac{1}{6} + \left( \frac{5}{6} \right)^5 \frac{1}{6} + \dots \tag{16}$

This isn’t quite a geometric series, but notice what happens if we multiply $p$ by $5/6$:

$\left( \frac{5}{6} \right) p = \left( \frac{5}{6} \right)^2 \frac{1}{6} + \left( \frac{5}{6} \right)^4 \frac{1}{6} + \left( \frac{5}{6} \right)^6 \frac{1}{6} + \dots \tag{17}$

Now we have two infinite series, one with odd powers and one with even powers. We can add them together to get a geometric series:

$p + \left( \frac{5}{6} \right) p = \left( \frac{5}{6} \right) \frac{1}{6} + \left( \frac{5}{6} \right)^2 \frac{1}{6} + \left( \frac{5}{6} \right)^3 \frac{1}{6} + \left( \frac{5}{6} \right)^4 \frac{1}{6} + \dots \tag{18}$

This isn’t quite the form of Equation $1$, but we can get it there easily by adding $1/6$ to both sides. We could, if we’d like, “turn the crank” of this trick on more time, but I’ll spare the reader and just use Equation $2$:

$\begin{aligned} p + \left( \frac{5}{6} \right) p + \frac{1}{6} &= \frac{1/6}{1 - 5/6} \\ &\Downarrow \\ p &= \frac{5}{11}. \end{aligned} \tag{19}$

This makes intuitive sense. The game is almost fair, but Alice has an advantage by going first.

Conclusion

This is a useful trick for quickly solving a geometric series if you do not remember the closed-form solution. The above derivations are a bit tedious, but they’re conceptually straightforward.

   

Acknowledgements

I thank Mattia Mariantoni for pointing out a typo near Equation $10$.