Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random Number Generator

  1. Jul 3, 2006 #1
    I am just curious. If I have a random number generator, eventually, if I wait long enough all possible numbers should began to repeat. Or would the numbers not repeat? For example, if say the first hundred numbers were totally random 455688132547... etc. would the machine eventually repeat the numbers? If so, how would I go about calculating an approximation of when they'd repeat?
    Anyway, hope that all made sense.
     
  2. jcsd
  3. Jul 4, 2006 #2
    Sure the numbers will repeat, but the question is just how many digits are you talking about? Now at dice numbers run from 2 to 12, 7 is the most frequent number. It is not uncommon, not that uncommon for 7 to repeat 3 or even 4 times in a row. Sure, not like everytime, but you keep playing and YOU WILL SEE SUCH REPEATS!

    To make a rough estimate, I guess a throw of dice may take only 15 seconds. So that would give 4 throws in a minute. The 7 comes up 1/6 of the time, and four of them every 1296 throws. So that amounts to 5.4 hours of actual play! Now, of course, at the table there is time spent changing dealers, so slower period exists, and probably faster ones too. Of course, your play could be over days or weeks, but certainly if what we are talking about is an average of 5.4 hours of actual play, you don't have to play that game for very long before it may happen!

    The trouble with these repeating 7s is they are the bane of the wrong better, who bets against the house. On the pass line, when you first start, the right player will automatically win if a 7 is thrown. (Rather than lose as is usual with a 7.) If the wrong better can get his number, (4,5,6, 8,9,10) he is likely to win because the shooter will probably throw a 7 before hitting the wrong better's number again. Since wrong betters have this advantage once they have their number, they may begin by betting heavy, because otherwise they will have to give odds if they want to add to their bet since with their number the game is now in their favor.) The true bane of being a wrong better is that a series of 7s might occur before he can get his number, then instead of rejoicing over immediate wins, he has immediate losses. (If this happens three times in a row, he may be cured of betting wrong.)

    The matter in general is discussed by the mathemtician and philosopher Nassin Nicholas, writer of "Fooled by Randomness." He asks what happens, "When the black swan alights"? (While some have compaired them to unicorns, it's not true, black swans do exist.) http://www.fooledbyrandomness.com/ I quote: NNT is the Dean’s Professor in the Sciences of Uncertainty at the University of Massachusetts at Amherst. He is also an essayist, belletrist, literary-philosophical-mathematical flâneur, and practitioner of uncertainty (“mathematical trader”) focusing on the attributes of unexpected events, with a focus on extreme deviations, the “Black Swans” (i.e. outliers), their unpredictability, and our general inability to forecast.

    Again, what is involved in the problem of kuahji is the range, R, of the numbers involved. Take Pick 3 there are 1000 numbers involved, 000 to 999. So that a reapeat of a GIVEN NUMBER would be 1/million, but normally what is being sought is the repeat of ANY NUMBER, and that is just 1/1000 or the range of the numbers in question. So if we suppose that Pick 3 is played twice a day for 6 days a week, we should expect that after about 83 weeks we would see the same number come up twice in two successive drawings. If one has the time or inclination, he could check this out!
     
    Last edited: Jul 4, 2006
  4. Jul 4, 2006 #3
    Sure?
    Well in principle one could make a random number generator that does not repeat.
     
  5. Jul 4, 2006 #4

    mathman

    User Avatar
    Science Advisor

    Random number generators, as normally thought of, are programs on digital computers, where numbers have a finite number of bits. Therefore there are only a finite number of possibilities for numbers out of the generator. As a result, the generator must eventually repeat numbers it had turned out previously.
     
  6. Jul 4, 2006 #5
    Then I suppose I do not think normally :blushing:

    Furthermore a true random number generator, assuming such a device would exist, that would never give any duplicate numbers would most certainly not be a true random generator.
     
    Last edited: Jul 4, 2006
  7. Jul 4, 2006 #6

    selfAdjoint

    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.
     
  8. Jul 4, 2006 #7
    Well not quite.
    For instance it is not true that if a random generator is not periodic it must be true random.
    Being periodic is just one of the criteria that disqualifies a generator as random. :smile:
     
  9. Jul 4, 2006 #8
    I am an advanced Programmer in Vbscript and in order to have what's called a true random number generator you'd have to deal with infinity.

    You can not deal with infinty on a system that requires a time limit therefore you can not have a true random number generator but you can give it very large odds.

    I can build you a true random number generator but it would never stop functioning and freeze your system.
     
  10. Jul 5, 2006 #9

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You cannot implement a true random number generator entirely on a digital computer. The best you can do is a "pseudo-random number generator," which, as has been said, will eventually repeat. This is because computer programs are deterministic, and can do no better than shuffling bits in a complex (yet not random) way.

    There are, however, many sources of true randomness available in the physical world. The voltage across a temperature-sensing diode in the processor, the time between successive user keystrokes, the receipt of random broadcast packets on a network interface, etc. are all random enough, at least in aggregate, for most cryptographic purposes. A random-number generator based on such sources of true randomness will never repeat.

    - Warren
     
  11. Jul 5, 2006 #10
    It depends on what you mean by "repeat". Any random number generator must pick over a finite set, so lets say you want to generate random integers from 1-100. A pseudorandom number generator would repeat it's sequence infinitely many times. A truly random number generator could never be guaranteed to repeat, but it must. Any sequence it generated once would be generated again later, but only given infinite time. Given finite time, the probability of repeating a sequence of length n starting from a given point would be (1/100)^n, same as it was for being generated the first time.
     
  12. Jul 5, 2006 #11

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Who cares? Why don't we keep the discussion to things that are physically realistic?

    - Warren
     
  13. Jul 5, 2006 #12
    Hmmm, this is the Mathematics / Number theory section right? :smile:
     
  14. Jul 5, 2006 #13

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Random number generators, including those implemented on computers, are rather physical things. The qualities being discussed -- repitition, for example -- depend on the actual physical nature of their implementation.

    - Warren
     
  15. Jul 5, 2006 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You want to do it mathematically? Define random then. What is the sample set, and what is the probability distribution on that sample set, i.e. what are the measurable subsets, the sigma algebra, whatever you choose to call it.

    Integer values? That doesn't have a uniform distribution. The interval [0,1] with the uniform measure? Then you're into all kinds of issues as to what it means to actually sample a single element from a continuous distribution. Remember, such things are purely mathematical constructs, and only model of what we find in the real world.
     
    Last edited: Jul 5, 2006
  16. Jul 5, 2006 #15
    Hmmm, well the digits of PI and e are quite random aren't they.
     
  17. Jul 5, 2006 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    That isn't a good enough definition. There are many interpretations of that sentence.

    What is true is that pi is believed to be normal (no proof exists) and that means something very specific, so its *digits* are believed to be 'random' in the sense of 'normal' (see e.g. wolfram for an explanation). If you wanted to generate a 3 digit string at random then sure picking some 3 digit string from pi would create a random (conjecturally) 3 digit string, but it is not producing a random number (how many digits in the string should you pick? And that doesn't even then begin to address what it means to pick a string at random).
     
    Last edited: Jul 5, 2006
  18. Aug 25, 2006 #17
    With random number generators, a quickly built one will often generate a series like 174891029174891029174891029174891029, where it repeats forever. Often, though, it is a long time before a repitition occurs. A good random number generator is designed to not have repitition as obvious as that, in fact a very good random number generator has no repitition that goes on forever. So, yes, if you took the output of some random number generators, they would repeat forever, and for some they wouldn't ever start repeating forever.
     
  19. Aug 26, 2006 #18

    0rthodontist

    User Avatar
    Science Advisor

    Any pseudo-random number generator that is written on a computer with a finite amount of memory must output a sequence that a repeating tail. This is because the computer only has a finite number of states it can take, so it must repeat some state eventually, and once it does that it gets locked into a loop of states which repeatedly outputs the same finite string of numbers.
     
  20. Aug 26, 2006 #19

    HallsofIvy

    User Avatar
    Science Advisor

    Okay, now you need to define "random" and "quite random"! I don't see how that responds to
     
  21. Aug 26, 2006 #20

    -Job-

    User Avatar
    Science Advisor

    Computers can be made to output an arbitrarily large randomish number, since it's not really required that the whole number be kept in memory. For example, an algorithm that outputs the digits of a random number in batches of k random digits only keeps at most k digits in memory. The difficulty is in deciding when to stop outputting the number. After how many digits will the computer stop? It should be a random number of digits. To be a perfect random generator the probability of stopping at the nth digit should be the same as that of stopping at the (n+1)th digit, approximately 0, which is not really feasible.
    Unless perhaps we start the computer and let it naturally come to a stop (i.e. due to destruction, insufficient resources, etc). If the universe is truly random, then the system will be a true random number generator.
     
    Last edited: Aug 26, 2006
  22. Aug 26, 2006 #21

    0rthodontist

    User Avatar
    Science Advisor

    It is necessary to have at least as many states in the computer as the length of the repeating tail of the sequence. I am using the following kind of model:
    1. Computer outputs a number based deterministically on its state, of which there are a finite number
    2. Computer moves to a new state, which is based deterministically on its previous state. Goto 1
    With finite memory eventually the path of states, and therefore the string of numbers that are output, will fall into a cycle. If the computer's states at any time become xaya, where a is a single state and x and y are strings of states, then they must repeat xayayaya... and the output numbers will also repeat since there can be only one number per state.
     
  23. Aug 26, 2006 #22
    Actually, about the fact that once it passes a state twice it will get locked in a cycle, that is false. If you think about any irrational number, and figure out a way to calculate the next digit quickly, where it doesn't slow down based on number of numbers already computed, it will never give a repeating sequence. That would be an easy way to make a random number generator. In that case it would not repeat. It may hit a similar state where it puts out the same number, but it would be possible to make a random number generator that never gets locked in a cycle.
    I thought up a quick random number generator that would never get locked in a cycle. You would start with the first digit of tan(1), rounded, and the second number would be the rounded second digit of tan(1), making a list of random values like:
    round(tan(1))
    round(tan(1)*10)-round(tan(1))
    round(tan(1)*100)-round(tan(1)*10)-round(tan(1))
    and so on...
    This would never get locked in a repeating state, since tan(1) is irrational. I am also trying to make one that runs fast and doesn't repeat.
    Also, to stress the point that a random number generator that doesn't repeat doesn't have to slow down with each digit, you could make one that takes the square root of 2.1428304820483 using a algorithm that doesn't slow down during each digit. If you research, there are a lot of methods to take a square root that don't slow down with each digit, and some don't need knowledge of the rest of the digits already calculated, just the last few.
    The only problem with ones that don't repeat is they probably run slowly.
     
    Last edited: Aug 26, 2006
  24. Aug 27, 2006 #23

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    To calculate an arbitrary number of digits would take an unbounded amount of memory. Of course it may be possible to calculate with a finite amount of internal memory plus the Turing machine tape output, but that's still an unbounded number of internal states (tape + memory).
     
  25. Sep 9, 2006 #24
    I don't see that a pseudo-random number generator need necessarily be periodic in principle - that depends on the seed and the algorithm for each random number generated.

    This applies if the computer algorithm is completely digitally self-contained with a finite number of internal states and takes no outputs from the external world. Add an interface to the computer so that it can utilise information from the outside world in its random number generation algorithm, and your potential number of states is as large as you like.

    Best Regards
     
    Last edited: Sep 9, 2006
  26. Sep 9, 2006 #25

    0rthodontist

    User Avatar
    Science Advisor

    True--or do something drastic like increase the memory by a gigabyte or two every million years.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook