Double zero, let it ride
October 15, 2014 4:30 PM Subscribe
I'm wondering whether a randomized computation (Monte Carlo, etc.) has ever gotten a string of very unlucky random numbers, computed an erroneous result, and caused a real-world problem.
I'm specifically interested in computations here, so not situations like Mississippi flooding where people were unprepared for an unlikely event. I'm also not interested in situations where a model's prediction was reasonable but the real world just happened to behave bizarrely, nor in situations where there was some flaw in the model.
I just want to know if at any point in history a serious problem has been caused solely by a source of randomness spitting out a very unlikely sequence during a randomized calculation using a sound algorithm.
I'm specifically interested in computations here, so not situations like Mississippi flooding where people were unprepared for an unlikely event. I'm also not interested in situations where a model's prediction was reasonable but the real world just happened to behave bizarrely, nor in situations where there was some flaw in the model.
I just want to know if at any point in history a serious problem has been caused solely by a source of randomness spitting out a very unlikely sequence during a randomized calculation using a sound algorithm.
The 2010 Flash Crash in the stock market was largely caused by out-of-control algorithms feeding off of each other and amplifying.
On edit, this might not be exactly what you were looking for, oops!
posted by fermezporte at 4:53 PM on October 15, 2014
On edit, this might not be exactly what you were looking for, oops!
posted by fermezporte at 4:53 PM on October 15, 2014
Best answer: With any probabilistic simulation it's basically on the researcher to understand the odds and how likely the result is anomalous. And to add more samples or or repeat the simulation with a different seed or whatever until you've come up with a chance of error you're comfortable with. Generally it's not a lot of extra work to bring the chance of error down to the point where the probability is not like winning the lottery, but like winning all of the lotteries in the same day.
This might have happened due to incorrect understanding of the probabilities, but it's pretty reasonable to assume that it hasn't happened "for real". What does happen though is statistical simulations sometimes give incorrect results because they expose subtle patterns in the pseudo-random generator.
posted by aubilenon at 4:57 PM on October 15, 2014 [1 favorite]
This might have happened due to incorrect understanding of the probabilities, but it's pretty reasonable to assume that it hasn't happened "for real". What does happen though is statistical simulations sometimes give incorrect results because they expose subtle patterns in the pseudo-random generator.
posted by aubilenon at 4:57 PM on October 15, 2014 [1 favorite]
I think you need to clarify this question. The phrase " a very unlikely sequence" is kind of meaningless when it comes to randomness. The very definition of randomness is that all sequences are equally very unlikely. Do you mean a random sequence somehow guesses a password or something..or?
posted by If only I had a penguin... at 4:58 PM on October 15, 2014 [5 favorites]
posted by If only I had a penguin... at 4:58 PM on October 15, 2014 [5 favorites]
That said, there is no way to ever definitively prove that at no point in history has someone's simulation given a significantly wrong result because of some coincidence with a probability of 10-75.
posted by aubilenon at 5:01 PM on October 15, 2014
posted by aubilenon at 5:01 PM on October 15, 2014
Though actually documented cases of extremely unlikely things happening do tend to get a lot of attention, so maybe we would have heard about it.
posted by aubilenon at 5:03 PM on October 15, 2014
posted by aubilenon at 5:03 PM on October 15, 2014
Best answer: You may be interested in the idea of Weak keys in encryption. With some small probability, many popular encryption algorithms will be highly insecure. This is widely studied by cryptographers seeking to find bigger holes in these algorithms. But to my knowledge no one has ever chosen a weak key by chance -- we're talking less than one in a quintillion odds.
posted by miyabo at 5:03 PM on October 15, 2014 [2 favorites]
posted by miyabo at 5:03 PM on October 15, 2014 [2 favorites]
Some long time ago (1960?), the RAND corporation published a book of a million random digits. This was before calculators and computers made random numbers available to everyone. Naturally, everyone used the first N numbers in the book. I heard on the grapevine long after that 1. the digits were proven later to be not so random, and 2. some wrong results were published due to either the reuse of the first numbers or some bias in the data set. Unfortunately, I can't cite an example, but it's a lead.
posted by SemiSalt at 5:06 PM on October 15, 2014 [4 favorites]
posted by SemiSalt at 5:06 PM on October 15, 2014 [4 favorites]
I imagine what you're talking about is something like the opening scene in Rozencrantz & Guildenstern Are Dead. But, no, I can't say I've heard of any such case.
posted by mr vino at 5:36 PM on October 15, 2014 [1 favorite]
posted by mr vino at 5:36 PM on October 15, 2014 [1 favorite]
I am old enough to have used random number books and were specifically not supposed to use the first one. You were supposed to randomly pick your first digit from a table randomly selected from the book. Blindfolded darts players may or may not have been involved.
posted by fshgrl at 5:50 PM on October 15, 2014 [2 favorites]
posted by fshgrl at 5:50 PM on October 15, 2014 [2 favorites]
Best answer: I ran into this on the internet today (possibly via news.ycombinator.com) and it is related to your question. In this case, a bug arises only when the random number generator's output is exactly zero. Some random number generators will output exactly zero, while others won't. But even those that do, do it very rarely (on the order of say 1 in 2 or 4 billion trials), so it's easy to overlook the bug in testing and then have it trigger at an inopportune time.
Indeed, it’s rare, and it took a while to reproduce. I took several billion Gaussian-distributed samples from it before I saw it fail. The numerology of that rarity alone made me suspicious of where the problem might lie. I’ve seen bugs that fail at a ~1 in 2^32 rate before. One way they happen is when someone’s confused about whether a 32-bit integer interval is open or closed… meaning, a number (a 32-bit int normalized to 0..1, say) is said to be “between 0 and 1″ but it absolutely matters whether it’s [0,1] versus (0,1). And that’s where the bug turned out to be.posted by jepler at 7:19 PM on October 15, 2014 [3 favorites]
RonButNotStupid: If any given random numbers are having a significant impact on the overall computation, then either the method isn't doing enough sampling or those random numbers aren't random.Completely untrue. Proof:
Given completely random numbers, any given sequence of digits is possible.
Some sequence of digits can have a significant impact on the overall computation (otherwise, the inputs are unrelated in any significant sense to the outputs).
Therefore, a *true* random number generator can have a significant impact on the overall computation.
posted by IAmBroom at 8:56 AM on October 16, 2014 [1 favorite]
Some long time ago (1960?), the RAND corporation published a book of a million random digits. This was before calculators and computers made random numbers available to everyone. Naturally, everyone used the first N numbers in the book.
I believe I've heard this, too, in a research class I believe. If it recall it was particularly about the pitfall of just using the first page of random digits in the book repeatedly.
But, in spending some time trying to find sources for this situation, I can't find any. So it might be just a oral tradition of some sort.
posted by flug at 9:18 AM on October 16, 2014
I believe I've heard this, too, in a research class I believe. If it recall it was particularly about the pitfall of just using the first page of random digits in the book repeatedly.
But, in spending some time trying to find sources for this situation, I can't find any. So it might be just a oral tradition of some sort.
posted by flug at 9:18 AM on October 16, 2014
Here is an interesting situation that is at least close to the one you are asking about.
It involves a Monte Carlo simulation that relies on a pseudorandom number generator. For whatever reason the pseudorandom number generator used had a subtle bias and this interacted with the particular model being simulated via Monte Carlo simulation to give systematic incorrect results. Specifically, they were using the Wolff algorithm and the results systematically gave energies that were too low and specific heats that were too high.
What is interesting here is that it is known that pseudorandom number generators are not really random, but they pass various statistical tests like having a nice even distribution of results and so on. So it is really somewhat unexpected for the subtle bias of the pseudorandom number generator to interact with another algorithm in just exactly such a way as to introduce a bias in the final results. But apparently, it happens!
Found this info in Monte Carlo By George Fishman (Springer), page 588.
posted by flug at 9:26 AM on October 16, 2014 [2 favorites]
It involves a Monte Carlo simulation that relies on a pseudorandom number generator. For whatever reason the pseudorandom number generator used had a subtle bias and this interacted with the particular model being simulated via Monte Carlo simulation to give systematic incorrect results. Specifically, they were using the Wolff algorithm and the results systematically gave energies that were too low and specific heats that were too high.
What is interesting here is that it is known that pseudorandom number generators are not really random, but they pass various statistical tests like having a nice even distribution of results and so on. So it is really somewhat unexpected for the subtle bias of the pseudorandom number generator to interact with another algorithm in just exactly such a way as to introduce a bias in the final results. But apparently, it happens!
Found this info in Monte Carlo By George Fishman (Springer), page 588.
posted by flug at 9:26 AM on October 16, 2014 [2 favorites]
« Older I am freaking out majorly over a new relationship.... | Best Format for Mobile Emergency Phone List Newer »
This thread is closed to new comments.
Monte Carlo methods work by repeated random sampling. If any given random numbers are having a significant impact on the overall computation, then either the method isn't doing enough sampling or those random numbers aren't random.
posted by RonButNotStupid at 4:48 PM on October 15, 2014 [4 favorites]