9 ms·

Why is quality of pseudorandom number generators important?

87 points by DrinkWater 13y ago

StavrosK 13y ago
The linked poker vulnerability article is really worth a read.
Udo 13y ago
I've been running a virtual dice roller site for pen & paper roleplayers for about ten years. I get these kinds of emails all the time. "Your RNG is faulty, I just rolled three 20s in a row!" and stuff like that. It's probably not fixable psychologically, we're just seeing patterns everywhere. This also happens with physical dice by the way. If a player rolled two or more abysmal results in a row it's common to say "hey, you should really swap out these dice".
- sturmeh 13y ago
  There's more rigging involved with people who can't throw dice properly than there is with the seed of a RNG on a server miles away with you. :P
- polymatter 13y ago
  I've toyed with the idea of not using a fair RNG for games for this reason. People expect die rolls to converge to the average distribution much much faster than they actually do. So perhaps you can make a RNG program that does exactly that and does what the user expects, even if mathematically ridiculous. For example, if 20 is rolled then the probability of 20 being rolled again is halved (so it has a 1/40 chance) while the probability of its inverse is doubled (so probability of 1 is 1/10). This dramatically reduces the chance of the three 20s in a row scenario and would very quickly regress to the mean, just like people expect. Added flair for affecting the probabilties of all possible values subtly (so that after rolling a 20, a 2 becomes more likely and a 19 less likely). I'm sure I can't be the only person to think of this.
  - dllthomas 13y ago
    I don't like the notion of reinforcing bad intuitions.
    - a-priori 13y ago
      People are born with bad intuitions about how randomness works -- it's not learned. For whatever reason, our brains are wired to make uniformity feel random and randomness feel ordered. It's why we see stars in the sky, which are more or less distributed randomly in the star field, yet they don't appear random: they appear to form constellations. It's basically impossible to correct this bad intuition. People educated in the statistics and mathematics of random numbers have to consciously learn what real randomness looks like and override their intuition. But try as you might, the night sky will still form constellations. And dice rolls will still, frustratingly and confusingly, fall into streaks more often than you'd expect.
      - dllthomas 13y ago
        There are a lot of systems in the brain. It's theoretically possible that one of them will be untrainably spitting out the same flawed predictions, but we can certainly learn how to respond appropriately to those sensations.
  - fhars 13y ago
    http://en.wikipedia.org/wiki/Sobol_sequence http://en.wikipedia.org/wiki/Sobol_sequence
  - merloen 13y ago
    iTunes did that at one time because people complained about the shuffle algorithm for similar reasons.
    - spuz 13y ago
      Shuffling is different from selecting at random. I had an MP3 player that would use random selection instead of shuffling all tracks and it would annoy the hell out of me to hear the same songs twice in a row. I don't know if this is what iTunes used to do but if so then those people were right to complain.
- ygra 13y ago
  Some people solve this by throwing hardware (and dice!) at it: http://gamesbyemail.com/News/DiceOMatic http://gamesbyemail.com/News/DiceOMatic :-)
- herokusaki 13y ago
  Fascinating. I wonder if visualizing the dice roll could help. If you don't have ethical objections to it you could also A/B test biased dice (say, biased away from 1 and 20) for complaints (give a different contact email address to players who get biased dice) or instead show the players the distribution of the last 100 rolls.
  - Udo 13y ago
    That's not really possible for a lot of reasons. First, the roller is absolutely anonymous. There are basically three major functions the site performs: just rolling some dice according to user input, an API taking HTTP requests answering in JSON, and a chat room feature that has a dice roller bot. It's not possible to identify individual players except maybe in the chat rooms (though they're not really authenticated there either). I do sometimes get requests to look into chat logs of a particular room over allegations that one player somehow tampered with the results. This happens about once a month. Invariably, the accused user isn't even that lucky, they almost always have bog standard average results. It's just that the other players think this person is unreasonably lucky and they keep this belief up even after I tell them about the data (which they could have calculated themselves by looking at their own chat logs). Second, the core value proposition of the site is its ability to render roleplaying dice codes directly. That means you don't select your dice from a drop down - you enter the code. A simple example would be "3d6+5" for damage or something, but there are lots of different codes for different rules - some of them quite convoluted. It's not feasible to tinker with them in any meaningful way because players use the site in so many different ways.
- baby 13y ago
  Throwing dices in real life is even less random than a "truly" random function.
- nmc 13y ago
  You are referring to the common mistake of confusing randomness and uniformity. Your players are thinking: "Dice rolls are equiprobable, so I should roll evenly-distributed results." That only starts being true after a great number of rolls. Random distributions will be uneven and present clumps, strands and voids. For the same reason, during WWII, British intelligence thought that the Germans were bombing specific targets in London, while they were just dropping bombs at random. Source recently posted on HN: http://www.wired.com/wiredscience/2012/12/what-does-randomness-look-like/ http://www.wired.com/wiredscience/2012/12/what-does-randomne...
  - Udo 13y ago
    If you knew how many times I launched into that randomness vs uniformity lecture myself ;) My point was that it's not possible to convince certain people with logic. They see random numbers and something happens to their brains, maybe it's religion. They'll always see oracles or at the very least shady manipulators behind random data.
  - pixl97 13y ago
    https://en.wikipedia.org/wiki/Law_of_large_numbers https://en.wikipedia.org/wiki/Law_of_large_numbers
- pessimizer 13y ago
  https://en.wikipedia.org/wiki/Representativeness_heuristic https://en.wikipedia.org/wiki/Representativeness_heuristic
- raverbashing 13y ago
  It should be fun to calculate the chance a RNG is biased based on a die rolling 20 3 times in a roll Similar to that question about biased coins and throwing 10 heads in sequence it was discussed some time ago here.
- walshemj 13y ago
  It happens at our recent dnd game our mage roiled all 1's on a magic missile 6d4 all 1's
- emhart 13y ago
  Re: Physical dice. I've gamed a lot over the years, and I don't believe I played with anyone anyone for whom swapping out dice had anything to do with actually effecting randomness/probability, but rather was just a fun way to wish for better luck. And, even then, that move "toward" luck or "away" from bad luck was always tongue-in-cheek. Yet...we still swapped the dice. :)
- edraferi 13y ago
  Clearly, there is something supernatural afoot: http://www.penny-arcade.com/comic/2014/02/05 http://www.penny-arcade.com/comic/2014/02/05
sturmeh 13y ago
The issue is that if you run the same program twice without selecting a suitably random seed you will make the same 60 million rolls. If you can somehow control, predict or influence the seed you can predict or influence rolls. For example if the game uses JUST the system time as a seed, I can shift the system time back to a specific position and run the application again to get the same random number generation. If you know the algorithm, for example you're playing an open source card game, and you can determine the time (offset) on the server or the other players computer you could cheat by calculating their random variables. Now it really isn't an issue in games, but it's incredibly important in security. Randomness makes up a huge component of encryption. That's why you have applications that require you to move the mouse a bit, hopefully randomly and they take in a whole bunch of other entropy fed in by the system. In Unix-like OS's you have /dev/random and /dev/urandom. /dev/random requires a certain amount of entropy and environmental noise, and it blocks on reads until it's satisfied with the output. /dev/urandom does not block, but it gives pseudo random output. For the purposes of security, /dev/urandom should NEVER be used. However neither are truly 'random'.
- sharpneli 13y ago
  But for any other purpose than generating private keys one should NEVER use /dev/random. If you're not sure use /dev/urandom. I've had to painstakingly explain to certain people why, as an example, erasing a HDD from /dev/urandom is allright. And why their program that simulates some random input should use /dev/urandom. But no, they babble about true randomness and then complain why they get like paltry few hundred bytes per second. Even if you have a server running casino games just use /dev/urandom/. It requires a total compromise of the server to get the internal state out of that, and in that case it's easier just to change urandom into /dev/zero.
  - blueskin_ 13y ago
    If you need a lot of entropy, it's good to use a hardware RNG to keep the load down (and it improves quality).
    - 13y ago
Aardwolf 13y ago
Ivy Bridge and newer CPU's of Intel have this new "random" instruction (I still have a Sandy Bridge CPU tho). Is that one truly random enough for crypto purposes? Thanks!
- fhars 13y ago
  It depends on whom you trust: http://arstechnica.com/security/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/ http://arstechnica.com/security/2013/12/we-cannot-trust-inte...
- Daniel_Newby 13y ago
  No, and it does not matter who you trust. Analog circuitry simply has too much inbound and outbound information leakage to be trustworthy. You must round it out with a mixing algorithm.
jbert 13y ago
PRNGs (pseudo-random-number-generators) take in a small amount of randonmness (a seed) and produce a long stream of numbers from that. Anyone using the same PRNG can look at the output of yours and try to put their PRNG in the same state. If they succeed, the output of theirs will match yours - now and in the future - unless you re-seed. Two problems can occur here: 1) you seed with something they can predict. e.g. seconds since 1970 (or microseconds since 1970). If they have a reasonable sample of numbers from your system, they can try lots of different seeds and see if they can find the one which gives the same output as you. 2) PRNGs have "internal state", which is a bunch of numbers they mix together. Some PRNGs have the property that if you can you can observe enough numbers in a row from the PRNG, you can turn them back into the internal state locally and then you can do the same thing as if you knew the seed (predict future numbers).
- chilldream 13y ago
  > you seed with something they can predict One of my favorite examples of this ever: Once in Las Vegas a keno machine mistakenly used a fixed seed. Meaning once someone figured this out, he could show up when the game started for the day and predict what the machine would do with 100% accuracy. http://www.americancasinoguide.com/slot-machines/the-worlds-greatest-slot-cheat.html http://www.americancasinoguide.com/slot-machines/the-worlds-...
pygy_ 13y ago
put on hold as primarily opinion-based by Xavierjazz, Olli, Excellll, HackToHell, Tog 3 hours ago Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question. Stack exchange is broken. The question mixes up uniform distribution and randomness, but the answers are factual. There's little to no opinion involved here.
- df07 13y ago
  Give the system time to work. It's already been taken off hold.
  - cruise02 13y ago
    No! A question got closed! The whole thing must be broken!
    - pygy_ 13y ago
      Hyperbole sometimes helps to get the point across... The problem with Stack exchange is that it conflates heavy site usage with domain experience and maturity. Avidity for imaginary internet points and maturity are at best orthogonal.
      - batguano 13y ago
        Excellent point, and well phrased. Still, I find the whole stack exchange system to be incredibly useful, including the original post. (Edit: And it looks like you do, too, since you point out the information is factual.)
      - bronsoja 13y ago
        As a general rule across the web, I'd agree with you. Although, I feel like on StackExcahge (or at least SO) those with the highest scores typically gave good answers in their domain as judged by their community and would not commonly give any answers outside their domain that could be voted up simply based on user rep alone. I don't really have any hard data on this, it's opinion based on seeing extremely good answers from high rep people regularly, and not being able to recall seeing poor answers from high rep users voted highly when they aren't actually useful.
chriswarbo 13y ago
When I see the word "random" I parse it as "unpredictable", since this is usually what people mean (even if they don't realise it) and can clear up many arguments. The concept of 'random' is interesting in some cases, but the vast majority of the time it's far stronger than what is required. In this case, the question is: > If a number generator is uniformly distributed, why might that not be 'random enough'? If we rephrase this as: > If a number generator is uniformly distributed, why might that be 'too predictable'? This makes the flaw obvious: there are many ways to choose numbers uniformly which are completely predictable. For example, choose the smallest value first, then choose a value which is furthest from any previously-chosen value (in, say, lexicographic gray-code order). The point here is that 'uniformity' is not the property we care about; it is a consequence of the property we care about (unpredictability). If a distribution were non-uniform, we would be better able to predict it (by biasing out predictions to match the distribution), hence the least-predictable distribution is necessarily a uniform one. Other times this comes up: > Are quantum measurements 'truly random'? That's untestable, but we can test whether they're predictable or not. > This encryption algorithm requires a source of random bits. It would work just as well with a source of bits that are merely unpredictable. > This strategy can only be defeated by a random opponent. It can also be defeated by an opponent which you can't predict. And so on.
- dllthomas 13y ago
  "[T]he vast majority of the time it's far stronger than what is required." Oftentimes it's also just not what is actually required. Often you want uniform spacing with some jitter, not points drawn from a uniform distribution.
- sdevlin 13y ago
  That is a good way to think of it. Indeed, that is how cryptographic randomness is typically defined. Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? A generator that passes this test will pass any statistical randomness test, but the converse is not necessarily true. For example Mersenne Twister is a good generator from a statistical perspective, but it's actually quite easy to recover its internal state by observing a small amount of output. (Around 20k bits, if I recall correctly.)
mathattack 13y ago
Eric Lippert's answer is great. It isn't the distribution of answers, it's the predictability. In most cases it's ok if the distribution looks random, but in some it turns out not to be ok.
aestra 13y ago
Take a look here: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... They found a flaw in a REAL poker site because they were using a pseudo random number generator (and a stupid algorithm) and were able to know the order of the cards being used in the game! >The RST exploit itself requires five cards from the deck to be known. Based on the five known cards, our program searches through the few hundred thousand possible shuffles and deduces which one is a perfect match. In the case of Texas Hold'em poker, this means our program takes as input the two cards that the cheating player is dealt, plus the first three community cards that are dealt face up (the flop). These five cards are known after the first of four rounds of betting and are enough for us to determine (in real time, during play) the exact shuffle. Figure 5 shows the GUI we slapped on our exploit. The "Site Parameters" box in the upper left is used to synchronize the clocks. The "Game Parameters" box in the upper right is used to enter the five cards and initiate the search. Figure 5 is a screen shot taken after all cards have been determined by our program. We know who holds what cards, what the rest of the flop looks, and who is going to win in advance.
lutusp 13y ago
> Just say you code in any language at all to roll some dice (just using dice as an example), after 600,000 rolls, I bet each number would have been rolled around 100,000 times, which to me, seems exactly what you expect. Bad example. Because the author specified "some dice", we can assume more than one die, in which case some numbers have a greater chance to appear than others, in a series of fair "random" throws. It's a bad sign that the author of a piece about randomness isn't aware of the systematic behavior of his chosen example, a behavior biased in favor of certain outcomes. http://www.algebra.com/algebra/homework/NumericFractions/Numeric_Fractions.faq.question.200314.html http://www.algebra.com/algebra/homework/NumericFractions/Num...
snarfy 13y ago
The idea of something being truly random bothers me because it goes against cause and effect. An effect happened without a cause. It violates laws of conservation, entropy, determinism, and a lot of other things.
- lutusp 13y ago
  > The idea of something being truly random bothers me because it goes against cause and effect. Not at all. The fact that one cannot predict the next number in a random sequence is irrelevant to the fact that, in the long term, that number has a predictable relationship with other numbers in the pool of possibilities. For a random generator of the digits 0-9, can I predict the next number in the sequence? No. Can I say what the proportion of, say, 7s will be, within a large list of outcomes? Yes, and the larger the list, the more reliable the prediction. If your position had merit, quantum theory, probabilistic on a small scale, would be seen as violating cause/effect relationships, a rather important part of physical theory. But, because of the mathematics of quantum probability, individually unpredictable atoms become very predictable macroscopic objects.
- sveit 13y ago
  If I toss a coin into the air and then it lands on tails, there is a visible cause and effect. The velocity of my arm, the position of the coin in my hand, the moment of release, the air currents in the room all affect the outcome. If I could measure these to a high degree of accuracy and plug the measurements into a detailed enough simulation, I could predict the outcome. However, I can't. So I am unable to predict the outcome (hence the outcome is random).

87 points by DrinkWater 13y ago

The linked poker vulnerability article is really worth a read.

Udo 13y ago

I've been running a virtual dice roller site for pen & paper roleplayers for about ten years. I get these kinds of emails all the time. "Your RNG is faulty, I just rolled three 20s in a row!" and stuff like that. It's probably not fixable psychologically, we're just seeing patterns everywhere. This also happens with physical dice by the way. If a player rolled two or more abysmal results in a row it's common to say "hey, you should really swap out these dice".

sturmeh 13y ago
There's more rigging involved with people who can't throw dice properly than there is with the seed of a RNG on a server miles away with you. :P
polymatter 13y ago
I've toyed with the idea of not using a fair RNG for games for this reason. People expect die rolls to converge to the average distribution much much faster than they actually do. So perhaps you can make a RNG program that does exactly that and does what the user expects, even if mathematically ridiculous. For example, if 20 is rolled then the probability of 20 being rolled again is halved (so it has a 1/40 chance) while the probability of its inverse is doubled (so probability of 1 is 1/10). This dramatically reduces the chance of the three 20s in a row scenario and would very quickly regress to the mean, just like people expect. Added flair for affecting the probabilties of all possible values subtly (so that after rolling a 20, a 2 becomes more likely and a 19 less likely). I'm sure I can't be the only person to think of this.
- dllthomas 13y ago
  I don't like the notion of reinforcing bad intuitions.
  - a-priori 13y ago
    People are born with bad intuitions about how randomness works -- it's not learned. For whatever reason, our brains are wired to make uniformity feel random and randomness feel ordered. It's why we see stars in the sky, which are more or less distributed randomly in the star field, yet they don't appear random: they appear to form constellations. It's basically impossible to correct this bad intuition. People educated in the statistics and mathematics of random numbers have to consciously learn what real randomness looks like and override their intuition. But try as you might, the night sky will still form constellations. And dice rolls will still, frustratingly and confusingly, fall into streaks more often than you'd expect.
    - dllthomas 13y ago
      There are a lot of systems in the brain. It's theoretically possible that one of them will be untrainably spitting out the same flawed predictions, but we can certainly learn how to respond appropriately to those sensations.
- fhars 13y ago
  http://en.wikipedia.org/wiki/Sobol_sequence http://en.wikipedia.org/wiki/Sobol_sequence
- merloen 13y ago
  iTunes did that at one time because people complained about the shuffle algorithm for similar reasons.
  - spuz 13y ago
    Shuffling is different from selecting at random. I had an MP3 player that would use random selection instead of shuffling all tracks and it would annoy the hell out of me to hear the same songs twice in a row. I don't know if this is what iTunes used to do but if so then those people were right to complain.
ygra 13y ago
Some people solve this by throwing hardware (and dice!) at it: http://gamesbyemail.com/News/DiceOMatic http://gamesbyemail.com/News/DiceOMatic :-)
herokusaki 13y ago
Fascinating. I wonder if visualizing the dice roll could help. If you don't have ethical objections to it you could also A/B test biased dice (say, biased away from 1 and 20) for complaints (give a different contact email address to players who get biased dice) or instead show the players the distribution of the last 100 rolls.
- Udo 13y ago
  That's not really possible for a lot of reasons. First, the roller is absolutely anonymous. There are basically three major functions the site performs: just rolling some dice according to user input, an API taking HTTP requests answering in JSON, and a chat room feature that has a dice roller bot. It's not possible to identify individual players except maybe in the chat rooms (though they're not really authenticated there either). I do sometimes get requests to look into chat logs of a particular room over allegations that one player somehow tampered with the results. This happens about once a month. Invariably, the accused user isn't even that lucky, they almost always have bog standard average results. It's just that the other players think this person is unreasonably lucky and they keep this belief up even after I tell them about the data (which they could have calculated themselves by looking at their own chat logs). Second, the core value proposition of the site is its ability to render roleplaying dice codes directly. That means you don't select your dice from a drop down - you enter the code. A simple example would be "3d6+5" for damage or something, but there are lots of different codes for different rules - some of them quite convoluted. It's not feasible to tinker with them in any meaningful way because players use the site in so many different ways.
baby 13y ago
Throwing dices in real life is even less random than a "truly" random function.
nmc 13y ago
You are referring to the common mistake of confusing randomness and uniformity. Your players are thinking: "Dice rolls are equiprobable, so I should roll evenly-distributed results." That only starts being true after a great number of rolls. Random distributions will be uneven and present clumps, strands and voids. For the same reason, during WWII, British intelligence thought that the Germans were bombing specific targets in London, while they were just dropping bombs at random. Source recently posted on HN: http://www.wired.com/wiredscience/2012/12/what-does-randomness-look-like/ http://www.wired.com/wiredscience/2012/12/what-does-randomne...
- Udo 13y ago
  If you knew how many times I launched into that randomness vs uniformity lecture myself ;) My point was that it's not possible to convince certain people with logic. They see random numbers and something happens to their brains, maybe it's religion. They'll always see oracles or at the very least shady manipulators behind random data.
- pixl97 13y ago
  https://en.wikipedia.org/wiki/Law_of_large_numbers https://en.wikipedia.org/wiki/Law_of_large_numbers
pessimizer 13y ago
https://en.wikipedia.org/wiki/Representativeness_heuristic https://en.wikipedia.org/wiki/Representativeness_heuristic
raverbashing 13y ago
It should be fun to calculate the chance a RNG is biased based on a die rolling 20 3 times in a roll Similar to that question about biased coins and throwing 10 heads in sequence it was discussed some time ago here.
walshemj 13y ago
It happens at our recent dnd game our mage roiled all 1's on a magic missile 6d4 all 1's
emhart 13y ago
Re: Physical dice. I've gamed a lot over the years, and I don't believe I played with anyone anyone for whom swapping out dice had anything to do with actually effecting randomness/probability, but rather was just a fun way to wish for better luck. And, even then, that move "toward" luck or "away" from bad luck was always tongue-in-cheek. Yet...we still swapped the dice. :)
edraferi 13y ago
Clearly, there is something supernatural afoot: http://www.penny-arcade.com/comic/2014/02/05 http://www.penny-arcade.com/comic/2014/02/05

sturmeh 13y ago

The issue is that if you run the same program twice without selecting a suitably random seed you will make the same 60 million rolls. If you can somehow control, predict or influence the seed you can predict or influence rolls. For example if the game uses JUST the system time as a seed, I can shift the system time back to a specific position and run the application again to get the same random number generation. If you know the algorithm, for example you're playing an open source card game, and you can determine the time (offset) on the server or the other players computer you could cheat by calculating their random variables. Now it really isn't an issue in games, but it's incredibly important in security. Randomness makes up a huge component of encryption. That's why you have applications that require you to move the mouse a bit, hopefully randomly and they take in a whole bunch of other entropy fed in by the system. In Unix-like OS's you have /dev/random and /dev/urandom. /dev/random requires a certain amount of entropy and environmental noise, and it blocks on reads until it's satisfied with the output. /dev/urandom does not block, but it gives pseudo random output. For the purposes of security, /dev/urandom should NEVER be used. However neither are truly 'random'.

sharpneli 13y ago
But for any other purpose than generating private keys one should NEVER use /dev/random. If you're not sure use /dev/urandom. I've had to painstakingly explain to certain people why, as an example, erasing a HDD from /dev/urandom is allright. And why their program that simulates some random input should use /dev/urandom. But no, they babble about true randomness and then complain why they get like paltry few hundred bytes per second. Even if you have a server running casino games just use /dev/urandom/. It requires a total compromise of the server to get the internal state out of that, and in that case it's easier just to change urandom into /dev/zero.
- blueskin_ 13y ago
  If you need a lot of entropy, it's good to use a hardware RNG to keep the load down (and it improves quality).
  - 13y ago

Aardwolf 13y ago

Ivy Bridge and newer CPU's of Intel have this new "random" instruction (I still have a Sandy Bridge CPU tho). Is that one truly random enough for crypto purposes? Thanks!

fhars 13y ago
It depends on whom you trust: http://arstechnica.com/security/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/ http://arstechnica.com/security/2013/12/we-cannot-trust-inte...
Daniel_Newby 13y ago
No, and it does not matter who you trust. Analog circuitry simply has too much inbound and outbound information leakage to be trustworthy. You must round it out with a mixing algorithm.

jbert 13y ago

PRNGs (pseudo-random-number-generators) take in a small amount of randonmness (a seed) and produce a long stream of numbers from that. Anyone using the same PRNG can look at the output of yours and try to put their PRNG in the same state. If they succeed, the output of theirs will match yours - now and in the future - unless you re-seed. Two problems can occur here: 1) you seed with something they can predict. e.g. seconds since 1970 (or microseconds since 1970). If they have a reasonable sample of numbers from your system, they can try lots of different seeds and see if they can find the one which gives the same output as you. 2) PRNGs have "internal state", which is a bunch of numbers they mix together. Some PRNGs have the property that if you can you can observe enough numbers in a row from the PRNG, you can turn them back into the internal state locally and then you can do the same thing as if you knew the seed (predict future numbers).

chilldream 13y ago
> you seed with something they can predict One of my favorite examples of this ever: Once in Las Vegas a keno machine mistakenly used a fixed seed. Meaning once someone figured this out, he could show up when the game started for the day and predict what the machine would do with 100% accuracy. http://www.americancasinoguide.com/slot-machines/the-worlds-greatest-slot-cheat.html http://www.americancasinoguide.com/slot-machines/the-worlds-...

pygy_ 13y ago

put on hold as primarily opinion-based by Xavierjazz, Olli, Excellll, HackToHell, Tog 3 hours ago Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question. Stack exchange is broken. The question mixes up uniform distribution and randomness, but the answers are factual. There's little to no opinion involved here.

df07 13y ago
Give the system time to work. It's already been taken off hold.
- cruise02 13y ago
  No! A question got closed! The whole thing must be broken!
  - pygy_ 13y ago
    Hyperbole sometimes helps to get the point across... The problem with Stack exchange is that it conflates heavy site usage with domain experience and maturity. Avidity for imaginary internet points and maturity are at best orthogonal.
    - batguano 13y ago
      Excellent point, and well phrased. Still, I find the whole stack exchange system to be incredibly useful, including the original post. (Edit: And it looks like you do, too, since you point out the information is factual.)
    - bronsoja 13y ago
      As a general rule across the web, I'd agree with you. Although, I feel like on StackExcahge (or at least SO) those with the highest scores typically gave good answers in their domain as judged by their community and would not commonly give any answers outside their domain that could be voted up simply based on user rep alone. I don't really have any hard data on this, it's opinion based on seeing extremely good answers from high rep people regularly, and not being able to recall seeing poor answers from high rep users voted highly when they aren't actually useful.

chriswarbo 13y ago

When I see the word "random" I parse it as "unpredictable", since this is usually what people mean (even if they don't realise it) and can clear up many arguments. The concept of 'random' is interesting in some cases, but the vast majority of the time it's far stronger than what is required. In this case, the question is: > If a number generator is uniformly distributed, why might that not be 'random enough'? If we rephrase this as: > If a number generator is uniformly distributed, why might that be 'too predictable'? This makes the flaw obvious: there are many ways to choose numbers uniformly which are completely predictable. For example, choose the smallest value first, then choose a value which is furthest from any previously-chosen value (in, say, lexicographic gray-code order). The point here is that 'uniformity' is not the property we care about; it is a consequence of the property we care about (unpredictability). If a distribution were non-uniform, we would be better able to predict it (by biasing out predictions to match the distribution), hence the least-predictable distribution is necessarily a uniform one. Other times this comes up: > Are quantum measurements 'truly random'? That's untestable, but we can test whether they're predictable or not. > This encryption algorithm requires a source of random bits. It would work just as well with a source of bits that are merely unpredictable. > This strategy can only be defeated by a random opponent. It can also be defeated by an opponent which you can't predict. And so on.

dllthomas 13y ago
"[T]he vast majority of the time it's far stronger than what is required." Oftentimes it's also just not what is actually required. Often you want uniform spacing with some jitter, not points drawn from a uniform distribution.
sdevlin 13y ago
That is a good way to think of it. Indeed, that is how cryptographic randomness is typically defined. Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)? A generator that passes this test will pass any statistical randomness test, but the converse is not necessarily true. For example Mersenne Twister is a good generator from a statistical perspective, but it's actually quite easy to recover its internal state by observing a small amount of output. (Around 20k bits, if I recall correctly.)

mathattack 13y ago

Eric Lippert's answer is great. It isn't the distribution of answers, it's the predictability. In most cases it's ok if the distribution looks random, but in some it turns out not to be ok.

aestra 13y ago

Take a look here: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... They found a flaw in a REAL poker site because they were using a pseudo random number generator (and a stupid algorithm) and were able to know the order of the cards being used in the game! >The RST exploit itself requires five cards from the deck to be known. Based on the five known cards, our program searches through the few hundred thousand possible shuffles and deduces which one is a perfect match. In the case of Texas Hold'em poker, this means our program takes as input the two cards that the cheating player is dealt, plus the first three community cards that are dealt face up (the flop). These five cards are known after the first of four rounds of betting and are enough for us to determine (in real time, during play) the exact shuffle. Figure 5 shows the GUI we slapped on our exploit. The "Site Parameters" box in the upper left is used to synchronize the clocks. The "Game Parameters" box in the upper right is used to enter the five cards and initiate the search. Figure 5 is a screen shot taken after all cards have been determined by our program. We know who holds what cards, what the rest of the flop looks, and who is going to win in advance.

lutusp 13y ago

> Just say you code in any language at all to roll some dice (just using dice as an example), after 600,000 rolls, I bet each number would have been rolled around 100,000 times, which to me, seems exactly what you expect. Bad example. Because the author specified "some dice", we can assume more than one die, in which case some numbers have a greater chance to appear than others, in a series of fair "random" throws. It's a bad sign that the author of a piece about randomness isn't aware of the systematic behavior of his chosen example, a behavior biased in favor of certain outcomes. http://www.algebra.com/algebra/homework/NumericFractions/Numeric_Fractions.faq.question.200314.html http://www.algebra.com/algebra/homework/NumericFractions/Num...

snarfy 13y ago

The idea of something being truly random bothers me because it goes against cause and effect. An effect happened without a cause. It violates laws of conservation, entropy, determinism, and a lot of other things.

lutusp 13y ago
> The idea of something being truly random bothers me because it goes against cause and effect. Not at all. The fact that one cannot predict the next number in a random sequence is irrelevant to the fact that, in the long term, that number has a predictable relationship with other numbers in the pool of possibilities. For a random generator of the digits 0-9, can I predict the next number in the sequence? No. Can I say what the proportion of, say, 7s will be, within a large list of outcomes? Yes, and the larger the list, the more reliable the prediction. If your position had merit, quantum theory, probabilistic on a small scale, would be seen as violating cause/effect relationships, a rather important part of physical theory. But, because of the mathematics of quantum probability, individually unpredictable atoms become very predictable macroscopic objects.
sveit 13y ago
If I toss a coin into the air and then it lands on tails, there is a visible cause and effect. The velocity of my arm, the position of the coin in my hand, the moment of release, the air currents in the room all affect the outcome. If I could measure these to a high degree of accuracy and plug the measurements into a detailed enough simulation, I could predict the outcome. However, I can't. So I am unable to predict the outcome (hence the outcome is random).