Say I have a simple program that has the pseudocode like this:

min = 1
max = 100
c = 5
random = randomInt(min,max)
while(c != random):
    random = randomInt(min,max);

Theoretically, from what I understand, I cannot guarantee this will halt. However, is this true for both PRNGs and say, random integers generated using atmospheric noise? Is there a difference? And by convention, can I say this will "almost surely" halt (probability 1), but still cannot guarantee this? I'm still trying to wrap my mind around the edge case of a program with an almost sure chance of halting, and how this is viewed from a computational perspective.

  • $\begingroup$ If you use genuinely random numbers, the program will halt almost surely (i.e., with probability 1). $\endgroup$ – Yuval Filmus Nov 18 '17 at 11:30
  • $\begingroup$ @YuvalFilmus why would this be different from PRNGs exactly? $\endgroup$ – rb612 Nov 18 '17 at 11:41
  • 1
    $\begingroup$ It depends on the PRNG. The PRNG might not go over all possible values, for example, or it might be guaranteed to go over all possible values. $\endgroup$ – Yuval Filmus Nov 18 '17 at 11:53

For deterministic algorithms, the statement "Algorithm $A$ halts on input $x$" is well defined. However, when $A$ is randomized (i.e. has access to some random source during its computation) this question becomes meaningless, as you need to know what was the outcome of the random source in order to answer it.

You can ask "does $A$ always halt on $x$", i.e. does it halt for every possible output of the random source. In your case, assuming the source produces uniformly distributed elements in the given range, the answer is no, since e.g. the infinite sequence "444..." is a possible outcome of the source, and this will cause $A$ to never halt.

However, "Algorithm $A$ halts on input $x$" is now an event, i.e. it is a subset of your sample space (we associate this event with the set of random outputs who cause $A$ to halt). Events have probabilities, so you can ask "What is the probability that $A$ halts on $x$"? If your source is uniform, then the probability that your algorithm doesn't halt is $p=\prod\limits_{i=1}^\infty\left(\frac{99}{100}\right)^i=0$. So in your case it is correct to say that the algorithm halts with probability $1$, but it is incorrect to say it always halts.

As for whether or not the randomness source matters, the answer is definitely yes. Consider the source which first chooses a number from the range uniformly at random, and then remembers it and outputs it to you in any later request (i.e. the source has memory, and different outcomes are not independent). In that case, your algorithm does not halt with probability $\frac{99}{100}$. For a source which always outputs $5$, it is true to say the the algorithm always halts (and not only with probability $1$, which is a weaker statement).


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.