Researchers are one step closer to adding probabilistic processes to deterministic machines
A Long-Term Computing Problem - Simulating the Dice Roll
Here's a deceptively simple exercise: Come up with a random phone number. Seven numbers in a row, chosen so that each of them is equally probable, and so that your choice of the next number does not affect the choice of the next. Most likely, this will not work for you. You can not take my word for it - research conducted since the 1950s shows how we are not random from a mathematical point of view, without even realizing it.
Dont be upset. Computers don't generate random numbers either. They shouldn't - the programs and hardware of computers run on Boolean logic , not probabilities. "Computer culture is based on determinism," said Vikash Mansinhkawho runs a probabilistic computing project at MIT - and it shows up at almost every level. "
However, programmers want to create programs that run with randomness — sometimes tasks require it. Over the years, ingenious algorithms have been developed that, while they do not generate random numbers, offer clever and efficient ways to use and manipulate randomness. One of the most recent attempts has been made by Mansinhee's group at MIT, which is about to present their Fast Loaded Dice Roller , or FLDR, algorithm at an international conference on AI and statistics in August.
In simple terms, FLDR uses a random sequence to perfectly simulate a cheating die (or a badly weighted coin or marked cards). “He shows how to turn a perfectly random coin toss into a distorted one,” said the mathematicianPeter Bierhorst of New Orleans University. Birhorst was not involved in this study, but he considers the premises underlying FLDR to be “compelling”.
FLDR will not give you an advantage when playing Monopoly or at the Las Vegas craps tables. However, its creators say it allows random numbers to be integrated into natively deterministic software or hardware. Incorporating such uncertainties will help machines make predictions more human-like and better simulate events based on chance, such as climate or financial markets.
Randomness is a more complex concept than it sounds. Each digit in a sequence of random digits where there is no discernible pattern, the probability of occurrence is the same. For example, the number π is not random, but it is believed that by this definition its numbers are random (mathematicians call it "normal"): each digit from 0 to 9 appears approximately the same number of times.
And although you can find "random number generators" on Google, there won't be pure chance. Today's processors, search engines, and password generators use a “pseudo-random” method that is “good enough” for most tasks. Numbers are generated using complex formulas - however, in theory, knowing the formula can predict the sequence.
Scientists have been trying to build real randomness into machines for at least 80 years. Until then, random numbers were taken from old and reliable assistants - they threw dice, took out balls with numbers from a well-mixed bag, or used other mechanical devices. In 1927, a statistician sampled the census data, compiling a table of 40,000 random numbers.
Vikash Mansinkhka, Probabilistic Computing Project Manager at MIT
The earliest sources of random numbers were physical machines. The first random number generator was invented by British statisticians Maurice George Kendall and Bernard Babington Smith, who described it in 1938. The car was placed in a dark room, and there it turned a disk, divided into 10 sectors, numbered from 0 to 9. When someone pressed the button at irregular intervals, brief flashes of neon or sparks illuminated the disk, snatching it out of the darkness, it seemed a frozen image where only one number was visible. A later machine, Ernie, used noise in neon tubes. Since 1957, she has been picking winning numbers in the British lottery.
Later, in search of truly random sequences, computer scientists, according to Birhorst, had to turn to natural phenomena such as relic radiation or unpredictable quantum systems. “There are truly unpredictable random processes in nature that can be exploited,” he said. "An electron reflecting to the left or to the right cannot tell in advance what it will do."
However, chance alone won't get you far. By the late 1940s, physicists began to generate random numbers that fit into a given probability distribution. Such tools - theoretical versions of the NOS cubes - worked more precisely in real situations, such as traffic congestion or chemical reactions. By 1976, computer science pioneers Donald Knuth and Andrew Yaopresented an algorithm capable of producing random samples of any array of weighted results based on a sequence of random numbers. “This is the most time efficient algorithm you can think of,” said Fera Saad, a graduate student at Mansinkhke's lab who led the FLDR.
Unfortunately, Saad says, the algorithm makes a compromise known among computer scientists: many fast-running applications use a lot of memory, and applications that use little memory can take very long. Knuth and Yao's algorithm falls into the first category, which makes it elegant, but too memory-intensive for practical use.
However, Saad came up with a clever move last spring. He realized that if the sum of the weights of the cube digits is equal to some power of 2, the algorithm turns out to be efficient both in memory and in time. Imagine that for a six-sided cube, the weights 1, 2, 3, 4, 5, and 1 are added to the probabilities of rolling out numbers from 1 to 6. That is, the probability of rolling out 1 is 1/16 and 2 is 2/16. As a result, the sum of the weights is 16 - or 2 4 - and the algorithm turns out to be efficient both in memory and in time.
Fera Saad, PhD student at MIT
But let's say the weights are 1, 2, 3, 2, 4, 2, which adds up to 14. Since 14 is not a power of 2, the Knut-Yao algorithm will require significantly more memory. Saad realized that one could add extra weight so that the weights always add up to a power of 2. In this case, you can add a fictitious face with a weight of 2, and then the weights add up to 16. If the algorithm chooses a real face, this value is recorded. If it is fictitious, the value is discarded and the algorithm starts again.
This is the key to the effectiveness of FLDR, making it a powerful simulation tool. The amount of extra memory for extra throws is negligible compared to the large amounts required by the original version of the algorithm.
FLDR makes the Knuth-Yao algorithm efficient and provides an opportunity to expand its scope. Climate change simulations, crop predictions, particle simulations, financial market models, and underground nuclear explosions are all dependent on random numbers distributed with weighted probability. Also, random numbers are at the heart of cryptographic schemes that protect data transmitted over the Internet.
Mansinkhka says FLDR can help researchers find ways to integrate probability into computer processors, his lab at MIT is doing this. The algorithm can help improve software libraries and new processor architectures that can generate random numbers and use them efficiently. This would be a significant change from the deterministic Boolean machines we are used to.
“We might have a good chance of integrating randomness into the building blocks of software and hardware,” he said.
See also: