0
$\begingroup$

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.

enter image description here

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.$$

$\endgroup$
  • 1
    $\begingroup$ Many problems in calculating time complexity produce geometric series. In that case, it is not a tool that is being used but the problem to solve. Maybe you mean techniques like generating functions? $\endgroup$ – Derek Elkins Jan 16 '18 at 0:07
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Feb 15 '18 at 9:19
  • $\begingroup$ If the algorithm seems to exhibit a geometric distribution, you better use geometric series in its analysis. So what's the real question here? $\endgroup$ – Raphael Feb 15 '18 at 9:20
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.