Is code that terminates on a random condition guaranteed to terminate?

Question

If I had a code which terminated based on if a random number generator returned a result (as follows), would it be 100% certain that the code would terminate if it was allowed to run forever.

while (random(MAX_NUMBER) != 0): // random returns a random number between 0 and MAX_NUMBER
   print('Hello World')

I am also interested in any distinctions between purely random and the deterministic random that computers generally use. Assume the seed is not able to be known in the case of the deterministic random.

Naively it could be suggested that the code will exit, after all every number has some possibility and all of time for that possibility to be exercised. On the other hand it could be argued that there is the random chance it may not ever meet the exit condition-- the generator could generate 1 'randomly' until infinity.

(I suppose one would question the validity of the random number generator if it was a deterministic generator returning only 1's 'randomly' though)

Answer 1

By definition, it must be possible to get an infinite sequence of 0 in a really casual ("random") sequence so this program must be able to run forever. Otherwise, this could not be considered a random sequence from a mathematical/statistical point of view. You cannot rule out a specific, legitimate sequence and still consider your system a really random one.

An infinite sequence of 0 would fail to be recognized as a legitimate random sequence by most if not all the standard statistical methods of analysis we use in practice but, despite this, it actually is a perfectly legitimate random sequence for the theory.

This in theory.

In practice, we all know that, given enough time, we will get a number different from 0 and the program will terminate.

The random generator used by computers are considered to be random when a reasonably long sequence of number they generate (say, some million numbers...) cannot be distinguished from a really casual one when analyzed whith standard statistical tools. That is: we do not really know if the sequence of number they generate is really random but we cannot tell it apart from a genuine random sequence when we analyze a finite-length sample.

This is a big difference because... given a longer sequence you can discover that your sequence is not really random and can be reproduced. In cryptography, this would be a very bad discovery.

As I said above, the statistical methods of analysis we use would not recognize an infinite sequence of 0 as a legitimate random sequence. Nevertheless, this is a failure of the analytical methods, not of the random generator. Mathematically speaking, you cannot rule out such a sequence just because it does not satisfy your analytical system or your personal taste. If you do not have a real, mathematical reason to rule it out, it is legitimate.

Answer 2

Yes, given infinite time the code would surely terminate. See infinite monkey theorem. The probability of it running forever is 0, there's a mathematical proof for that.
That's if the numbers were truly random. I don't know enough about random number generators to tell you more than that.

Answer 3

To answer the other part of your question (regarding the implementation of random) then I would say it depends entirely on the implementation. Divide implementations into pseudo-random number generators and "true" random number generators.

One popular implementation of a pseudo-random number generator is a linear feedback shift register (LFSR). These actually generate repeatable sequences of numbers and they are only random in the sense of fulfilling a random distribution. There is, in fact, an entity called a "maximum length LFSR" that is guaranteed to cycle through all the values. In that case, your code would certainly terminate.

"True" random number generators can't be implemented only in software. They need some kind of fundamental "noise" source: typically a reverse-biased PN junction with an amplifier, or a radio tuned off station run into a sound card, where you sample the smallest bit. Sometimes there's a source built into the operating system that tries to generate random bits using entropy such as disk I/O times, keyboard press times, etc. In that case, you're talking about whether a truly (quantum) random physical process will ever generate a zero, and for that perhaps we need to consult a physicist.

Also realize that even a truly random implementation may not be truly random if there's a subtle flaw that causes it never to generate some subset of numbers.

Answer 4

I think all code is guaranteed to terminate, since eventually entropy will eliminate all energy differentials, making it impossible for logic circuits to change state. However, one of the attributes of a truly random number generator is that it may never produce a particular number, just as it may produce infinitely-long runs of one particular number. So the answer to your question is "yes, but not because it meets your exit criterion".