Random algorithm termination

Question

Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On the one hand you can show that $\lim_{n \to \infty}p^n = 0$, so it must terminate at some point before infinity. On the other hand it also seems reasonable to say that it is possible for the algorithm to call itself repeatedly indefinitely. What is the correct interpretation?

Answer 1

The question "Does it terminate?" isn't well-formed. You need to define more precisely what you mean by that question before it can be answered.

• Is it guaranteed to terminate on all possible execution traces? No. There exists an execution trace where it never terminates.

• Does it terminate with probability one? Yes. If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.

• Is the expected number of repetitions until termination finite? Yes. If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).

So, the answer to the question depends upon precisely which of those questions you meant to ask. Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely. For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness). Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.