Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)

share|improve this question
1  
Are you edge cases inclusive or exclusive? I know your intention but I'm a nitpick "a random number between 0 and MAX_NUMBER" doesn't have to mean it includes 0 or MAX_NUMBER and then it would run forever. (consider: list all numbers between 1 and 4: would you answers: 2,3 or 1,2,3,4 ?) And I could make a perfectly valid random number generator that actually does output numbers between 0 and maxnumber, but the algorithm only outputs the numbers 2 and 5 purely random. –  Pieter B Nov 29 '12 at 9:09
    
Ignoring pseudo-randomness, this is similar to the classic Schrödinger's cat thought experiment. –  Sean Nov 29 '12 at 16:45
    
@Pieter B: It's inclusive of 0. –  Simon Campbell Nov 29 '12 at 18:27

4 Answers 4

up vote 7 down vote accepted

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.

share|improve this answer
    
The question says while(random != 0), so it terminates when it gets zero. So all it needs is a random sequence that never contains 0. If the range is big enough, such sequence would even look random to most tests. –  Jan Hudec Nov 29 '12 at 8:19
    
Yep, sorry. Reading mistake. –  AlexBottoni Nov 29 '12 at 8:25
    
Thank you. I had accidentally put 0 as an example string of random numbers (which would satisfy the exit condition, contrary to the argument). It has been changed to '1' so that it makes sense and supports that argument. –  Simon Campbell Nov 29 '12 at 9:02
    
Mathematically speaking, it could run forever with probability 0. See my answer. –  iCanLearn Nov 29 '12 at 9:22

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.

share|improve this answer
4  
Well, this is getting subtle :-) Given infinite time, the code would almost surely terminate. See: en.wikipedia.org/wiki/Almost_surely . The probability of it running forever is infinitely near to 0 (but not 0). This is a logical subtility that torments mathematicians since the birth of analysis. See: en.wikipedia.org/wiki/Asymptotic_analysis . –  AlexBottoni Nov 29 '12 at 10:40
    
Ok, this really is getting subtle. :) The way they taught us is that if something is non-negative and smaller than epsilon for any epsilon > 0, it must be 0. I guess you could make a distinction between zero and infinitely near to zero, but when exactly do you need that distinction? I don't know, to me it sounds the same. Why do we say that sum of a (for example) geometric series is equal to something, and not infinitely near something? –  iCanLearn Nov 29 '12 at 11:15
    
As I told in my previous message, this is the fundamental issue of infinitesimal calculus and torments mathematicians since a very long time: en.wikipedia.org/wiki/Infinitesimal_calculus and en.wikipedia.org/wiki/Mathematical_analysis . Every time you have to deal with infinitesimals quantities ( en.wikipedia.org/wiki/Infinitesimal ), you have to face it. It makes the difference between "guaranteed" (as in the OP question) and "almost sure". Mathematically speaking, you can get an infinite sequence of 0 (or !0) from a random process. It is just... very improbable. –  AlexBottoni Nov 29 '12 at 13:05
    
Another detail: "almost surely" becomes "surely" if you define "infinite time" as "a period of time long at least enough to consume each and every different entropic state of the system at least once, being the system our universe". In this case, by definition, the code of the OP will terminate. Unfortunately, this definition is related to (a specific field of) cosmology, not to mathematics. Mathematically speaking, "infinite time" just means "an infinite series of seconds". In this case, you can still have an infinite sequence of 0 from a truly random generator. –  AlexBottoni Nov 29 '12 at 13:15
    
@iCanLearn: Alex Bottoni's point is further strengthened by the infinite monkey theorem you linked to, which states explicitly that the correct term is "almost surely". It's not really probably 0, it is probability 1/infinity. If I run infinite such random programs, some of them would terminate on each iteration of the loop, but (almost surely) not all of them. –  Brian Nov 29 '12 at 14:40

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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