Talk:Random number generation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Statistics (Rated Start-class, Low-importance)
WikiProject icon

This article is within the scope of the WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page or join the discussion.

Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 Low  This article has been rated as Low-importance on the importance scale.
 

Section 3.3 is irrelevant[edit]

The subsection on generating a random variable describes how to generate a random variable with an arbitrary probability distribution from a uniform random variable. It presumes the availability of a uniform random variable. The rest of the entire entry is focused on how to acquire some approximation of a uniform random variable. This section should at the very least be moved to a different part, as it has little to do with pseudo-random number generators and entropy machines. — Preceding unsigned comment added by Geekynerdrd (talkcontribs) 05:53, 4 January 2014 (UTC)


Randomness is an observed entity[edit]

The article starts out with: "A random number generator (RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random." But it should be the other way around: If an Observer find that a sequence lack any pattern, it appears random to him. Different observers may rate the same sequence differently. The randomness is not in the sequence.

Bo Domstedt http://www.trng98.se


Reference to PokerStars[edit]

The segment mentioning 'PokerStars' is entirely false. It falsely claims:

"individual statistics gathered from hundreds of multiple players and tens of thousands of played hands show that the outcome of games are nowhere near the statistical occurrences"

There is no such survey that exists.

In fact, the only published surveys find that the random shuffling processes are entirely legitimate and conform to expectation. Three such surveys exist at:

http://groups.google.com/group/rec.gambling.poker/msg/90082dfe67dc4a7f?hl=en& http://groups.google.com/group/rec.gambling.poker/msg/177010a4879f4c6b http://www.spadebidder.com

Further, Cigital has released their audit last week confirming that their shuffle is truly random:

http://www.pokerstars.com/poker/rng/cigital-rng-labresults.pdf

Since I work for PokerStars, I feel that it would be inappropriate for me to directly edit the page, but I think that the four independent sources provided above contrast with the false and unsourced claims on the page. The existing paragraph fails Wikipedia's standards on 'Verifiability', 'Identifying reliable sources', and 'Citing sources'. MichaelJosem (talk) 04:59, 29 March 2010 (UTC)

Example?[edit]

The article does not provide an example of a RNG that one can pop into one's code. I think really 99% of the people coming to this page would be looking for an algorithm. For "the experts" not to provide one is not meeting their needs because it is actually quite difficult to find a simple general purpose RNG on the web. I found this (http://www.bobwheeler.com/statistics/Password/MarsagliaPost.txt) article which seems to have a very nice random number generator better than most operating systems ship standard (i.e. surely better than rand() or random() in the C libraries). Of course to provide cryptographically strong code would fill too much space, so I think the article should stop short of this. —Preceding unsigned comment added by Paulsheer (talkcontribs) 15:46, 23 August 2009 (UTC)

??[edit]

This page is redundant with Randomization and Random number generator. However, I believe it's important to make the bridge between the two.

Randomization is about taking elements and putting them in random order (i.e. shuffling) (or maybe also selecting a random subset), generating random numbers is about just creating numbers at random. The two processes are fairly equivalent.

I believe that random number generator could be merged into this page. Flammifer 09:06, 23 September 2005 (UTC)

the odd thing about this is the fact that i clicked on the Random Article link and this was the page that came up :)

Yes, it should be merged with random number generator at the least. Richard001 05:09, 12 February 2007 (UTC)

I think it should be the other way round. A random number generator is an important kind of computer programme. Random number generation is the technique it uses. FSharpMajor 11:44, 23 February 2007 (UTC)

Yes but Random Number Generation exists outside of computer programming 71.52.51.151

I also believe this page and random number generator should be merged. —Preceding unsigned comment added by 66.191.137.2 (talk) 19:36, 16 October 2007 (UTC)


I'm going to express a view I'm never seen before: the only true random number generators are those implemented in software. Physical (hardware) generators have some kind of bias. Possibly quantum generators produce truly random bits, but how do we know that deficiencies in our physical setup haven't biased the quantum generator? Some software "gathers entropy" by measuring physical things (e.g. mouse movements, key-press timing, temperature of processor, disk seek time) but then goes to great efforts to convert this to a uniform distribution. Why not just use software from the start? Every time the diehard tests get another (stronger) test, authors of PRNGs re-write their software to reduce the newly-discovered bias by another order of magnitude. This arms race results in better and better PRNGs. 132.244.72.5 (talk) 13:30, 26 March 2013 (UTC)

Your view appears to be biased... A properly designed hardware RNG will be theoretically unpredictable, no measurable bias. By the way, quantum generators do exist ( http://comscire.com/cart/Files/whitepaper/Pure%20Quantum%20White%20Paper.pdf ) — Preceding unsigned comment added by 64.238.189.169 (talk) 19:57, 18 July 2013 (UTC)

Practical applications and uses of random numbers[edit]

i have a problem with the following sentense: "For instance, a system that 'randomly' selects music tracks for a background music system must only appear to be random; a true random system would have no restriction on the same item appearing two or three times in succession." it just isn't true. most systems to select random music tracks work on the principle of drawing a sample of n songs from the master list without replacement. in this paradigm, repeasts are are possible (a song could be the last in one random sample, and the first in the next), and are not prohibited by the randomness. this is not a problem with random number generators because these playlist selectors are not designed to sample with replacement. lest we all forget our introduction to statistics courses, sampling without replacement is just as random as sampling with replacement. 6 march 2008. —Preceding unsigned comment added by 198.182.163.125 (talk) 13:07, 6 March 2008 (UTC)

I don't think they were saying it was a problem with random number generators, just that users would not want truly random behavior. The fact that it is random means it could appear multiple successive times, and users don't want that. They even see patterns where there are none, as in this newsweek article by Steven Levy. -Euicho- (talk) 02:52, 28 July 2010 (UTC)

Sophie Germain prime[edit]

How can the result of 1/q be a random number? —Preceding unsigned comment added by 84.56.223.168 (talk) 07:55, 16 January 2008 (UTC)

it wouldn't be truly random, but it may have properties close enough to randomness that make it valuable for some purposes. what properties? two major properties are that the numbers should be distributed appoximately according to a uniform distribution, and that the numbers are uncorrelated (that is, the second number doesn't tend to be high if first one is high, or simmilar effects). it is best for the lack of correlation to extend to multiple dimensions (that is, the first three don't have statistically important effects on the second three). 6 march 2008 198.182.163.125 (talk) 13:15, 6 March 2008 (UTC)

Fact tag[edit]

For instance, a system that 'randomly' selects music tracks for a background music system must only appear to be random; a true random system would have no restriction on the same item appearing two or three times in succession.

I, and anyone else who used the random repeat feature of some early software PC CD-ROM players, can attest to the fact that allowing the same selection twice (or more) in no way ensures that selection is truly random. (Either that or my computer loved the song I hated on an otherwise good album because the track list would go something like 7,3,2,10,3,1,9,4,3,12,6,3.) Nowadays when one hears the same track several times it actually brings in question how random the selection is by ignoring dozens (or more) of other possible choices, for example if I hear #3 of a 100+ song mp3 cd four times in the first 12 selections (or something similar) and haven't set some kind of preference for it, I'd be especially dubious of its "randomness" the same way I'd wonder about a pair of dice in a craps game that tend to roll 1s and 2s.

Long story short who/what says a true random system would have no restriction on the same item appearing two or three times in succession. because it seems counterintuitive to the idea of random selection? Anynobody(?) 06:39, 26 June 2008 (UTC)

I'm assuming that you put in the "fact" tag about six months ago...
By definition, a TRULY random system, having playing one song out of one hundred, would not have a lower chance of playing that same song again. It's still one in a hundred. (If it were otherwise, that would mean we'd have a simple means of guessing what will happen next with a better than one in one hundred success. That don't sound random, do it?)
With true randomness, the sorts of flukes that you describe would actually be a quite noticeable phenomenon, especially when you consider that you'd probably notice if ANY of the one hundred songs repeated quickly. Humans are pattern-seeking animals, and we sometimes see them where they don't exist. If one NEVER saw repeating track, we probably wouldn't notice, although it would actually be gradually building evidence that it wasn't random.
But back to the nutmeat. Here's the article's statement:

"...A true random system would have no restriction on the same item appearing two or three times in succession."

And here's your statement:

"...Allowing the same selection twice (or more) in no way ensures that selection is truly random."

These two statements do not contradict each other, any more than "Eating an apple means you're eating a fruit" is contradicted by "Eating fruit doesn't ensure you're eating an apple". I've got another analogy. "Playing with matches might start a wildfire" isn't contradicted by "A wildfire's existence in no way ensures that someone played with matches".
In my analogies, and the statements, matches aren't the only way to start a fire, apples aren't the only fruit, and randomness isn't the only way to get repetitions.
Some of this may be confusing or counterintuitive to some people, and may need more explanation, but the article doesn't need a tag for citation, as it's a simple statistical truth. I think I should remove it, and I think I will.
Misha Vargas (talk) 14:48, 5 February 2009 (UTC)

This has been discussed enough. The thread is obviously dead and any further contention seems pointless. I'm going to remove the dubious mark now. 7. September 2010 —Preceding unsigned comment added by 84.208.92.110 (talk) 14:15, 7 September 2010 (UTC)

SOCR advertisement[edit]

I know its probably against wiki guidelines but one section appears to be just an advertisement for the SOCR website or something along those lines. --213.203.161.144 (talk) 22:38, 21 July 2008 (UTC)

Spam as a source of randomness[edit]

Gentlemen, finally a use for spam: employ it in Random number generation. (Implies a vibrant and creative spam producing community in your country. OK, not as good as radio, tv, clouds...)

Jidanni (talk) 01:37, 28 December 2008 (UTC)

Entropy vs. unpredictability to an attacker[edit]

There's terminology here that isn't clearly defined about the "quality" of random numbers and what is "truly" random. Here are some categories:

  • Arbitrary numbers: the shuffle function on your MP3 player might not even try to be random, but it's not obvious either.
  • Non-cryptographic pseudorandom number generators: easy to predict future outputs from past.
  • Cryptographic *pseudo*random number generators: These take a key of, say, 256 bits. For the best generators (e.g., AES in counter mode), nobody knows a practical way to distinguish a couple gigabytes of output from true randomness. If we discover an attack on the algorithm or have a vast (qualitative) increase in computing power, that could change.
  • Typical cryptographic random number generators: These hash information that's assumed unpredictable to an attacker (e.g., details of mouse movements, precise timing of keystrokes and hard disk activity), with the goal that the attacker should have to make 2^128 or 2^256 or whatever guesses. Given good estimates of the entropy in those inputs, the generator can be rigged so the crypto algorithms only need to provide statistical mixing, and the output will still appear random no matter what advances there are in cryptanalysis and computing power.
  • Basic "true" random number generators: Based on air turbulence, the lower bits of precise temperature readings, etc. -- things we're highly confident nobody (us or anyone else) could predict. We may be able to use parts of the output directly, without a mixing function.
  • Advanced "true" random number generators: Based on timings of atomic decays, etc.

Note that secrecy, unpredictability, and mathematical generation vs. direct observation are three distinct axes. The lower digits of the S&P 500's closing price for tomorrow are unpredictable and directly observed but not secret. Numbers generated from a good passphrase (passparagraph?) are secret and mathematically generated but some folks might question whether they're "truly" random since better crypto or computing could theoretically distinguish them from random. And so on. :) —Preceding unsigned comment added by 67.119.195.43 (talk) 23:41, 12 January 2009 (UTC)

Edit: Maybe the solution is a section, "Traits of Random Numbers", that separates out and defines (1) even statistical distribution, (2) cryptographic randomness, and (3) unpredictability regardless of computational power. 67.119.195.43 (talk) 23:52, 12 January 2009 (UTC)

Another edit: I think better names for the traits are 1) evenly distributed, 2) indistinguishable from random, 3) truly random. The difference between secrecy and randomness (except in cryptography), and between "basic" random number generators and fancypants quantum stuff, can wait until after the basic definitions. Now, the hard part is figuring out how better to organize the info currently scattered among many, many headings.67.119.195.43 (talk) 08:55, 25 January 2009 (UTC)

References and footnotes[edit]

I like this article. But it is missing references and footnotes section. To highlight this for editor(s) I have added the template "morefootnotes" as a reminder for work to be done. A starting point is to take the 3 external references and put them into a references section; then a footnote can be added into the body. I will attempt this as soon as I can.--Михал Орела (talk) 13:21, 13 January 2009 (UTC)

I have just added two new sections: Notes and References. I put the [1] external link into the References section and made a footnote reference to the original web-page link. Looking at the result suggests that I reverse this and put the external link reference into the Notes... Will do that now!--Михал Орела (talk) 14:12, 13 January 2009 (UTC)
Skiena Mission complete! There are two more inline references still to be dealt with.--Михал Орела (talk) 14:25, 13 January 2009 (UTC)
All done! Now it would be nice to provide citations (if needed) for other claims in the body of the article.--Михал Орела (talk) 14:56, 13 January 2009 (UTC)

Cleanup[edit]

The article had a lot of redundant sections, so I tried to collate the information and add references. I moved the section headings around to give some logical flow to the presentation. It looks like more footnotes are needed and the intro could use some cleanup. --Hakanai (talk) 22:35, 27 June 2009 (UTC)

See Also[edit]

Add a link to Randomness_tests ? 82.163.24.100 (talk) 17:45, 7 July 2009 (UTC)

Marsaglia MWC generator[edit]

The present version of the article shows the following code for the Marsaglia MWC generator:

m_w = <choose-initializer>;    /* must not be zero */
m_z = <choose-initializer>;    /* must not be zero */
 
uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result */
}

However, it seems that there are different versions of this PRNG. For example Marsaglia, 12 Jan 1999: [1]

#define znew  ((z=36969*(z&65535)+(z>>16))<<16)
#define wnew  ((w=18000*(w&65535)+(w>>16))&65535)
#define MWC   (znew+wnew)

and Marsaglia, 20 Jan 1999: [2]

#define znew   (z=36969*(z&65535)+(z>>16))
#define wnew   (w=18000*(w&65535)+(w>>16))
#define MWC    ((znew<<16)+wnew )

Note the difference in the definition of wnew. The article implements the second one. Is the first one a mistake? The first one seems suspicious to me, since it concatenates two 16-bit random numbers; applications which use only the highest-order bit (to generate random sequences of 0 and 1) don't benefit from the additional randomness of the 'w' part. Han-Kwang (t) 13:31, 30 October 2010 (UTC)

In this archive Marsaglia himself states (Posted: Jan 15, 1999 11:41 AM):

"In my earlier work, done in Fortran, I had implemented
two 16-bit multiply-with-carry generators, say z and w,
as 32-bit integers, with the carry in the top 16 bits,
the output in the bottom 16. They were combined by
(z<<16)+w. (In Fortran, ishft(z,16)+w.) Such a
combination seemed to pass all tests. In the above-
mentioned post, I used (z<<16)+(w&65525), and that
does not pass all tests. So (z<<16)+w seems
preferable; it is used below, providing a MWC that
seems to pass all tests."

http://mathforum.org/kb/message.jspa?messageID=1524861 — Preceding unsigned comment added by 62.121.49.2 (talk) 08:55, 5 February 2013 (UTC)

"Truly random computational number generator" ???[edit]

"Only in 2010 was the first truly random computational number generator produced, recurring to principles of quantum physics.[2]"\

As far as I can tell, the work referred to by this is not a computational method, it employs two 171Yb+ qubits trapped in independent vacuum chambers -- hardly a computational element.--84.108.213.97 (talk) 00:47, 23 December 2010 (UTC)

W-Chaos[edit]

i want to add a mention about W-Chaos algorithm as yet another method to get True Random Numbers. this algo is used by cipher Mademoiselle Entropia. W-Chaos uses a list of web-resources to ping them, fluctuations of ping values allow to generate TRNs. — Preceding unsigned comment added by Evgeney Knyazhev (talkcontribs) 23:05, 1 January 2011 (UTC)

As I mentioned in my edit summaries, there is nothing that indicates notability for this software. The SourceForge web page does not even list the name of the developer (you); it is buried inside the 7zip file. For an implementation to be mentioned on Wikipedia, it should be in widespread use or be acknowledged by independent experts as being a novel idea. Han-Kwang (t) 19:20, 2 January 2011 (UTC)
Agreed, but, actually, it cannot be done in no Time. Just a question, did you try app to generate random numbers??? — Preceding unsigned comment added by Evgeney Knyazhev (talkcontribs) 01:35, 3 January 2011 (UTC)
"try app to generate random numbers" -- I don't understand you, but anyway, I don't think the answer is relevant for this discussion. Han-Kwang (t) 22:27, 3 January 2011 (UTC)

@Hankwang why irrelevant??? app (Mademoiselle Entropia) allows not only to cipher a file, but to generate true random numbers too (with algorithm W-Chaos). You mentioned of necessity to test algorithms with independent experts. i suppose you have had knowledge to judge about generator of random numbers. --Evgeney Knyazhev (talk) 02:55, 4 January 2011 (UTC)

Sorry, if there are no reputable reviews or papers mentioning W-Chaos then it shouldn't be here. Can you supply any such references? Sebastian Garth (talk) 20:46, 4 January 2011 (UTC)
Thanks for reply, Sebastian. Actually, i've searched independent specialists to verify algorithms. --Evgeney Knyazhev (talk) 00:07, 5 January 2011 (UTC)

Visual comparison of random vs. pseudo-random generators[edit]

Would anyone include a picture showing the large-scale difference in patterns (or lack thereof) between random sequences and pseudo-random sequences? This example http://boallen.com/random-numbers.html clearly illustrates this difference. It would be valuable if something like this could be included in the article. 23.16.127.167 (talk) 21:29, 13 March 2012 (UTC)

That is not a representative picture. Some PRNGs are very very good and are indistinguishable from an RNG. That website only shows a very poor PRNG and gives a false impression that all PRNGs are bad. HumphreyW (talk) 21:36, 13 March 2012 (UTC)

New software-based TRNG[edit]

I get the impression from various sources on the internet that random number generators (especially of the true variety) are suposedly very hard to create. I have however managed to create a Perl script which I believe to be a pretty much bullet-proof TRNG. I would like there to be a mention of it on Wikipedia but I know very little about the protocols regarding adding an entry to Wikipedia. Please can an expert in both Wikipedia and Perl thoroughly examine my script and if you think it is worth including, please can you put it in an appropriate place and add any relevant links to it from other Wikipedia pages. Thank you very much. Here is the script:

sub TRNGrand
 {
 ($range) = @_;

#This Perl subroutine almost instantly outputs a true random #number between zero and $range inclusive to 15 decimal places. # #If you are considering purchasing a hardware TRNG, save your #money and use this script instead. # #The author has only tested this subroutine on Windows and #therefore does not know if it works on Unix. # #It works by counting the number of for-loop cycles per eight #microseconds several times and dividing the counts into two #groups. A bit (0 or 1) is then determined by which group wins. #A draw means "try again". This process is repeated for each bit. # #The very first count is not included in the groups because it #tends to be somewhat different to the other counts. # #The two groups are intermeshed according to the following pattern: # #ABABBABAABABBABABABAABABBABAABAB # #The pattern is irregular in order to guard against any regularities #in the computer. # #Tests confirm that it produces results which are fairly evenly #distributed and because of the way it operates, the results are #theoretically independent of each other. # #Unfortunately, the Perl "bignum" module and associated modules #break this subroutine so if you are writing a Perl script which #uses these modules, the author suggests that you use this #subroutine to populate an array with all of the random data your #script will need before issuing the "use bignum;" command.

use Time::HiRes qw(gettimeofday);

$decimalplace = 1; until ($decimalplace == 15) { $bitstring = ""; for ($binaryplace = 0; $binaryplace <= 3; $binaryplace++) { @loopcount = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); $loopcountsgroupA = 0; $loopcountsgroupB = 0; until ($loopcountsgroupA ne $loopcountsgroupB) { for ($runnumber = 0; $runnumber <= 32; $runnumber++) { $x8microsecondschanges = 0; $previousx8microseconds = "null"; until ($x8microsecondschanges == 2) { ($seconds,$microseconds) = gettimeofday; $x8microseconds = int($microseconds / 8); if($previousx8microseconds ne "null" && $x8microseconds ne $previousx8microseconds) { $x8microsecondschanges++; } $previousx8microseconds = $x8microseconds; if($x8microsecondschanges == 1) {$loopcount[$runnumber]++;} } } $loopcountsgroupA = $loopcount[1]+$loopcount[3]+$loopcount[6]+$loopcount[8]+ $loopcount[9]+$loopcount[11]+$loopcount[14]+$loopcount[16]+ $loopcount[18]+$loopcount[20]+$loopcount[21]+$loopcount[23]+ $loopcount[26]+$loopcount[28]+$loopcount[29]+$loopcount[31]; $loopcountsgroupB = $loopcount[2]+$loopcount[4]+$loopcount[5]+$loopcount[7]+ $loopcount[10]+$loopcount[12]+$loopcount[13]+$loopcount[15]+ $loopcount[17]+$loopcount[19]+$loopcount[22]+$loopcount[24]+ $loopcount[25]+$loopcount[27]+$loopcount[30]+$loopcount[32]; } if($loopcountsgroupA < $loopcountsgroupB) {$bit = 0;} else {$bit = 1;} $bitstring = "$bitstring$bit"; } $decimaldigit = unpack("N",pack("B32",substr("0"x32 .$bitstring,-32))); if($decimaldigit < 10) { $decimaldigits = "$decimaldigits$decimaldigit"; $decimalplace++; } } if($range eq "") {$range = 1;} return "0.$decimaldigits" * $range; }

95.172.231.160 (talk) 18:20, 29 January 2014 (UTC)

Wikipedia is not the place to publish original research (see WP:OR). There are many Category:Cryptography journals for that. I would call your attention to the fact that the problem you are addressing has numerous pitfalls. In particular, not all operating systems (e.g. Windows) provide time of day to microsecond resolution. --agr (talk) 19:23, 29 January 2014 (UTC)

Quote: "In particular, not all operating systems (e.g. Windows) provide time of day to microsecond resolution." Windows does support it. Otherwise my script would not work. I have successfully tested it on Windows. 95.172.231.160 (talk) 19:35, 29 January 2014 (UTC)

Maybe so, but this is still not the place to publish your idea. Good luck with it, tho.--00:00, 30 January 2014 (UTC)