John Hunter Good point, the series won’t last an infinite amount of time and they only have a finite amount of time they can actually film. My suggestion is handle the videos as a supertask with each video taking half the time to make and coming out twice as quickly as the last one. That way they could release an infinite series of videos using only a finite amount of material. :)
Good god. That is a brilliant idea to keep the show alive for infinite time. I love it. Only problem is the host and the technical staff need to be able to handle it (if people were able to do it then humanity would reach a whole new level).
Sripad Kowshik Subramanyam Reminds me of the old joke about the chemist, the engineer and the mathematician who go vacationing in a cabin in the woods. One night the chemist wakes up and sees a fire on the stove. He quickly looks around, finds some inert powder in the cupboard and dumps it on the fire to put it out. The next night the engineer comes in and sees another fire on the stove (none of them are apparently great with kitchen safety). The engineer thinks for a bit about how much water he’ll need to dowse it, goes and grabs their water canteens and pours out just enough of them to douse the flame. The third night the mathematician comes in and sees yet another fire on the stove. He quickly grabs his notepad and starts vigorously writing down equations. A few minutes later he smiles, puts the pad down on the table and says “A solution exists, QED,” and goes back to bed. 😄
Who says their need to be infinitely many *distinct* episodes? Let n be the number of the last episode. Then every episode e_k with k>n is defined to be equal to episode e_n. Voilà, infinite series. :^)
It is not that precise, it is stated in the video that radiation and things like that are random, while in reality they are not random, it is close to impossible to replicate and things like that, but it is not truly random. Maybe Veritasium or Vsauce had a video about true randomness where it is described a lot more precise. Even a service like random.org which collects electromagnetic background noise from antennas is not truly random, that noise has a source. I don't think true randomness exists, but we can get fairly close.
This is such a massively important topic. This issue alone has contributed to literally hundreds of thousands of dollars of my lifetime income. You've done a fantastic job of explaining a topic that, in interviews, I've found software engineers with over a decade of experience manage to get completely wrong.
@@konstantin7596 implementing telecom encryption from spec, writing and verifying secure code through static analysis, reverse engineering, and automated testing, that sort of thing.
This was a great video, but i feel like the definition of randomness was a little vague. It would be great to see a video on Kolmogorov complexity to get a more in-depth insight on randomness. Im loving the computer science direction of this channel and i can't think of a better topic to cover!
I'm sure the definition of randomness was vague because the video focused chiefly on psuedorandomness. However, it's pretty difficult to define randomness. When I took mathematical statistics for my BS in mathematics, we focused on randomness being the tendency of the image of a random variable to resemble the composition of its PDF/PMFs as the number of samples grows arbitrarily large. For instance, the PMF of flipping a fair coin is Pr(X=x) = 1/2, x∈{Heads, Tails}, so if a flip of a fair coin truly is random, then flipping it an arbitrarily large number of times should give a 1/2 chance for each side. However, if there were another process involved, such as having to choose one of four coins with replacement each flip, where one coin is fair, two gives give heads 75% of the time and the last gives tails 75% of the time, then if the process truly is random, the outcome should resemble the composition of those functions. Additionally, as mentioned in the video, we should expect randomness to not exhibit any identifiable pattern. However, this isn't immediately disqualifying of something as being random. For instance, I could roll a d6 18 times and get 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6. This is extremely unlikely, but can happen under a truly random system. Ultimately, though, this pattern should not continue for arbitrarily large sequences. Also, again mentioned in the video, an important aspect of randomness is irreproducibility. You should expect no two random processes to give the exact same output, though if you are extremely unlucky (or extremely lucky!) you might have to observe for a bit before the outputs diverge. In this last season of Doctor Who, there was an episode where people are living in a simulated reality, and they learn of this because any group of people calling out random numbers at the same time always calls out the same sequence of numbers because, as explained in the episode, computers can't generate truly random numbers (quantum computers should allow true random number generation, but that's beside the point). Ultimately, though, randomness by its very nature is difficult to precisely define. It is easier to identify what *is not* random and trim it away, like an asymptotic game of mathematical jezzball.
John D. Cook wrote an interesting blog post on the topic: www.johndcook.com/blog/2012/04/19/random-is-as-random-does/
7 ปีที่แล้ว +2
Why not define randomness in relation to an observer? If an observer can't predict the sequence, then the sequence is random for that observer. That definition does away with the whole problem. The old "true randomness" requires a sequence to be unpredictable to all possible observers. That is problematic, as we don't know what observers there can be. If there is a god, he would be an observer?
Lars Pensjö This is very similar to Kolmogorov Complexity. A series would be considered random if the shortest program that could generate the series is the length of the series plus a constant
I just put the numbers 0 - 9999 into a spreadsheet and ran the Middle Square Algorithm on them. A few curiosities arose, which signify reasons it's Bad News for purpose.... 1) There are 20 ways to produce a 0000 value. As 0000 has period 1, there are multiple ways to end up in this sinkhole. 2) Nearly 39% of the seed numbers can NEVER be produced this way. 3) A further 35% of sees numbers can only be produced by one other four-digit value 4) The number 5625 can be generated twelve ways. 2500 can be generated eleven ways (including itself). You might expect a number or two out of 10,000 seeds to be very popular, but knowing what they are means they're very predictable. In reality, you're not producing random numbers [0,9999] : you're producing numbers [0,6109] with a ton of spaces and biases scattered within....!
MS is an old algorithm, not the best one. But in April of 2017 people have implemented a Middle Square Weyl Sequence PRNG. It is a modified version of MS and instead of [0;9999] produces [0;2^32-1] possible values. It fixes alot of problems of MS, and passes every statistical test. Just take a modulo of the returned value (for example mod 16384), and check the distribution. It should be uniformal. Note: `s` is the seed. To initialise `s` take a random even number and add 0xb5ad4eceda1ce2a9 to it. en.wikipedia.org/wiki/Middle-square_method#Middle_Square_Weyl_Sequence_PRNG
Knuth (volume 2 of The Art of Computer Programming) has lots of analysis and practical algorithms for pseudo-random numbers. Simple recipe: pseudo-random numbers (one of his algorithms) followed by another neat procedure of Knuth's which is shuffling the numbers in an output buffer. Another book, "Numerical Recipes", refers to this. Numerical Recipes has references to Knuth. You can order the Knuth book and Numerical Recipes at any good bookshop. Beware: these are weighty books with a heavy price tag. Also look up "primitive polynomial modulo 2" which gives you a sequence which only repeats after a looooooooooong time. It's fairly easy to find tables of these, i.e. someone has calculated some of these "primitive polynomials modulo 2". (Knuth describes these.) Pick one which has a long repeat period, and the result is a trivially-simple recipe to make a stream of bits which repeats after an amazingly long time, i.e. longer than the age of the universe. Using this as the basis of a random-number generator gives a very fast and simple algorithm. Look at tests of random number sequences: if you think you have a random number generator, there are ways of testing it, so hook up your RNG (Random Number Generator) to one of these tests to see how it behaves. The web has lots of information on this. Wikipedia, for example, has descriptions of ways of testing random numbers. So do other mathematics-related web sites. The tests are generally easy to perform. I've also experimented with prime numbers. Find a sequence which can be quite simple, based on addition modulo the prime number, and (importantly) repeats with a period of your favorite prime number. Have several of these in parallel, each based on a different prime number, and the period of the resulting generator will be something like the product of all of the prime numbers. If you have 6 prime numbers which are of size about 1,000,000 then the composite behaviour will repeat with a period of about 1,000,000^6.
AFIK - The best random number generators are based on cryptology functions. Or, one could just as easily say that cryptology methods are based on random number generators, since the whole point of cryptology is to take a message and create a patternless sequence of numbers. This video barely scratched the surface of random number generators. I asked a predoctoral math teacher if she had considered random number research for her doctoral thesis. Her reply was that she should have. There was a lot of research opportunities available. And that was maybe 20 years ago, so more research must still be available.
Inverse transform sampling is great in theory; in fact, when I needed to generate numbers from a distribution a few years back, it was my first instinct despite not knowing what to call it at the time. Turns out, though, that - well, I'll let Wikipedia tell you: "For a continuous distribution, however, we need to integrate the probability density function (PDF) of the distribution, which is impossible to do analytically for most distributions (including the normal distribution). As a result, this method may be computationally inefficient for many distributions and other methods are preferred." And that's how I discovered the Box--Muller Transform. Marvelous bit of work that actually will give you a normal distribution.
Ooh! That drifting numbers background really did a number on the video quality. No pun intended. Tom Scott did a video on the topic called "Why Snow and Confetti Ruin TH-cam Video Quality" (at least I think that was the title) which gives a basic explanation of the phenomenon if you're interested.
65 days quarentined. frist weed i get, i came to watch your videos. Amazing. I understand the Maths, but not why I'm doing this to myself. Congratulations on the video.
Knuth in his book pointed out that a randomly generated random number generator does not necessarily generate good random numbers. He discusses an algorithm he designed using things like a human's height and other imponderables. He wrote the code for it and set it to work. Though it had a space of 32 bits (if I remember correctly), if cycled with a period of 12.
One thing I'd add to this (very good) video is that uniform random numbers, besides having a constant probability density, have to be also *independent*. So every number has to be equally likely regardless what preceded it. Congruential generators might have a hard time achieving this since they essentially loop over the domain defined by M - and it's of course heavily dependent on the chosen A and C. Selecting primes for these parameters is usually a good start...
It's true that a pseudo random generator must eventually repeat. However, it's not true that it must happen as soon as it hits the same output again. SRGs can have hidden state. Stuff inside the black box that isn't part of the output. That way they may effectively loop through all possible outputs not in just one way but, in fact, potentially in all possible orders. Similarly you can build them such that they occasionally spit out the same value twice in a row without falling into a loop where they spit out ONLY that one value. They have to repeat only once their entire state (hidden state plus output) is hit again. And that could take a LOT longer than hitting every possible output once.
adding irrational number (or in actual computer case, very very accurate decimal one) to the seed on every step will cause the cycle be so long the existence of humanity will come to end faster.
You're right, but that's just deferring the problem - if you had N non-hidden states and H hidden ones, then your period is going to be (at best) N*H, so you're essentially back to square one.
I don't really see a problem here... I just pointed out that a PRNG can through the same outputs a *lot* of times before starting to repeat. Of course if you want to go through all possible sequences you'll need to have H*N >= N! or, if you want to allow for arbitrary duplicates, it ought to be H*N >= N^N. That's quite a tall ask, usually. (that's just numerically. You'll also want to satisfy some properties to actually generate the desired sequences) But why stop there? What if, not only you want to run through all permutations, but you want to permute the order you run through the permutations? The numbers obviously become insanely huge long before we even get to that point. Too large to contain on a computer. (By N=59, N! exceeds the estimated number of atoms in the observable universe, N^N clears that by 48)
Fun side note, in the 1960s and 1970s IBM had a random number generator call “RANDU”. Donald Knuth, the author of the seminal book “ The Art of Computer Programing”, call it “Truly Horrible”. Once the flaw came out, it called into question a large number publish papers that used this function for simulations.
" in the 1960s and 1970s IBM had a random number generator call “RANDU”. " Yes, I think IBM's reply to a query about that was "We guarantee that each number individually is random, but we cannot guarantee that more than one of them is random."
Another nice thing about picking 2^32 as your m is that 32-bit computers would do it automatically. That's just how many bits they have, so any bits after that would just get lopped off. No additional computation required.
Mersenne Twister isn't a linear congruential generator. It's a linear feedback shift register. For the normal distribution, one normally does not use the inverse distribution function, because that's not expressible in closed form. Instead, one generates two normal variates at once, because the distribution function of the radius (in polar coordinates) of a 2D normal distribution is in closed form. There are at least two ways of doing this.
1. The state of a PRNG can be larger than the last bits of randomness it generated. 2. Cryptographically secure pseudo-random numbers cannot be distinguished from truly random numbers with limited resources, so unless your program is galactical size it is guaranteed you won't notice a difference. CSPRNG are typically significantly slower than PRNG in general. 3. The period of the most used Mersenne Twister is much larger than 2^32.
The Mersenne Twister is really generating 19937 bit numbers. The code only gives you 32 bits at a time, giving the appearance that the numbers are repeating within a cycle but that isn't the real size of the output. If you consider the actual output value, then the period is exactly 2^19937 - 1 which is what she meant. If you consider all the inputs to the generator, then there can be no hidden state. If there was state that wasn't dependent on the input, then you wouldn't have a PRNG, since it could produce different outputs for the same input. With these technical considerations, what she said is correct, you can't cycle longer that 2^outputbits. It is just a bit more nuanced.
The speed thing rather depends on your implementation constraints. For example a CSPRNG based on a block cipher in CTR mode can be implemented in a parallel form that can be extended as far as is required to get the speed that is required. For many non cryptographic RNGs, like for example XORSHIFT or PCGs, this is not the case. The CSPRNG in most modern desktop and server CPUs is designed to exploit this parallelism. The worlds fastest production RNG is a CSPRNG that is frequently reseeded (0.5 to 1 millions times a second). I noticed that the video states that the Mersenne Twister is the gold standard, which is laughably false. Also the stated procedure for random fractions doesn't yield a uniform distribution when tried with floating point arithmetic. Especially if you do the multiply before the divide pushing the first term into the lowest resolution end of the floating point representation. It's easy enough to make uniform floats, but the method in the video is simply wrong.
Good job! You explained the idea clearly and precisely. One thing I am still wondering is why the inverse distribution of uniformly sampled cumulative probability densities of a normal distribution becomes a normal distribution again. You have given us a very good example using the heights of US women in the video. I think I will do some more research to find a mathematical proof to convince myself.
Ah, Linear Feedback Shift Registers! The Playstation 2 had them on the VPU1 (sort of a vector shader before there were GPUs) and I naively used them to create x,y,z coordinates for snow and rain sprites. It looked fine as long as just a few dozen were generated, but as more were added a pattern would show; all points confined to a few slanted columns. Caused a lot of head scratching; ended up using LFSR for x, a Linear Congruential Generators for y and for z something like z' = frac( z + GoldenRatio). Thought it was a hardware issue but found out later it was a problem inherent to LFSR.
I wrote a random number program in an old HP 41CX calculator. It was simple. Extract the 1/10th of a sec digit, set it next to the previous extraction in the alpha register, and when you have the number of digits wanted, execute AMUN and presto, a real random number appears in the X register. Requires a, or several, random execution or presses of the key assigned to extract the digit from the clock.
I think its important to point out that the internal state of a PRNG is not required to be the same size as the output value. In any "good" implementation your period will be much larger then the resulting set. IE using a 64bit (or larger) internal state and returning a 32bit value. It is also important to note that many PRNGs apply functions to the output bits in such a way to protect that internal state from leaking out, such as a hash. X_n+1 = (X_n * a + c) % 2^64 return hash(X_n) & (2^32 - 1)
I think it’s diabolical that this is the _only_ video I found that _actually gives a valid equation._ Like, I’m looking up random number generator, why aren’t you giving me one?
I'm showing this to all my coworkers. Really good way to explain how things work behind the scenes for all those different distributions in various random modules/libraries
In the case of the linear-congruential generator, you could increment the value of c after every pass, so with the right values of m, a, and c, you could have a period of m^2 instead of m.
Though storage was briefly alluded to, the statement that using a “natural” sequence (e.g. via a Geiger counter) isn’t repeatable, isn’t strictly correct, e.g. if one stores the sequence thus generated. While it’s obviously more efficient to use a pseudo-random generator, storing and retrieving a sequence that’s many times the period of a typical pseudo-random generator (e.g. 2^32) isn’t all that impractical in this age of relatively fast storage. And some simulations do require much longer sequences than the periods of typical pseudo-random generators.
Ok so this might also be nitpicky but a parabola may follow a quite a bit more complex parametrization than that. For instance: a / b² x² - sin(2α) (x-x0) + (1 - cos(2α)) (y-y0) = 0 This is the parabola you get if you have a constant gravitational field pointing down with strenght "a" (if a is negative it points up instead), and you throw a ball with starting velocity "b" in a direction dictated by "α" when you at first stand on "(x0, y0)". It includes all 2D parabolas that are aligned with the x and y axis. (In fact it has more parameters than necessary. You could do the same with y = a x² + b x + c) But of course you could also want freely rotated parabolas (which would involve an extra parameter giving that angle) or you could look parabolas in higher dimensional space...
LegendLength - maybe nit picky but try to estimate e.g. the likelihood of generating a Higgs at the LHC via the standard model using, e.g. the Merssene twister - only pointing out that when a sequence longer than the period of the standard pseudo-random generators is required one can in fact generate it and also have repeatability via storage and that can be done feasibly.
Afaik, since prng needs a seed seuence to extract entropy from, you must have a cache of real random inputs to run one. Windows supposedly does this by logging assorteed junk data like time keystrokes mous pointer position and various network info at predetermined times into an ever expanding cache of just random strings.
In the case of banking systems for example with tokens, the seed is the current time since we assume that the laws of physics at the surface of the Earth remain constant such that if your phone clock and the bank systems clocks are synchronized you both get the same generated number through the implemented algorithm. If however one would go a bit higher, let's say low Earth orbit, then the time will differ due to general relativity. You will be unable to login to your bank account from space if you don't correct for the time difference due to earth gravity.
I actually came up with a random algorithm called XSR for XOR with Shifting Right. It passes many random tests, and is faster and even better than the Mersenne Twister when stacked up.
One problem alluded to, but not mentioned explicitly with pseudorandom vs random numbers, is that truly random integer sequences could have exactly two (or "n") identical numbers in a row (for example with p=1/1e6 for rolling a thousand-sided die twice) , whereas for pseudorandom sequences, if there are two identical numbers in a row, there must be ONLY that number forever after. Therefore using pseudorandoms pairwise (over the entire range of possible numbers) would never give you the same distribution you would see in actual random sequence.
I love the show! Keep it up guys and galls! Although the reasoning for obtaining a normal RV from a uniform RV follows from the inverse transform method (as you've illustrated), I'm a bit scared that this might be advocating its use for this case rather than the Box-Muller transform in order to obtain normal variates, which is much easier (and safer) to implement on a range of platforms and in fact much more elegant! (Save for the fact that you might be throwing an unneeded normal RV away or donating it to charity, but who in this simulation driven world only requires a single normal RV - am I right?) For the Inverse Transform demonstration I would've used a Pareto / exponential distribution (granted, it would not produce nice S curved graphs as the normal CDF does, but it does give the opportunity of quickly doing an on-screen algebraic manipulation to arrive at the desired RV, which always makes my heart sing :-) )
This video really clarified computer "randomness" for me. I always wondered why they didn't use a hardware solution or query the last few digits on the second on an atomic clock. It makes a lot of sense that for the purposes of debugging this would be bad. Thanks!
There were a lot of issues regarding pseudo random generators (Java 2013, Sony 2010, OpenSSL 2008), but that doesn't mean hardware generators are better and humans definitely aren't. Hardware generator even those which uses radiation reader could be "hacked" by putting another device near it (ofc it requires physical access to that machine but that's always the case). Numbers/phrases generated by humans are even less random that simple PRNG. It could be determine base on that person knowledge, habits, friends how probabilistic is that he will chose exact number/character in sequence.
Was it just a coincidence that the probability density function looked like the derivative of that cumulative distribution of heights? It appeared to be exactly that and I think that makes sense but I've not seen such an elegant link between statistics and calculus before that.
What is "truly" random in every day life is more of a philosophical question than a mathematical one. If a poker website has a RNG that combines seed from micro temperature fluctuations, internet traffic, number of players on website and other variables, I'm going to call it random for the purpose of me trusting the website to deal me cards "randomly".
I hope there's a follow up episode on some of the tests used to gauge a PRNG's statistical randomness. Looking at the 3-dimensional planes generated by LCGs is a pretty direct way to see how bad they are (in that respect).
at 8:20 you say that the distributions of the random number generators is uniform. But isn't this only the case when the period of the sequence is equal to the size of the interval? If so then the Middle-Square Algorithm will never have a uniform distribution (the maximum period was less than the interval), and the Linear Congruential Generator will only have one when "good" values are chosen (such that the period=m). I would be interested to see another episode going into more detail about how these "good" values are found, and about the actual distribution of the Middle-Square Algorithm (as it is not uniform).
(Weird comment from game programmer on getting away with sampling a PRNG with a small period. Ignore as needed :P) Interesting thing WRT period for procedurally generated content (eg game levels) is it doesn't necessarily have to be particularly large. You are advancing the PRNG through it's sequence every time it is sampled, but you can sample it in such a way that the repetition is not apparent to the player. For example, if we have a small period PRNG determining the heights of tiles in a level, it will become apparent if the period is significantly less than the number of tiles generated. But if we generate a tile's height and then before we sample for the next tile we sample the PRNG a second time or more ("how many blades of grass are on this tile?" or "Shall we place a monster here?" - "Which direction is the monster facing?") by the time we get to calculating the next tile's hight, the PRNG could be at a (psuedo) random point in it's sequence. The sequence repeats but less noticeably for something the playing will recognise (tile heights) unless the player can view a lot more of the generated level. This can work against us too though; a program sampling a PRNG can request random numbers in step with it's period, so every tile would have the same height, and the same number of blades of grass, the same monster spawned. Or if the program made periodLength/2 samples for a tile, every ~other~ tile will be the same. This is largely irrelevant these days since most computers can comfortably generate very long pseudorandom sequences, and do it very quickly. But it is a trick that can be used if careful and when computation power is extremely limited :)
And I was watching a video from GDC of some game devs talking about procedural content, which usually makes use of pseudorandom numbers just this afternoon.
Good point. And just to unpack your comment a bit for other people: The period of the common Mersenne Twister generator is 2^19937-1, which is called a Mersenne Prime.
Inverse Transform Sampling should also generate pseudo normal distribution because probability at each point is different but in this case, it will be constant for given ranges however short we go.
This demonstrates the difference between a mathematician and an engineer. The problem was defined with 2 significant digits. The answer can only possibly contain 2 significant digits. You don't pick up more. So, the baseball rulebook is correct. The correct answer to this problem is "12". The trailing ".019" is meaningless. Great videos, sir. Keep them coming!
how do computers pick the a, m, and c for the linear congruential generator? do companies all use the same one? do they use a different pseudorandom number generator to pick them?
Roll20 uses the true random hardware source to periodically re-seed its pseudorandom number generator (probably every few minutes for each user session).
Custom hardware for randomness is less and less of a problem, now that basically every consumer computer (including phones) comes with a camera in it. Random movement of electrons in the CCD sensor produces thermal noise that you can use. Note that this does not depend on actual light entering the camera.
Hi Nathan, you are right, a web cam can be used. I made a web base tool some years ago that works inside the browser an captures the web cam to generate random numbers. You can put a sticker on the cam and the sensor still it generates pixel noise. For poeple interested in it: retura.de/camrng/camrng.html Its in german...klick on "web cam aktivieren" to start the capturing and then on START. The graph then shows the quality or "randomness" of the data, by calculating PI with a monte-carlo simulation and the rate between ones and zeros. Greetings David
How would you go about proving that a given SRNG is uniformly distributed? how does the Mersenne twister improve upon a linear congruential generator? What are some common randomness tests? I feel like there's a lot this video just glossed over; some further reading would be appreciated.
OK, this is kind of a nit, but a bit after 10½ min, the CDF that's plotted doesn't appear to correspond to the stated µ and σ values of 162 and 5. For other readers ('cause I know you know this), in a normal distribution, about 68% of data fall between µ±1σ; about 95% fall between µ±2σ. So while the mean on the plot (µ=162) is fine, at µ-1σ = 157, it should be 0.16; it looks more like half that. And at µ-2σ = 152, it should be 0.025; it looks more like 0.01 or less. I bother to point this out because I really admire what you've done here in presenting a subject that can be very perplexing even to some pretty smart people. I find your explanations just right on the simplicity/complexity scale, and your illustrations with numerical examples seal the deal. And what I point out above, doesn't detract from the overall high quality of this; I just think it might catch one or two other viewers' eyes. Rolling back to ≈9½ min, it looks as though the PDF is plotted correctly, but that the highlighted central region as shown, is µ±½σ, which has *width* = σ, when what should have been plotted was µ±1σ which has *radius* = σ. This may have led to the incorrect CDF plot, if σ=2.5 got used to make that plot. E.g., in the table at 11:24, CDF(154.5, 168.4) are shown as occurring at (0.0671, 0.9), which seems good, considering that CDF(157, 167) = (0.16, 0.84); while those values on the CDF plot don't seem to fall at the right heights. Also, I found it odd that you never mentioned one of the most common ways to generate a "random" seed - the least significant several bits or digits of the computer's internal clock.
Very cool, I had never heard of inverse transform sampling before. I can think of a few programming applications where it would have been useful. Thanks!
You had a video about normal numbers half a year ago. These are exactly the numbers x in [0,1] such that the sequence x_{n+1}=10 x_n mod 1 equidistribute in [0,1]. I'm not sure how close is the connection to pseudo random numbers, but it is true that almost every number in [0,1] is normal (so it is a "good seed").
So when I use R or Stata to simulate a normally distributed set of numbers, even if I simulate a large number it often deviates from what a standard normal distribution is supposed to look like--sometimes by pretty noticeable amounts. Why is that so if the program is just basing its values off of the equation for the CDF?
Two possible reasons. (1) It takes a lot of deviates for the curve to start looking nice, like a few million. (2) Not all algorithms are perfect.I use Zignor. I don't know what R uses.
Hey!! I think there's a way to generate random numbers from a deterministic process. We can take the square root of 2 or 3 or any such imperfect squares. We get a sequence of truly random numbers. We can then tell the computer to select four numbers sequentially and thus we create a series of random numbers from a deterministic process. Would be glad if you could answer it. 😄😄
Learning Tutorials The digits in sqrt(n) aren't random, because you can algorithmically generate the next number. If there's an algorithm to generate the next number in the sequence, then it's by definition not random.
"a way to generate random numbers from a deterministic process" - what if that deterministic process takes more and more time and information, the farther you go in the sequence? Each digit takes more time to compute than the previous digit.
+David Johnston Because its a single well known sequence right? But say someone went ahead and calculated a section of it that is as of yet unknown, and presented it on its own. Could that be considered a random string?
Surely comparing the Linear Congruential Generator with the Middle Square Algorithm at 5:49, and asking which sequence looks the most random, is an unfair comparison? They have different moduli- the MSA has mod 9999, but the LCG has mod 7829. Small sample nonwithstanding, the two sets provided are inherently different.
9:00 just to clarafy that it will never actually be 1. The way it's implemented on practice doesn't allow it, and if it would happend all sorts of os-crashing level of glitches would happend.
9:56 the Uniform distribution: wouldn't the value in the y-axis be a value y, such that y approaches 0? Not y=1, because there would be an uncountably infinite values all with probability equal to 1? Or rather in your example y=10,000?
Idea: use a true random number generator to generate a seed for use with pseudorandom number generator. This will give an efficient and semi-random number generator. Of course it will repeat eventually but the period is undefined.
So why is it that the shuffle feature on apple music/ spotify is so bad? I have well over a thousand songs downloaded but will hear the same 10-20 songs played several times and never hear the majority of songs on my phone.
A few years ago apple had true randomness in their shuffle function but people complained that sometimes the same song being played twice(randomness can repeat itself, you can get to continuous 5s on a die and it's still random), so they removed the feature with who knows what algorithm.
Are there applications in which a pseudo random sequences are required that never repeat. One sequence that never repeats would be a Thue-Morse sequence, however it does not look very random. However one could use it as a seed to make it look "more random". Or are there better alternatives for this?
LegendLength It is also relatively simple to get an extremely long period by using two long sequences, whose lengths are relatively prime (share no common factor other then one). And then combine the two, for example by addition. The result should have a period equal to the product of the two periods of the original sequences.
No deterministic procedure which can be implemented in a physical system and has a finite size can give an infinite sequence that never goes into a loop, because there are only so many possible physical states for the implementation, by the bekenstein bound.
A counter example would be a Thue-Morse sequence. For example if you start of with some finite sequence X consisting out of numbers between 0 and 1 and not all equal to 0.5 (and maybe some other conditions), then you can recursively extend this sequence such that it is never repeating itself using X:=[X, 1-X]. However this sequence probably does not have very good properties regarding appearing random.
My point was in the "and has a finite size". Of course, if you have an unlimited amount of memory, then you can make a program that makes a sequence that never repeats, by doing something as simple as 01001000100001... etc. . But for any machine with a finite physical size, it has finitely many possibly physical states (because of the Bekenstein bound), and therefore must eventually repeat.
+drdca I was wondering what you exactly meant by that, because I am absolutely no expert, but I am rather certain that a simple number line will never repeat, and it can be sescribed with xn=xn-1 + 1. But I guess memory couldnt hold the numbers after they exceed its size.
The cycle repeats every time you get the same number? Wouldn't it make more sense to have the algorithm be based on the last several numbers instead of the last one? For example, in the linear congruential generator, the increment could be changed to the seed number we got on the previous turn, and the modulo could be the seed we got two turns ago. That leads to the problem of how to actually start the algorithm (How can you start something that relies on previous turns?) but at the very most, this just means we need multiple seeds, and the modulo, increment, etc. become their own seeds.
3:30 "Mersenne Twister" = "gold standard". It depends on what aspect you care about. Of the PRNGs in common use, MT generates the longest non-repeating stream of numbers, so it wins there. It's also reasonably easy to implement and good implementations are available. But it doesn't do well on some measures of statistical randomness.
Some links, if Kelsey wants to let them thru: Summary of major PRNGs properties: www.pcg-random.org/ A paper comparing the MT to other PRNGS: www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
PCGs (permuted congruential generators) are the current gold standard for statistically uniform, non cryptographic RNGs. The Mersenne Twister output has been shown to be statistically non uniform.
I think you'll find that a LFSR (linear feedback shift register) designed as primitive polynomial modulo 2, has a period of 2^n - 1 where n is the number of bits stored. I found an old paper which has the equation X(n)=X(n-6)+X(n-167) modulo 2 has a period of 2^167 - 1. One can use this for a larger integer, for example using 2^24 = 16777216 , X(n)=X(n-6)+X(n-167) modulo 16777216 (2^24 = 16777216 which is convenient for my purposes.) This gives a series of integers for which the least significant bit repeats every 2^167-1 numbers. Other bits repeat on at least the same period, or possibly they repeat on periods which are larger by a power of 2, (see Knuth) but I think that 2^167-1 is enough. For comparison, 2^167 is about the number of carbon atoms which would make a ball the size of Planet Earth. 2^98 is a lot smaller, but is about three quarters of the age of the universe, measured in picoseconds. This is still useful, as my program is not required to run for that long. I have implemented Knuth's suggestion of a buffer to shuffle the output, greatly increasing the period, by an unknown amount. In the program, the buffer (currently 150 items long) which holds the numbers to be shuffled, is called harlem. My program is therefore doing the Harlem shuffle. Do not confuse this with the Haarlem shuffle because Haarlem (double a) is in Amsterdam, while Harlem (single a) is in New York City.
I think I have a good random number generator. Approximate the Weierstrass function. Approximate derivative. Put the value of the derivative for input x in this: value-floor(value). And boom! You get your random numbers between
The devs responsible for INSIDE did a GDC talk about their graphics tech, and random numbers featured quite heavily in it. Though, unlike Minecraft, they weren't using them for content generation, but rather to make their visuals look nicer by dithering stuff to eliminate banding.
Could the Cumulative Distribution Function trick (mapping from uniform [0,1] to some other distribution) be expressed in matrix multiplication? Not sure what benefit that could have, but it seem potentially powerful.
But what if we want to create pseudorandom sequence that seem to contain all numbers - that is, any real number between for instance 0 and 1 can be produced? Wouldn't it be possible to acheive this by using a formula that typically produces transcendental numbers? It is true that only certain numbers will be contained, but we don't know which creating the impression that any number can accur. But... Functions that produce transcendental numbers can also contain rational numbers for certain input values. However, I wonder if it is possible to include irrational, non-transcendental numbers as well.
I needed to know about pseudorandom numbers for cryptography. Was pretty excited when this came up. I know we're not supposed to talk about how along with being smart the host is a total babe, so i won't.
It's going to be really awkward when Infinite Series, eventually ends.
John Hunter Good point, the series won’t last an infinite amount of time and they only have a finite amount of time they can actually film. My suggestion is handle the videos as a supertask with each video taking half the time to make and coming out twice as quickly as the last one. That way they could release an infinite series of videos using only a finite amount of material. :)
Good god. That is a brilliant idea to keep the show alive for infinite time. I love it.
Only problem is the host and the technical staff need to be able to handle it (if people were able to do it then humanity would reach a whole new level).
Sripad Kowshik Subramanyam Reminds me of the old joke about the chemist, the engineer and the mathematician who go vacationing in a cabin in the woods. One night the chemist wakes up and sees a fire on the stove. He quickly looks around, finds some inert powder in the cupboard and dumps it on the fire to put it out. The next night the engineer comes in and sees another fire on the stove (none of them are apparently great with kitchen safety). The engineer thinks for a bit about how much water he’ll need to dowse it, goes and grabs their water canteens and pours out just enough of them to douse the flame. The third night the mathematician comes in and sees yet another fire on the stove. He quickly grabs his notepad and starts vigorously writing down equations. A few minutes later he smiles, puts the pad down on the table and says “A solution exists, QED,” and goes back to bed. 😄
Doug Rosengard good one.
Who says their need to be infinitely many *distinct* episodes?
Let n be the number of the last episode. Then every episode e_k with k>n is defined to be equal to episode e_n. Voilà, infinite series. :^)
PBS explains these crazy topics with such precision and clarity, expecially infinite series. kudos for an exellent channel!
omg lmao this ego
r/iamverysmart
+
Also this thread made me giggle~
It is not that precise, it is stated in the video that radiation and things like that are random, while in reality they are not random, it is close to impossible to replicate and things like that, but it is not truly random. Maybe Veritasium or Vsauce had a video about true randomness where it is described a lot more precise. Even a service like random.org which collects electromagnetic background noise from antennas is not truly random, that noise has a source. I don't think true randomness exists, but we can get fairly close.
This right down my alley. Computer Science and Math. My goodness.
She sings her siren's song!
unfortunately this channel is gone :(
Kinda funny watching the video quality getting slaughtered at 2:21. Thanks to Tom Scott, I now know why!
Well spotted. I was concentrating on the audio not the video so I missed Dr Houston-Edwards face pixelating. Tom Scott: TH-cam's cool uncle.
Thanks for that reference. I was wondering what happened there.
add more confeity add more confeity !! lol
On a mobile screen at 1080p it's hardly noticeable. Never been this disappointed about a sharp picture.
Kailei R m.th-cam.com/video/r6Rp-uo6HmI/w-d-xo.html found it!
This is such a massively important topic. This issue alone has contributed to literally hundreds of thousands of dollars of my lifetime income. You've done a fantastic job of explaining a topic that, in interviews, I've found software engineers with over a decade of experience manage to get completely wrong.
What are you doing? :)
@@konstantin7596 implementing telecom encryption from spec, writing and verifying secure code through static analysis, reverse engineering, and automated testing, that sort of thing.
This was a great video, but i feel like the definition of randomness was a little vague. It would be great to see a video on Kolmogorov complexity to get a more in-depth insight on randomness. Im loving the computer science direction of this channel and i can't think of a better topic to cover!
I'm sure the definition of randomness was vague because the video focused chiefly on psuedorandomness. However, it's pretty difficult to define randomness.
When I took mathematical statistics for my BS in mathematics, we focused on randomness being the tendency of the image of a random variable to resemble the composition of its PDF/PMFs as the number of samples grows arbitrarily large.
For instance, the PMF of flipping a fair coin is Pr(X=x) = 1/2, x∈{Heads, Tails}, so if a flip of a fair coin truly is random, then flipping it an arbitrarily large number of times should give a 1/2 chance for each side.
However, if there were another process involved, such as having to choose one of four coins with replacement each flip, where one coin is fair, two gives give heads 75% of the time and the last gives tails 75% of the time, then if the process truly is random, the outcome should resemble the composition of those functions.
Additionally, as mentioned in the video, we should expect randomness to not exhibit any identifiable pattern. However, this isn't immediately disqualifying of something as being random. For instance, I could roll a d6 18 times and get 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6. This is extremely unlikely, but can happen under a truly random system. Ultimately, though, this pattern should not continue for arbitrarily large sequences.
Also, again mentioned in the video, an important aspect of randomness is irreproducibility. You should expect no two random processes to give the exact same output, though if you are extremely unlucky (or extremely lucky!) you might have to observe for a bit before the outputs diverge. In this last season of Doctor Who, there was an episode where people are living in a simulated reality, and they learn of this because any group of people calling out random numbers at the same time always calls out the same sequence of numbers because, as explained in the episode, computers can't generate truly random numbers (quantum computers should allow true random number generation, but that's beside the point).
Ultimately, though, randomness by its very nature is difficult to precisely define. It is easier to identify what *is not* random and trim it away, like an asymptotic game of mathematical jezzball.
John D. Cook wrote an interesting blog post on the topic: www.johndcook.com/blog/2012/04/19/random-is-as-random-does/
Why not define randomness in relation to an observer? If an observer can't predict the sequence, then the sequence is random for that observer. That definition does away with the whole problem.
The old "true randomness" requires a sequence to be unpredictable to all possible observers. That is problematic, as we don't know what observers there can be. If there is a god, he would be an observer?
Lars Pensjö This is very similar to Kolmogorov Complexity. A series would be considered random if the shortest program that could generate the series is the length of the series plus a constant
Interesting, I will look it up!
I just put the numbers 0 - 9999 into a spreadsheet and ran the Middle Square Algorithm on them. A few curiosities arose, which signify reasons it's Bad News for purpose....
1) There are 20 ways to produce a 0000 value. As 0000 has period 1, there are multiple ways to end up in this sinkhole.
2) Nearly 39% of the seed numbers can NEVER be produced this way.
3) A further 35% of sees numbers can only be produced by one other four-digit value
4) The number 5625 can be generated twelve ways. 2500 can be generated eleven ways (including itself). You might expect a number or two out of 10,000 seeds to be very popular, but knowing what they are means they're very predictable.
In reality, you're not producing random numbers [0,9999] : you're producing numbers [0,6109] with a ton of spaces and biases scattered within....!
that's why a good pseudorandom number generator should be used and not a bad one
MS is an old algorithm, not the best one. But in April of 2017 people have implemented a Middle Square Weyl Sequence PRNG. It is a modified version of MS and instead of [0;9999] produces [0;2^32-1] possible values. It fixes alot of problems of MS, and passes every statistical test. Just take a modulo of the returned value (for example mod 16384), and check the distribution. It should be uniformal.
Note: `s` is the seed. To initialise `s` take a random even number and add 0xb5ad4eceda1ce2a9 to it.
en.wikipedia.org/wiki/Middle-square_method#Middle_Square_Weyl_Sequence_PRNG
Knuth (volume 2 of The Art of Computer Programming) has lots of analysis and practical algorithms for pseudo-random numbers. Simple recipe: pseudo-random numbers (one of his algorithms) followed by another neat procedure of Knuth's which is shuffling the numbers in an output buffer.
Another book, "Numerical Recipes", refers to this. Numerical Recipes has references to Knuth. You can order the Knuth book and Numerical Recipes at any good bookshop. Beware: these are weighty books with a heavy price tag. Also look up "primitive polynomial modulo 2" which gives you a sequence which only repeats after a looooooooooong time. It's fairly easy to find tables of these, i.e. someone has calculated some of these "primitive polynomials modulo 2". (Knuth describes these.) Pick one which has a long repeat period, and the result is a trivially-simple recipe to make a stream of bits which repeats after an amazingly long time, i.e. longer than the age of the universe. Using this as the basis of a random-number generator gives a very fast and simple algorithm.
Look at tests of random number sequences: if you think you have a random number generator, there are ways of testing it, so hook up your RNG (Random Number Generator) to one of these tests to see how it behaves. The web has lots of information on this. Wikipedia, for example, has descriptions of ways of testing random numbers. So do other mathematics-related web sites. The tests are generally easy to perform.
I've also experimented with prime numbers. Find a sequence which can be quite simple, based on addition modulo the prime number, and (importantly) repeats with a period of your favorite prime number. Have several of these in parallel, each based on a different prime number, and the period of the resulting generator will be something like the product of all of the prime numbers. If you have 6 prime numbers which are of size about 1,000,000 then the composite behaviour will repeat with a period of about 1,000,000^6.
AFIK - The best random number generators are based on cryptology functions. Or, one could just as easily say that cryptology methods are based on random number generators, since the whole point of cryptology is to take a message and create a patternless sequence of numbers.
This video barely scratched the surface of random number generators. I asked a predoctoral math teacher if she had considered random number research for her doctoral thesis. Her reply was that she should have. There was a lot of research opportunities available. And that was maybe 20 years ago, so more research must still be available.
Random-number-generating algorithms are so interesting.
Inverse transform sampling is great in theory; in fact, when I needed to generate numbers from a distribution a few years back, it was my first instinct despite not knowing what to call it at the time.
Turns out, though, that - well, I'll let Wikipedia tell you: "For a continuous distribution, however, we need to integrate the probability density function (PDF) of the distribution, which is impossible to do analytically for most distributions (including the normal distribution). As a result, this method may be computationally inefficient for many distributions and other methods are preferred."
And that's how I discovered the Box--Muller Transform. Marvelous bit of work that actually will give you a normal distribution.
Ooh! That drifting numbers background really did a number on the video quality.
No pun intended.
Tom Scott did a video on the topic called "Why Snow and Confetti Ruin TH-cam Video Quality" (at least I think that was the title) which gives a basic explanation of the phenomenon if you're interested.
65 days quarentined. frist weed i get, i came to watch your videos. Amazing. I understand the Maths, but not why I'm doing this to myself. Congratulations on the video.
Knuth in his book pointed out that a randomly generated random number generator does not necessarily generate good random numbers. He discusses an algorithm he designed using things like a human's height and other imponderables. He wrote the code for it and set it to work. Though it had a space of 32 bits (if I remember correctly), if cycled with a period of 12.
One thing I'd add to this (very good) video is that uniform random numbers, besides having a constant probability density, have to be also *independent*. So every number has to be equally likely regardless what preceded it. Congruential generators might have a hard time achieving this since they essentially loop over the domain defined by M - and it's of course heavily dependent on the chosen A and C. Selecting primes for these parameters is usually a good start...
It's true that a pseudo random generator must eventually repeat. However, it's not true that it must happen as soon as it hits the same output again.
SRGs can have hidden state. Stuff inside the black box that isn't part of the output. That way they may effectively loop through all possible outputs not in just one way but, in fact, potentially in all possible orders. Similarly you can build them such that they occasionally spit out the same value twice in a row without falling into a loop where they spit out ONLY that one value.
They have to repeat only once their entire state (hidden state plus output) is hit again. And that could take a LOT longer than hitting every possible output once.
adding irrational number (or in actual computer case, very very accurate decimal one) to the seed on every step will cause the cycle be so long the existence of humanity will come to end faster.
Reaaaally depends on the rest of your setup. But yes, irrational numbers are a nice source of entropy.
You're right, but that's just deferring the problem - if you had N non-hidden states and H hidden ones, then your period is going to be (at best) N*H, so you're essentially back to square one.
I don't really see a problem here...
I just pointed out that a PRNG can through the same outputs a *lot* of times before starting to repeat.
Of course if you want to go through all possible sequences you'll need to have H*N >= N! or, if you want to allow for arbitrary duplicates, it ought to be H*N >= N^N. That's quite a tall ask, usually. (that's just numerically. You'll also want to satisfy some properties to actually generate the desired sequences)
But why stop there? What if, not only you want to run through all permutations, but you want to permute the order you run through the permutations?
The numbers obviously become insanely huge long before we even get to that point. Too large to contain on a computer. (By N=59, N! exceeds the estimated number of atoms in the observable universe, N^N clears that by 48)
Hidden states or not once your back to the same "exact" state your started with you are bound to repeat
Finally a complete explanation as to why pseudo random exists :D
Persi Diaconis does an excellent lecture series on what it means to be random.
Her videos are always so well made
Fun side note, in the 1960s and 1970s IBM had a random number generator call “RANDU”. Donald Knuth, the author of the seminal book “ The Art of Computer Programing”, call it “Truly Horrible”. Once the flaw came out, it called into question a large number publish papers that used this function for simulations.
Interesting, thanks!
" in the 1960s and 1970s IBM had a random number generator call “RANDU”. "
Yes, I think IBM's reply to a query about that was "We guarantee that each number individually is random, but we cannot guarantee that more than one of them is random."
I love Infinite Series but I gotta say, the Comp-Sci related videos are above and beyond spectacular
Complete and to the point! Great video.
Another nice thing about picking 2^32 as your m is that 32-bit computers would do it automatically. That's just how many bits they have, so any bits after that would just get lopped off. No additional computation required.
Mersenne Twister isn't a linear congruential generator. It's a linear feedback shift register.
For the normal distribution, one normally does not use the inverse distribution function, because that's not expressible in closed form. Instead, one generates two normal variates at once, because the distribution function of the radius (in polar coordinates) of a 2D normal distribution is in closed form. There are at least two ways of doing this.
Pierre Abbat, it actually is essentially an lcg, but has a tremendous amount of state.
Couldn't agree more, but morons might say No, it’s based on a shift register, not an LCG.
1. The state of a PRNG can be larger than the last bits of randomness it generated.
2. Cryptographically secure pseudo-random numbers cannot be distinguished from truly random numbers with limited resources, so unless your program is galactical size it is guaranteed you won't notice a difference. CSPRNG are typically significantly slower than PRNG in general.
3. The period of the most used Mersenne Twister is much larger than 2^32.
The Mersenne Twister is really generating 19937 bit numbers. The code only gives you 32 bits at a time, giving the appearance that the numbers are repeating within a cycle but that isn't the real size of the output. If you consider the actual output value, then the period is exactly 2^19937 - 1 which is what she meant.
If you consider all the inputs to the generator, then there can be no hidden state. If there was state that wasn't dependent on the input, then you wouldn't have a PRNG, since it could produce different outputs for the same input. With these technical considerations, what she said is correct, you can't cycle longer that 2^outputbits. It is just a bit more nuanced.
The speed thing rather depends on your implementation constraints. For example a CSPRNG based on a block cipher in CTR mode can be implemented in a parallel form that can be extended as far as is required to get the speed that is required. For many non cryptographic RNGs, like for example XORSHIFT or PCGs, this is not the case. The CSPRNG in most modern desktop and server CPUs is designed to exploit this parallelism. The worlds fastest production RNG is a CSPRNG that is frequently reseeded (0.5 to 1 millions times a second). I noticed that the video states that the Mersenne Twister is the gold standard, which is laughably false. Also the stated procedure for random fractions doesn't yield a uniform distribution when tried with floating point arithmetic. Especially if you do the multiply before the divide pushing the first term into the lowest resolution end of the floating point representation. It's easy enough to make uniform floats, but the method in the video is simply wrong.
Good job! You explained the idea clearly and precisely. One thing I am still wondering is why the inverse distribution of uniformly sampled cumulative probability densities of a normal distribution becomes a normal distribution again. You have given us a very good example using the heights of US women in the video. I think I will do some more research to find a mathematical proof to convince myself.
this is the best explanation I have ever seen for random number algorithms
You should've talked about Linear Feedback Shift Registers... And output bias/properties. But this is still a great video.
Ah, Linear Feedback Shift Registers! The Playstation 2 had them on the VPU1 (sort of a vector shader before there were GPUs) and I naively used them to create x,y,z coordinates for snow and rain sprites. It looked fine as long as just a few dozen were generated, but as more were added a pattern would show; all points confined to a few slanted columns. Caused a lot of head scratching; ended up using LFSR for x, a Linear Congruential Generators for y and for z something like z' = frac( z + GoldenRatio). Thought it was a hardware issue but found out later it was a problem inherent to LFSR.
I wrote a random number program in an old HP 41CX calculator. It was simple. Extract the 1/10th of a sec digit, set it next to the previous extraction in the alpha register, and when you have the number of digits wanted, execute AMUN and presto, a real random number appears in the X register. Requires a, or several, random execution or presses of the key assigned to extract the digit from the clock.
Someone should recommend this video to the guys who 'programmed' the randomizer for my car music player
I think its important to point out that the internal state of a PRNG is not required to be the same size as the output value. In any "good" implementation your period will be much larger then the resulting set. IE using a 64bit (or larger) internal state and returning a 32bit value. It is also important to note that many PRNGs apply functions to the output bits in such a way to protect that internal state from leaking out, such as a hash.
X_n+1 = (X_n * a + c) % 2^64
return hash(X_n) & (2^32 - 1)
First time i've seen a video this interesting that I couln't focus on the content because the speaker was too beautiful.
This video's topic was _so random!_
I think it’s diabolical that this is the _only_ video I found that _actually gives a valid equation._ Like, I’m looking up random number generator, why aren’t you giving me one?
As a computer scientist this is unbelievably important.
I'm showing this to all my coworkers. Really good way to explain how things work behind the scenes for all those different distributions in various random modules/libraries
In the case of the linear-congruential generator, you could increment the value of c after every pass, so with the right values of m, a, and c, you could have a period of m^2 instead of m.
but there can only be m states so the period cannot be greater than m
Though storage was briefly alluded to, the statement that using a “natural” sequence (e.g. via a Geiger counter) isn’t repeatable, isn’t strictly correct, e.g. if one stores the sequence thus generated. While it’s obviously more efficient to use a pseudo-random generator, storing and retrieving a sequence that’s many times the period of a typical pseudo-random generator (e.g. 2^32) isn’t all that impractical in this age of relatively fast storage. And some simulations do require much longer sequences than the periods of typical pseudo-random generators.
Ok so this might also be nitpicky but a parabola may follow a quite a bit more complex parametrization than that.
For instance:
a / b² x² - sin(2α) (x-x0) + (1 - cos(2α)) (y-y0) = 0
This is the parabola you get if you have a constant gravitational field pointing down with strenght "a" (if a is negative it points up instead), and you throw a ball with starting velocity "b" in a direction dictated by "α" when you at first stand on "(x0, y0)".
It includes all 2D parabolas that are aligned with the x and y axis. (In fact it has more parameters than necessary. You could do the same with y = a x² + b x + c) But of course you could also want freely rotated parabolas (which would involve an extra parameter giving that angle) or you could look parabolas in higher dimensional space...
LegendLength - maybe nit picky but try to estimate e.g. the likelihood of generating a Higgs at the LHC via the standard model using, e.g. the Merssene twister - only pointing out that when a sequence longer than the period of the standard pseudo-random generators is required one can in fact generate it and also have repeatability via storage and that can be done feasibly.
Afaik, since prng needs a seed seuence to extract entropy from, you must have a cache of real random inputs to run one. Windows supposedly does this by logging assorteed junk data like time keystrokes mous pointer position and various network info at predetermined times into an ever expanding cache of just random strings.
In the case of banking systems for example with tokens, the seed is the current time since we assume that the laws of physics at the surface of the Earth remain constant such that if your phone clock and the bank systems clocks are synchronized you both get the same generated number through the implemented algorithm. If however one would go a bit higher, let's say low Earth orbit, then the time will differ due to general relativity. You will be unable to login to your bank account from space if you don't correct for the time difference due to earth gravity.
I actually came up with a random algorithm called XSR for XOR with Shifting Right. It passes many random tests, and is faster and even better than the Mersenne Twister when stacked up.
One problem alluded to, but not mentioned explicitly with pseudorandom vs random numbers, is that truly random integer sequences could have exactly two (or "n") identical numbers in a row (for example with p=1/1e6 for rolling a thousand-sided die twice) , whereas for pseudorandom sequences, if there are two identical numbers in a row, there must be ONLY that number forever after. Therefore using pseudorandoms pairwise (over the entire range of possible numbers) would never give you the same distribution you would see in actual random sequence.
Only if the the state size = the output size. This is not true of sensible PRNGs.
I love the show! Keep it up guys and galls!
Although the reasoning for obtaining a normal RV from a uniform RV follows from the inverse transform method (as you've illustrated), I'm a bit scared that this might be advocating its use for this case rather than the Box-Muller transform in order to obtain normal variates, which is much easier (and safer) to implement on a range of platforms and in fact much more elegant! (Save for the fact that you might be throwing an unneeded normal RV away or donating it to charity, but who in this simulation driven world only requires a single normal RV - am I right?)
For the Inverse Transform demonstration I would've used a Pareto / exponential distribution (granted, it would not produce nice S curved graphs as the normal CDF does, but it does give the opportunity of quickly doing an on-screen algebraic manipulation to arrive at the desired RV, which always makes my heart sing :-) )
This video really clarified computer "randomness" for me. I always wondered why they didn't use a hardware solution or query the last few digits on the second on an atomic clock. It makes a lot of sense that for the purposes of debugging this would be bad. Thanks!
I really want to watch these videos, but I'm waiting for the series to finish so I can binge watch the entire series.
Thank god for this video... Teaching me this subject way better than my college professor!
There were a lot of issues regarding pseudo random generators (Java 2013, Sony 2010, OpenSSL 2008), but that doesn't mean hardware generators are better and humans definitely aren't. Hardware generator even those which uses radiation reader could be "hacked" by putting another device near it (ofc it requires physical access to that machine but that's always the case). Numbers/phrases generated by humans are even less random that simple PRNG. It could be determine base on that person knowledge, habits, friends how probabilistic is that he will chose exact number/character in sequence.
Was it just a coincidence that the probability density function looked like the derivative of that cumulative distribution of heights? It appeared to be exactly that and I think that makes sense but I've not seen such an elegant link between statistics and calculus before that.
PDF is always the derivative of the cumulative function. The exact opposite of a coincidence!
What is "truly" random in every day life is more of a philosophical question than a mathematical one. If a poker website has a RNG that combines seed from micro temperature fluctuations, internet traffic, number of players on website and other variables, I'm going to call it random for the purpose of me trusting the website to deal me cards "randomly".
Awesome video🔥
Love your videos!🤗
Nice DIN font choice, fits in nicely.
Thank you very much for this video! It was very clear and informative for me :)
I hope there's a follow up episode on some of the tests used to gauge a PRNG's statistical randomness. Looking at the 3-dimensional planes generated by LCGs is a pretty direct way to see how bad they are (in that respect).
And then a follow up on how awful the tests are.
This channel is perfect.
I wish I paid attention in maths.
at 8:20 you say that the distributions of the random number generators is uniform. But isn't this only the case when the period of the sequence is equal to the size of the interval? If so then the Middle-Square Algorithm will never have a uniform distribution (the maximum period was less than the interval), and the Linear Congruential Generator will only have one when "good" values are chosen (such that the period=m). I would be interested to see another episode going into more detail about how these "good" values are found, and about the actual distribution of the Middle-Square Algorithm (as it is not uniform).
That was a great video!
(Weird comment from game programmer on getting away with sampling a PRNG with a small period. Ignore as needed :P)
Interesting thing WRT period for procedurally generated content (eg game levels) is it doesn't necessarily have to be particularly large. You are advancing the PRNG through it's sequence every time it is sampled, but you can sample it in such a way that the repetition is not apparent to the player.
For example, if we have a small period PRNG determining the heights of tiles in a level, it will become apparent if the period is significantly less than the number of tiles generated. But if we generate a tile's height and then before we sample for the next tile we sample the PRNG a second time or more ("how many blades of grass are on this tile?" or "Shall we place a monster here?" - "Which direction is the monster facing?") by the time we get to calculating the next tile's hight, the PRNG could be at a (psuedo) random point in it's sequence. The sequence repeats but less noticeably for something the playing will recognise (tile heights) unless the player can view a lot more of the generated level.
This can work against us too though; a program sampling a PRNG can request random numbers in step with it's period, so every tile would have the same height, and the same number of blades of grass, the same monster spawned. Or if the program made periodLength/2 samples for a tile, every ~other~ tile will be the same.
This is largely irrelevant these days since most computers can comfortably generate very long pseudorandom sequences, and do it very quickly. But it is a trick that can be used if careful and when computation power is extremely limited :)
That's weird, I was just thinking about this this morning. Perfect!
And I was watching a video from GDC of some game devs talking about procedural content, which usually makes use of pseudorandom numbers just this afternoon.
No reference to why it is called Mersenne Twister? 2^19937-1
Good point. And just to unpack your comment a bit for other people: The period of the common Mersenne Twister generator is 2^19937-1, which is called a Mersenne Prime.
Inverse Transform Sampling should also generate pseudo normal distribution because probability at each point is different but in this case, it will be constant for given ranges however short we go.
Well, I was planning on doing Perlin Noise today anyway. I guess I'll write my own PRNG too.
great! worth a second watch to really understand pseudo RNG for newbies like myself
This demonstrates the difference between a mathematician and an engineer. The problem was defined with 2 significant digits. The answer can only possibly contain 2 significant digits. You don't pick up more. So, the baseball rulebook is correct. The correct answer to this problem is "12". The trailing ".019" is meaningless.
Great videos, sir. Keep them coming!
how do computers pick the a, m, and c for the linear congruential generator? do companies all use the same one? do they use a different pseudorandom number generator to pick them?
WIkipedia has a thorough page on Linear Congruential Generator
First of all - Thanks for making such great videos for free. I have a question - How can we generate non-uniform distribution between [0,1]?
Roll20 uses the true random hardware source to periodically re-seed its pseudorandom number generator (probably every few minutes for each user session).
Thank you so much
Custom hardware for randomness is less and less of a problem, now that basically every consumer computer (including phones) comes with a camera in it. Random movement of electrons in the CCD sensor produces thermal noise that you can use. Note that this does not depend on actual light entering the camera.
Hi Nathan,
you are right, a web cam can be used. I made a web base tool some years ago that works inside the browser an captures the web cam
to generate random numbers.
You can put a sticker on the cam and the sensor still it generates pixel noise.
For poeple interested in it:
retura.de/camrng/camrng.html
Its in german...klick on "web cam aktivieren" to start the capturing and then on START.
The graph then shows the quality or "randomness" of the data, by calculating PI with a monte-carlo simulation and the rate between ones and zeros.
Greetings David
oh I forgot I made an english version too:
retura.de/camrng/camrng_en.html
How would you go about proving that a given SRNG is uniformly distributed? how does the Mersenne twister improve upon a linear congruential generator? What are some common randomness tests? I feel like there's a lot this video just glossed over; some further reading would be appreciated.
OK, this is kind of a nit, but a bit after 10½ min, the CDF that's plotted doesn't appear to correspond to the stated µ and σ values of 162 and 5.
For other readers ('cause I know you know this), in a normal distribution, about 68% of data fall between µ±1σ; about 95% fall between µ±2σ.
So while the mean on the plot (µ=162) is fine, at µ-1σ = 157, it should be 0.16; it looks more like half that. And at µ-2σ = 152, it should be 0.025; it looks more like 0.01 or less.
I bother to point this out because I really admire what you've done here in presenting a subject that can be very perplexing even to some pretty smart people.
I find your explanations just right on the simplicity/complexity scale, and your illustrations with numerical examples seal the deal.
And what I point out above, doesn't detract from the overall high quality of this; I just think it might catch one or two other viewers' eyes.
Rolling back to ≈9½ min, it looks as though the PDF is plotted correctly, but that the highlighted central region as shown, is µ±½σ, which has *width* = σ, when what should have been plotted was µ±1σ which has *radius* = σ. This may have led to the incorrect CDF plot, if σ=2.5 got used to make that plot.
E.g., in the table at 11:24, CDF(154.5, 168.4) are shown as occurring at (0.0671, 0.9), which seems good, considering that CDF(157, 167) = (0.16, 0.84); while those values on the CDF plot don't seem to fall at the right heights.
Also, I found it odd that you never mentioned one of the most common ways to generate a "random" seed - the least significant several bits or digits of the computer's internal clock.
Very cool, I had never heard of inverse transform sampling before. I can think of a few programming applications where it would have been useful. Thanks!
You had a video about normal numbers half a year ago. These are exactly the numbers x in [0,1] such that the sequence x_{n+1}=10 x_n mod 1 equidistribute in [0,1]. I'm not sure how close is the connection to pseudo random numbers, but it is true that almost every number in [0,1] is normal (so it is a "good seed").
So when I use R or Stata to simulate a normally distributed set of numbers, even if I simulate a large number it often deviates from what a standard normal distribution is supposed to look like--sometimes by pretty noticeable amounts. Why is that so if the program is just basing its values off of the equation for the CDF?
Two possible reasons. (1) It takes a lot of deviates for the curve to start looking nice, like a few million. (2) Not all algorithms are perfect.I use Zignor. I don't know what R uses.
Hey!! I think there's a way to generate random numbers from a deterministic process. We can take the square root of 2 or 3 or any such imperfect squares. We get a sequence of truly random numbers. We can then tell the computer to select four numbers sequentially and thus we create a series of random numbers from a deterministic process. Would be glad if you could answer it. 😄😄
Learning Tutorials The digits in sqrt(n) aren't random, because you can algorithmically generate the next number. If there's an algorithm to generate the next number in the sequence, then it's by definition not random.
Benjamin Przybocki Then none of the pseudo random numbers are random according to you??
pseudo-something means not-quite-something, Benjamin is correct.
UncommonReality Thank You for your reply and time...😄😄
"a way to generate random numbers from a deterministic process" - what if that deterministic process takes more and more time and information, the farther you go in the sequence? Each digit takes more time to compute than the previous digit.
I believe I've heard that the digits of pi pass most statistical randomness tests. And they never repeat. But they are also not random.
The sequence is not even close to fully random and is easily distinguished from random.
+David Johnston Because its a single well known sequence right? But say someone went ahead and calculated a section of it that is as of yet unknown, and presented it on its own. Could that be considered a random string?
On that graph on the right at 10:20, the line from 0 to 1 is not parallel with the axis
Surely comparing the Linear Congruential Generator with the Middle Square Algorithm at 5:49, and asking which sequence looks the most random, is an unfair comparison?
They have different moduli- the MSA has mod 9999, but the LCG has mod 7829. Small sample nonwithstanding, the two sets provided are inherently different.
9:00 just to clarafy that it will never actually be 1. The way it's implemented on practice doesn't allow it, and if it would happend all sorts of os-crashing level of glitches would happend.
9:56 the Uniform distribution: wouldn't the value in the y-axis be a value y, such that y approaches 0?
Not y=1, because there would be an uncountably infinite values all with probability equal to 1?
Or rather in your example y=10,000?
Great video. I love when it gets more applied or computer-science-y 😊
Please do more applied stats videos like these. This was amazing!
Clear and precise explanations, thank you! Could you show me the literature used for this video or recommend some further literature?
4:57 Save the random numbers on disk, then on bugtesting, pipe them into the program.
Idea: use a true random number generator to generate a seed for use with pseudorandom number generator. This will give an efficient and semi-random number generator. Of course it will repeat eventually but the period is undefined.
So why is it that the shuffle feature on apple music/ spotify is so bad? I have well over a thousand songs downloaded but will hear the same 10-20 songs played several times and never hear the majority of songs on my phone.
A few years ago apple had true randomness in their shuffle function but people complained that sometimes the same song being played twice(randomness can repeat itself, you can get to continuous 5s on a die and it's still random), so they removed the feature with who knows what algorithm.
9:58 I have completed a probability course at university and only now I discover this?
Ambient piano pitch sound drives me crazy .
This was cool topic! Can you do more videos on random or maybe even series of videos about random in mathematics and physics ^^
That was awesome.... Thank you so much.
Are there applications in which a pseudo random sequences are required that never repeat. One sequence that never repeats would be a Thue-Morse sequence, however it does not look very random. However one could use it as a seed to make it look "more random". Or are there better alternatives for this?
LegendLength It is also relatively simple to get an extremely long period by using two long sequences, whose lengths are relatively prime (share no common factor other then one). And then combine the two, for example by addition. The result should have a period equal to the product of the two periods of the original sequences.
No deterministic procedure which can be implemented in a physical system and has a finite size can give an infinite sequence that never goes into a loop, because there are only so many possible physical states for the implementation, by the bekenstein bound.
A counter example would be a Thue-Morse sequence. For example if you start of with some finite sequence X consisting out of numbers between 0 and 1 and not all equal to 0.5 (and maybe some other conditions), then you can recursively extend this sequence such that it is never repeating itself using X:=[X, 1-X]. However this sequence probably does not have very good properties regarding appearing random.
My point was in the "and has a finite size". Of course, if you have an unlimited amount of memory, then you can make a program that makes a sequence that never repeats, by doing something as simple as 01001000100001... etc. . But for any machine with a finite physical size, it has finitely many possibly physical states (because of the Bekenstein bound), and therefore must eventually repeat.
+drdca I was wondering what you exactly meant by that, because I am absolutely no expert, but I am rather certain that a simple number line will never repeat, and it can be sescribed with xn=xn-1 + 1. But I guess memory couldnt hold the numbers after they exceed its size.
The cycle repeats every time you get the same number? Wouldn't it make more sense to have the algorithm be based on the last several numbers instead of the last one? For example, in the linear congruential generator, the increment could be changed to the seed number we got on the previous turn, and the modulo could be the seed we got two turns ago.
That leads to the problem of how to actually start the algorithm (How can you start something that relies on previous turns?) but at the very most, this just means we need multiple seeds, and the modulo, increment, etc. become their own seeds.
Can Inverse Transform Sampling be used to transform a different distribution into a uniform distribution?
3:30 "Mersenne Twister" = "gold standard". It depends on what aspect you care about. Of the PRNGs in common use, MT generates the longest non-repeating stream of numbers, so it wins there. It's also reasonably easy to implement and good implementations are available. But it doesn't do well on some measures of statistical randomness.
Tehom what measures does it do poorly at?
+Alexander F I had to look it up, but basically tests of linear complexity, such as a part of TestU01 called BigCrush.
Some links, if Kelsey wants to let them thru:
Summary of major PRNGs properties: www.pcg-random.org/
A paper comparing the MT to other PRNGS:
www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
PCGs (permuted congruential generators) are the current gold standard for statistically uniform, non cryptographic RNGs. The Mersenne Twister output has been shown to be statistically non uniform.
I think you'll find that a LFSR (linear feedback shift register) designed as primitive polynomial modulo 2, has a period of 2^n - 1 where n is the number of bits stored. I found an old paper which has the equation X(n)=X(n-6)+X(n-167) modulo 2 has a period of 2^167 - 1.
One can use this for a larger integer, for example using 2^24 = 16777216 , X(n)=X(n-6)+X(n-167) modulo 16777216
(2^24 = 16777216 which is convenient for my purposes.)
This gives a series of integers for which the least significant bit repeats every 2^167-1 numbers. Other bits repeat on at least the same period, or possibly they repeat on periods which are larger by a power of 2, (see Knuth) but I think that 2^167-1 is enough.
For comparison, 2^167 is about the number of carbon atoms which would make a ball the size of Planet Earth. 2^98 is a lot smaller, but is about three quarters of the age of the universe, measured in picoseconds. This is still useful, as my program is not required to run for that long.
I have implemented Knuth's suggestion of a buffer to shuffle the output, greatly increasing the period, by an unknown amount. In the program, the buffer (currently 150 items long) which holds the numbers to be shuffled, is called harlem. My program is therefore doing the Harlem shuffle.
Do not confuse this with the Haarlem shuffle because Haarlem (double a) is in Amsterdam, while Harlem (single a) is in New York City.
I think I have a good random number generator.
Approximate the Weierstrass function. Approximate derivative. Put the value of the derivative for input x in this: value-floor(value). And boom! You get your random numbers between
Pseudorandom numbers are very underrated. They are what make infinite yet reproducible Minecraft worlds possible!
The devs responsible for INSIDE did a GDC talk about their graphics tech, and random numbers featured quite heavily in it. Though, unlike Minecraft, they weren't using them for content generation, but rather to make their visuals look nicer by dithering stuff to eliminate banding.
Could the Cumulative Distribution Function trick (mapping from uniform [0,1] to some other distribution) be expressed in matrix multiplication? Not sure what benefit that could have, but it seem potentially powerful.
It depends on the curve. Some curves are not analytic and so need iterative numerical methods. So the process is quite inefficient.
i wish i learned about inverse transform sampling earlier
Thanks indeed,, could we have an episode on extractor functions? like how to simulate a fair dice using unfair one.
Ahmed Almutairi, oh, that's a great topic. Yes please!
But what if we want to create pseudorandom sequence that seem to contain all numbers - that is, any real number between for instance 0 and 1 can be produced? Wouldn't it be possible to acheive this by using a formula that typically produces transcendental numbers? It is true that only certain numbers will be contained, but we don't know which creating the impression that any number can accur. But... Functions that produce transcendental numbers can also contain rational numbers for certain input values. However, I wonder if it is possible to include irrational, non-transcendental numbers as well.
I needed to know about pseudorandom numbers for cryptography. Was pretty excited when this came up. I know we're not supposed to talk about how along with being smart the host is a total babe, so i won't.
You're head always moves like a typewriter... :D this distracts me so hard. Is it because of reading from a prompter?