Why and how geometric series are used for proofs?

Question

I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for proofs? Can I transform problems to fit to geometric series?

For example the time complexity of this simple function to get a random prime is estimated by a geometric series, I don't see this is naturally (or rather intuitively) a geometric series.

The number of primes is guessed by $m / ln(m)$, so the expected value is $$\sum_{i=1}^\infty i\left(1 - \frac{1}{\ln m}\right)^{i-1} \frac{1}{\ln m} = \frac{1}{\ln m} \cdot \frac{1}{1/(\ln m)^2} = \ln m.$$

Answer 1

The pattern appears often because many randomly controlled loops behave like a series of coin flips!

Consider this sketch:

while P(state)
    do(state)

If the different evaluations of P are stochastically independent and identical (i.i.d.), the probability of the loop executing for $k$ times is

$\qquad\displaystyle \operatorname{Pr}(\mathtt{P(state) == false}) \cdot \sum_{i=0}^k \operatorname{Pr}(\mathtt{P(state) == true})^{k}$;

this is exactly the probability weight of a geometric distribution. Therefore, it will appear in any analysis.

Many loops do not fall into this pattern, and then you will see other sums or recurrences during the analysis.

Answer 2

Okay, this is the first case of my comment. This isn't a "tool"; this is simply the formula that comes up when you try to estimate the expected time complexity. Or more precisely, the expected number of iterations of the loop.

The $\frac{m}{\ln m}$ estimate for the number of primes less than $m$ comes from the prime number theorem. If we uniformly pick a number from $\{2,\dots,m\}$, then the probability that it will be prime is $\frac{1}{\ln m}$. The probability that it won't be prime is then $1-\frac{1}{\ln m}$. The probability that we will find a prime in exactly $i$ iterations is the probability that we fail to find a prime in the first $i-1$ iterations, and then find one on the $i$th iteration. Since the selection of the random numbers are (assumed) independent, this is $(1-\frac{1}{\ln m})^{i-1}\frac{1}{\ln m}$. Let $S$ be the number of iterations the algorithm takes. The probability that the algorithm takes exactly $i$ iterations, i.e. $S=i$, is $$P(S=i)=\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$ except $P(S=0)=0$ since the algorithm always goes through at least one iteration.

By definition of expectation, the expected value of the number of steps is $$\mathsf{E}[S]=\sum_{i=0}^\infty SP(S=i)$$ Expanding this out, we get $$\mathsf{E}[S]=\sum_{i=1}^\infty i\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$

In other words, exactly the geometric series you mention. At no point did I attempt to get the problem in the form of a geometric series, and there is no guarantee that it would be of that form. Instead, you can just start from the definition of expected value which is what you're trying to show. Then you see you need the probability of $S=i$ which happens to have a form that leads to the expectation being a geometric series. That said, if each iteration of a loop independently has a constant probability of terminating, which is common, then you will get a similar geometric series. If the probability changed with each iteration or the probabilities were correlated, then you would not end up with a geometric series in general, but the approach to the solution would be just the same, though actually simplifying the resulting infinite series in those cases might be quite difficult or impossible.