Jump to content


Photo
- - - - -

Random Number Series


  • Please log in to reply
28 replies to this topic

#1 petrushkagoogol

petrushkagoogol

    Understanding

  • Members
  • 387 posts

Posted 23 July 2017 - 07:58 AM

Is it possible to have a computer program that can find the nth term of a random number series, with a single algorithm ?  :bow: 


Edited by petrushkagoogol, 23 July 2017 - 07:59 AM.


#2 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 23 July 2017 - 10:17 AM

Yes, but either you've included a lot of specifications here that are irrelevant or there are things about your question you're not explaining.

 

 

An algorithm must be seen to be believed, :phones:

Buffy



#3 phillip1882

phillip1882

    Thinking

  • Members
  • 646 posts

Posted 09 September 2017 - 04:59 PM

yes and no. if you're asking, given a finite set of numbers, can you produce a sequence that will give the nth term, but not necessarily the next term after the end of the series. then the answer is yes. for example, you can list the first 30 primes and then give a polynomial equation that goes through those 30 primes but wont necessarily give the 31st prime.

if however your asking, given a sequence of numbers can you predict with absolute certainty  what the next number is going to be, the answer is no.



#4 scherado

scherado

    Questioning

  • Banned
  • 207 posts

Posted 10 September 2017 - 04:44 AM

Is it possible to have a computer program that can find the nth term of a random number series, with a single algorithm ?  [emoticon removed] 

.
Can you write a program that generates a string of random numbers?

Edited by scherado, 10 September 2017 - 04:45 AM.


#5 petrushkagoogol

petrushkagoogol

    Understanding

  • Members
  • 387 posts

Posted 10 September 2017 - 09:10 AM

.
Can you write a program that generates a string of random numbers?

 

Most programming languages have a function like RND(x) which generates a random number, use this iteratively and you get a series.



#6 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 10 September 2017 - 11:00 AM

Most programming languages have a function like RND(x) which generates a random number, use this iteratively and you get a series.


Right, which is an O(n) algorithm. You haven't specified whether this is part of the algorithm or not, but even if it isn't you'd still need to read it from a file, which is also O(n) and of course the thing to do is simply stop after reading the nth number in the input.

If you're asking about this for data generated outside of the algorithm such that it can be assumed to already be in memory, the issue is the data structure it's stored in. If it is an array, you just address it directly, which is an O(1) algorithm, whereas if it is a linked list, you loop to get to the nth object, which is also O(n). There are other possibilities that will get you to O(log n) (e.g. a tree-structure).

If this seems trivial, it is, because your problem statement is still not clear.

What are you trying to accomplish?


As a reporter you tend to seek coherence from your subject or your source - it all needs to add up and make sense. In truth, in reality, there's often a great deal of murkiness and muddiness, confusion and contradiction, :phones:
Buffy

#7 scherado

scherado

    Questioning

  • Banned
  • 207 posts

Posted 10 September 2017 - 01:43 PM

Most programming languages have a function like RND(x) which generates a random number, use this iteratively and you get a series.

.
I asked that question to determine whether you knew the meaning of "random." I didn't ask the right question.

More than once--as I had to learn more than one programming language--my professors asked us to write a program that generated some small number of random numbers.

Since that time, some decades, I have heard countless times people use the word "random" when they meant no such thing.

The task the professors asked us to do was create an algorithm to generate X random numbers and write a program based on that algorithm in the subject language.

Do you know how to generate a random number repeatedly? Repeatedly because your algorithm can't produce a pattern no matter how many times the program, on which it is based, is run.

#8 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 10 September 2017 - 03:57 PM

Do you know how to generate a random number repeatedly? Repeatedly because your algorithm can't produce a pattern no matter how many times the program, on which it is based, is run.

 

This isn't strictly true, and kind of misleads what a pseudo-random function (e.g. RND(seed)) is designed to do. The Original Post really didn't specify the source of the numbers, although the Original Poster then clarified he was referring to pseudo-random numbers from a library. 

 

"Truly random" numbers need to come from a truly random source, and there is hardware you can get that uses electronic circuits to generate numbers from various physical properties of those circuits to guarantee randomness. These are not a big deal and are not very expensive and the newer ones just plug into a USB port.Obviously if you want to ensure "true randomness" in real time, then you want to use one of these.

 

"Pseudo-random" numbers are generated by an algorithm, and while often denigrated because they are not "truly random," they are incredibly useful where you want to have the *same set* of "random" numbers as input to different algorithms to test/compare the performance of those algorithms. They do this by using the seed argument as a mechanism for starting the sequence, and they normally guarantee that if you use the same seed, you'll get the exact same sequence of numbers: this is a feature, not a bug. It means that you don't actually need to store your sequence and read it in for each algorithm run, you can just call the function and get a repeatable sequence.

 

Now of course you can use them to be "a lot like" a "true random number generator" by picking a random seed (most of us pull the current millisecond counter from the system clock at the time the function is first called to do this). As long as the algorithm is "pretty good" you should in most cases get "pretty random" numbers.

 

Now what's not the case is the notion that there will be no repetitions of sequences in the numbers you generate. This should be obvious in the case where your range for the random numbers is say 0-10 and your definition of "repetition" is any two numbers in a row, you're guaranteed to have a repetition somewhere in the first 100 or so numbers you generate (proof left as an exercise for the reader). But even if you expand the range size you're using or the "repetition length" you've defined, you just reduce the *probability* of finding a repetition.

 

There are two things to be noted about this:

  • The "accuracy" of your generator is primarily dependent on it's ability to produce the desired distribution values over time: if you're shooting for a Poisson or a Bell curve distribution, your algorithm's output sure as heck ought to match those curves on a distribution graph.
  • Secondly, as a result of the computation you may have done above, for a given range, a repetition length and a distribution, you should be able to compute the ideal run-length between repetitions if it were a "true random" source. If you get a lot more repetitions than that ideal, then you've got a crappy algorithm. Fortunately, smart people have come up with very good and very efficient algorithms for this so you don't have to, and that's why there are RND functions in most math libraries that already have them built in.

Bottom line is that these things are quite useful, both "true" and "pseudo" versions are good for different things, and repetition isn't necessarily a bad thing.

 

As I mentioned above though, the OP really doesn't seem to have anything to do with random numbers but the data structure you use to store them which defines the amount of work you have to do to find the nth one (whether the "things" are random or not).

 

 

Goals transform a random walk into a chase, :phones:
Buffy


#9 petrushkagoogol

petrushkagoogol

    Understanding

  • Members
  • 387 posts

Posted 10 September 2017 - 11:43 PM

.
Can you write a program that generates a string of random numbers?

 

Here is a function in C# that does the job neatly   :innocent: 

 

static string getRandomSeries()
        {
            string random_no_str = string.Empty;
            StringBuilder sb = new StringBuilder();
            Random _r = new Random();
            
            for (int i = 0; i < 5; i++)
            {
                int n = _r.Next(i, 10);
 
                sb.Append(n.ToString() + ",");
            }
 
            return sb.ToString().Substring(0, sb.Length - 1);
        }


#10 scherado

scherado

    Questioning

  • Banned
  • 207 posts

Posted 11 September 2017 - 02:58 AM

.
I appreciate that and I thank you for the reply.

I had to write what you give as "Random()" in the several languages I was taught in college. The difference should between given the task for which you give an example and the task I was required to pass the first week of he respective courses should be obvious: the true meaning of "random" must be understood to pass the homework in that first week. If your professors didn't require such a thing, then I'd consider getting my money back, though this presumes that it was your money, no offense to anyone.

The difference being obvious.

Those languages were, in order:

APL (interpretive language)
Pascal
C
C++

Those which didn't require that for homework (not in order):

Prolog
PLI
Fortran
Assembly (Assembler)
COBOLT

#11 scherado

scherado

    Questioning

  • Banned
  • 207 posts

Posted 11 September 2017 - 02:59 AM

Here is a function in C# that does the job neatly :innocent: -

static string getRandomSeries()
{
string random_no_str = string.Empty;
StringBuilder sb = new StringBuilder();
Random _r = new Random();

for (int i = 0; i < 5; i++)
{
int n = _r.Next(i, 10);

sb.Append(n.ToString() + ",");
}

return sb.ToString().Substring(0, sb.Length - 1);
}

.
I appreciate that and I thank you for the reply.

I had to write what you give as "Random()" in the several languages I was taught in college. The difference should between given the task for which you give an example and the task I was required to pass the first week of he respective courses should be obvious: the true meaning of "random" must be understood to pass the homework in that first week. If your professors didn't require such a thing, then I'd consider getting my money back, though this presumes that it was your money, no offense to anyone.

The difference being obvious.

Those languages were, in order:

APL (interpretive language)
APL2 (interpretive) ------edit-------------
Pascal
C
C++

Those which didn't require that for homework (not in order):

Prolog (interpretive) ------edit-------------
Pascal
PLI
Fortran
Assembly (Assembler)
COBOLT
Visual Basic ------edit-------------

Edited by scherado, 12 September 2017 - 01:43 PM.


#12 petrushkagoogol

petrushkagoogol

    Understanding

  • Members
  • 387 posts

Posted 11 September 2017 - 09:03 AM

.
I appreciate that and I thank you for the reply.

I had to write what you give as "Random()" in the several languages I was taught in college. The difference should between given the task for which you give an example and the task I was required to pass the first week of he respective courses should be obvious: the true meaning of "random" must be understood to pass the homework in that first week. If your professors didn't require such a thing, then I'd consider getting my money back, though this presumes that it was your money, no offense to anyone.

The difference being obvious.

Those languages were, in order:

APL (interpretive language)
Pascal
C
C++

Those which didn't require that for homework (not in order):

Prolog
PLI
Fortran
Assembly (Assembler)
COBOLT

 

Truly random numbers cannot be  defined as per an algorithm. This  would make them pseudo-random.

 

Here is my idea :

Have an enumeration { 1,2,3.4,5,6,7,8,9,0 }.

Have a timer reorder the enum every 100 milliseconds.

Have another timer read a number from the enum at different intervals 1 sec, 1.02 sec, 0.98 sec and so on.

 

This effectively could solve the problem.

Is it truly random, I'm not sure  :irked:


Edited by petrushkagoogol, 11 September 2017 - 09:07 AM.


#13 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 11 September 2017 - 10:41 AM

Is it truly random, I'm not sure  :irked:

 

No, it's not because it is algorithmic (must be so even though you have not specified how you're doing the "reorder"), and therefore will be pseudo-random. You cannot have "truly random" without an external source of random events as described above. Depending on the "reorder" algorithm, it may or may not be "effective" (that is match expected distribution and repetition behavior described above), but I can tell you that any reordering approach will be incredibly inefficient, as most Random() functions are O(1), and what you're describing is at least O(log n) or worse.

 

And of course storing them in a comma delimited string is the most inefficient thing you could do, unless your only intent is to write them out to a file rather than use them directly.

 

 

An algorithm must be seen to be believed, :phones:

Buffy



#14 OceanBreeze

OceanBreeze

    Explaining

  • Members
  • 527 posts

Posted 11 September 2017 - 11:24 AM

My thought is we can never generate a true random number by any means at all. Even if you start with something as random as a stream of white noise, you still have the problem of collecting something randomly out of it. How do you select a true random moment to dive in and make your collection?

The collecting action itself would need to be random as well as the stream the collecting is done from.

Maybe crashing two random streams together will cause something random to fall out, but how do you choose what to collect of the fallout and when?

I think it can get very deeply philosophical and even touch on the whole argument about free will and determinism.

Then again, I am probably over thinking it. If the experiment cannot cause a repetition of the number for the duration of the experiment, it should be random enough for any practical usage, I would think.

 



#15 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 11 September 2017 - 11:53 AM

My thought is we can never generate a true random number by any means at all. Even if you start with something as random as a stream of white noise, you still have the problem of collecting something randomly out of it. How do you select a true random moment to dive in and make your collection?
The collecting action itself would need to be random as well as the stream the collecting is done from.


This is actually a great question, because while it does go to the philosophical about the definition of "randomness," randomness in fact has been well-defined in information theory which defines it as Information Entropy, or simplistically, the "lack of order in a set of information."
 
It's notable that this has gradations, as random number generators that produce uneven distribution curves (Poisson, logarithmic, etc.) "contain information" vs. a uniform distribution which provides "perfect entropy."
 
The bottom line though is that if you have one source of randomness, even a non-random picking mechanism (for example, picking one ever second, which has no information entropy), is still guaranteed to result in a data set that has the same Entropy as the original source.

So...
 

Then again, I am probably over thinking it. If the experiment cannot cause a repetition of the number for the duration of the experiment, it should be random enough for any practical usage, I would think.


Yes, and even better, it's guaranteed to be! :cheer:

 

Thus we may have knowledge of the past but cannot control it; we may control the future but have no knowledge of it, :phones:

Buffy



#16 scherado

scherado

    Questioning

  • Banned
  • 207 posts

Posted 12 September 2017 - 01:52 PM

My thought is we can never generate a true random number by any means at all. Even if you start with something as random as a stream of white noise, you still have the problem of collecting something randomly out of it. How do you select a true random moment to dive in and make your collection?
The collecting action itself would need to be random as well as the stream the collecting is done from.
Maybe crashing two random streams together will cause something random to fall out, but how do you choose what to collect of the fallout and when?
I think it can get very deeply philosophical and even touch on the whole argument about free will and determinism.
Then again, I am probably over thinking it. If the experiment cannot cause a repetition of the number for the duration of the experiment, it should be random enough for any practical usage, I would think.

.
I can tell you that I don't know how the professors determined whether or not our programs ever produced any pattern. I do know that some students failed the assignment.

#17 Buffy

Buffy

    Resident Slayer

  • Administrators
  • 8805 posts

Posted 12 September 2017 - 03:05 PM

I can tell you that I don't know how the professors determined whether or not our programs ever produced any pattern. I do know that some students failed the assignment.


For a given set of random numbers you can perform statistical analyses on it to check if the distribution is uniform and to check for repeating sequences or patterns. One of my favorite easy tests is to create a bit map of the data (this one's in black and white, but ones I've used use color):

True random numbers:

randbitmap-rdo-section.png

 

PHP rand() function:

randbitmap-wamp-section.png

 

Source: Random.org

 

...and as you can see, just eyeballing it will show the patterns that indicate a weakness in the generator.

 

It is, as Ocean pointed out though, very difficult to *prove* randomness, as truly random sources *will* produce runs and patterns. The fact that they're in there is not an indication of any weakness in the randomness unless it shows long-term repetition.

 

 

You should call it entropy (because).... no one really knows what entropy really is, so in a debate you will always have the advantage, :phones:

Buffy