Solving Geometric Series

I describe a useful trick for computing geometric series without closed-form solutions.

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

a+ar+ar2+ar3+(1) 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 ss be the infinite sum in Equation 11. Now subtract rsrs from ss:

s=a+ar+ar2+ar3+rs=ar+ar2+ar3+ar4+srs=a.(2) \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 aa, and we’re left with

s=a1r.(3) s = \frac{a}{1 - r}. \tag{3}

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

s=a+ar+ar2+ar3++arnrs=ar+ar2+ar3+ar4++arn+1s(1r)=a(1rn+1),(4) \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=a(1rn+1)(1r).(5) 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 33.

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

Mean

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

E[N]=p+qp2+q2p3+q3p4+(6) \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 qE[N]q \mathbb{E}[N] from the series:

qE[N]=qp+q2p2+q3p3+q4p4+E[N](1q)=p+qp+q2p+q3p+q4p+E[N]=1+q+q2+q3+q4+(7) \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 44. Now let’s just apply our trick again: E[N]=1+q+q2+q3+q4+qE[N]=q+q2+q3+q4+q5+E[N](1q)=1E[N]=1p.(8) \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, V[N]\mathbb{V}[N], we just need to compute the second moment E[N2]\mathbb{E}[N^2] since

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

Let’s apply the same trick as before:

E[N2]=p+qp22+q2p32+q3p42+qE[N2]=qp+q2p22+q3p32+q4p42+E[N2](1q)=p+qp(221)+q2p(3222)+q3p(4232)+(10) \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 a2b2=(a+b)(ab)a^2 - b^2 = (a + b)(a - b), we can simplify the squared differences as just a+ba + b since ab=1a - b = 1 when a=b1a = b - 1, as in Equation 1010. So the last line of Equation 1010 can be written as

E[N2](1q)=p+qp3+q2p5+q3p7+E[N2]=1+q3+q25+q37+(11) \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:

qE[N2]=q+q23+q35+q47+E[N2](1q)=1+q2+q22+q32+q42+E[N2]=1p+q2p+q22p+q32p+(12) \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!

E[N2]=1p+q2p+q22p+q32p+qE[N2]=qp+q22p+q32p+q42p+E[N2](1q)=1p+qpE[N2]=1+qp2.(13) \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 99), and simplify:

V[N]=E[N2](E[N])2=1+qp21p2=1pp2.(14) \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 33 but do not remember the mean or variance of the geometric distribution, you can use Equation 33 after one application of the trick for the mean (Equation 77) or after two applications of the trick for the variance (Equation 1212). The mean calculation is straightforward. To compute the variance, you simply add 2/p2/p to both sides of the equation to get a series of the form in Equation 11:

E[N2]1p+2p=2p+2pq+2pq2+2pq3+2/p2(15) \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 1313.

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 66 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 66, 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 66 on the second round, but then Bob does. And so forth. We can express this probability, call it pp, as

p=(56)16+(56)316+(56)516+(16) 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 pp by 5/65/6:

(56)p=(56)216+(56)416+(56)616+(17) \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+(56)p=(56)16+(56)216+(56)316+(56)416+(18) 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 11, but we can get it there easily by adding 1/61/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 22:

p+(56)p+16=1/615/6p=511.(19) \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 1010.

  1. Joshi, M. S., Denson, N., & Downes, A. (2013). Quant job interview questions and answers. Pilot Whale Press Parkville.