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.
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.
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.
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)
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.
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.
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.
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...
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 RUclips Video Quality" (at least I think that was the title) which gives a basic explanation of the phenomenon if you're interested.
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 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)
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.
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.
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.
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.
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.
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.
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."
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 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.
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?
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.
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 :-) )
(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 :)
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.
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.
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
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.
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.
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!
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.
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).
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".
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
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").
Roll20 uses the true random hardware source to periodically re-seed its pseudorandom number generator (probably every few minutes for each user session).
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
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!
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.
+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?
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.
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!
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.
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?
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.
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.
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.
Lots of RNG engines for programs being activley interacted with (say, a game) use user input as part of the sequence. Is this still psudeorandom, or does the realtime user input make it totally random?
I'm security expert and saying that LCG is random number generator in slight even context of encryption is not good. You must not use such PRNG in crypto ever! Cryptography is hard and random generators used in cryptography must have certain properties. That must be stated clearly because a lot of people make mistakes of developing they own crypto which is always very bad idea.
What about AES-CTR? That is using the AES algorithm to produce a stream of random numbers that you XOR with the plain text. While in principle you are correct, she mentions in the video that true random number generators often can't produce enough entropy needed by modern systems. Web servers for example need a lot more entropy than can be provided by hardware RNGs. I would definitely agree with you about using a PRNG exclusively or for a significant period of time, allowing attackers to figure out the state of your PRNG and guess the next one. Wouldn't it be safe to use hardware (that you trust) to seed a PRNG? Essentially you are using all the truly random numbers your system can generate with a PRNG filling in gaps between them as needed.
The Intel DRNG uses the AES-CTR-DRBG algorithm. The state is the K and V (for vector). For each cycle of the algorithm, run AES-CTR with the Key=K and the counter start = V. Then it generates some numbers. The first AES output is the random number. The next two outputs of the CTR algorithm are xored into K and V so we have a new K & V so numbers can repeat as the expected rate for full entropy bits. CTR mode on its own never repeats a value until you wrap V around, whereas fully entropic data might. Hence the need to update K & V. To prevent the state being inferred over time, a 2.5GBPS entropy source is constantly feeding the entropy extractor which is constantly reseeding the DRBG at about 0.5 million times a second. There is also the NRBG output that feeds the RdSeed instruction that gets a full entropy extractor output mixed into every number, so it is ideal for seeding downstream PRNGs, hence the name RdSeed. That and a few other layers of attack prevention features is why it has remained secure for the past 7 years and there has been no sucessful attack against it.
How to know which to use? Simple; it depends on application: • non-cryptography (simulations, games etc) - use pseudo-random number generator like MT, xorshift or something else you fancy. • cryptography (key generation, nonce generation etc) - why are you implementing cryptographic primitives‽ Stop and use existing libraries.
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.
I have seen some pseudo random number generators that use a bell-curve distribution, given its mean and the standard deviation. However, I don't quite understand how they generate the numbers, because they seem to be unbounded, differently from the first two algorithms shown in this video.
Many modern computers have hardware RNGs built into the CPU. en.wikipedia.org/wiki/RdRand I have actually written a PRNG that uses cryptographic hashes. Basically just take an initial seed (/dev/random works great for that, actually a whole RNG infrastructure in itself), find the SHA256 of it, then use the last (for example) 16 bits of it as your random number. To get the next random number, take the previous hash and run it through SHA256 again. Since the application was for test software, if it's desired to rerun a test with the same initial conditions, it's as simple as giving the seed that was saved in the logs.
A few other methods... x(n+1)=x(n)*a_larger_prime_number/a_smaller_prime_number x(n+1)=sha2(x(n)) // or sha1, or md5 or... On the later one since they generate a larger number of bits than you require for most ranges, you can take a sequence of bits from them, generating the next number when you run out of bits of the previous pool. sha1/sha2 is a very good random number generation (passes diehard tests very well over any number of bits used en.wikipedia.org/wiki/Diehard_tests ) On my generator using sha2, when another pool of bits is required, I provide a callback method which can allow you to add entropy. This allows each call to add say the current clock tick to remove cycling. Even adding a simple incrementing number into the mix fixes cycling.
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.
I can understand why you'd want to shy away from any of the more technical details about PRNGs like whether you can infer their state or not and if you can, how much output it takes before you can infer their state. That said, I don't think anyone would consider Mersenne Twister to be the "gold standard". Of course it's much better than an LCG but it's inferior to many other PRNGs and even more so when you consider the size of it state compared to much better PRNGs with smaller state.
Nice, but a few nits to pick 1. The thermal noise from passing à current through a semiconductor junction is genuinely random in QM. Don't need a geiger counter, so the implication that significant external equipment is needed is not entirely fair. 2. If you want a sequence to be repeatable for testing, this does not mean that you need a pseudo random deterministic generator, you could just store the run from the geiger, for example, and replay it. 3. Please don't say that a computer has a limited number of decimal places. Any Turing complete computer can do long division by the same iterative method as a human with paper and pencil. The limit is set by storage (paper) and time. On a modern machine if you have one hundredth of a second you can calculate to thousands of decimal places. People can easily be confused about that if they don't have the foundations, thinking it may be to do with hardware support for floating point, or that you would be bound to use floating point data types. Not so. I'm a bit distressed about this because it seems to be quite common on scientific channels, you actually want to challenge Turing?
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.
The Middle Square Algorithm can't possibly generate all numbers between 0 and 9999. If it generated a single-digit number, the next number in the sequence would be 0000, which would square to 0000 and it would get stuck there forever.
I have to take issue with asking the audience which of two sequences appear more random. Humans are demonstrably incapable of discerning truly random sequences. Moreover the majority will claim that a truly random bit stream is not random, while a pseudorandom (especially with a low exponent such as 2^7-1) bit stream is truly random. It’s in human nature to do pattern finding, which brings an insurmountable bias to the table.
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. :^)
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: RUclips'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.ruclips.net/video/r6Rp-uo6HmI/видео.html found it!
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 :(
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.
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.
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
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.
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.
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.
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...
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 RUclips Video Quality" (at least I think that was the title) which gives a basic explanation of the phenomenon if you're interested.
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 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)
Persi Diaconis does an excellent lecture series on what it means to be random.
Finally a complete explanation as to why pseudo random exists :D
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.
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.
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.
First time i've seen a video this interesting that I couln't focus on the content because the speaker was too beautiful.
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.
this is the best explanation I have ever seen for random number algorithms
I love Infinite Series but I gotta say, the Comp-Sci related videos are above and beyond spectacular
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.
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.
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."
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 really want to watch these videos, but I'm waiting for the series to finish so I can binge watch the entire series.
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.
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?
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
This video's topic was _so random!_
Her videos are always so well made
Someone should recommend this video to the guys who 'programmed' the randomizer for my car music player
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 :-) )
(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 :)
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.
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.
Complete and to the point! Great video.
Clear and precise explanations, thank you! Could you show me the literature used for this video or recommend some further literature?
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
Well, I was planning on doing Perlin Noise today anyway. I guess I'll write my own PRNG too.
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!
Thank god for this video... Teaching me this subject way better than my college professor!
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.
Nice DIN font choice, fits in nicely.
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!
great! worth a second watch to really understand pseudo RNG for newbies like myself
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.
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.
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".
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
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").
Roll20 uses the true random hardware source to periodically re-seed its pseudorandom number generator (probably every few minutes for each user session).
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
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]?
This channel is perfect.
Thank you so much
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!
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.
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?
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.
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 wish I paid attention in maths.
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.
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
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.
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.
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.
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!
Thank you very much for this video! It was very clear and informative for me :)
You're head always moves like a typewriter... :D this distracts me so hard. Is it because of reading from a prompter?
Lots of RNG engines for programs being activley interacted with (say, a game) use user input as part of the sequence. Is this still psudeorandom, or does the realtime user input make it totally random?
Ambient piano pitch sound drives me crazy .
I'm security expert and saying that LCG is random number generator in slight even context of encryption is not good. You must not use such PRNG in crypto ever! Cryptography is hard and random generators used in cryptography must have certain properties. That must be stated clearly because a lot of people make mistakes of developing they own crypto which is always very bad idea.
I'm a full time RNG designer and I approve this message.
What about AES-CTR? That is using the AES algorithm to produce a stream of random numbers that you XOR with the plain text. While in principle you are correct, she mentions in the video that true random number generators often can't produce enough entropy needed by modern systems. Web servers for example need a lot more entropy than can be provided by hardware RNGs.
I would definitely agree with you about using a PRNG exclusively or for a significant period of time, allowing attackers to figure out the state of your PRNG and guess the next one. Wouldn't it be safe to use hardware (that you trust) to seed a PRNG? Essentially you are using all the truly random numbers your system can generate with a PRNG filling in gaps between them as needed.
The Intel DRNG uses the AES-CTR-DRBG algorithm. The state is the K and V (for vector). For each cycle of the algorithm, run AES-CTR with the Key=K and the counter start = V. Then it generates some numbers. The first AES output is the random number. The next two outputs of the CTR algorithm are xored into K and V so we have a new K & V so numbers can repeat as the expected rate for full entropy bits. CTR mode on its own never repeats a value until you wrap V around, whereas fully entropic data might. Hence the need to update K & V. To prevent the state being inferred over time, a 2.5GBPS entropy source is constantly feeding the entropy extractor which is constantly reseeding the DRBG at about 0.5 million times a second. There is also the NRBG output that feeds the RdSeed instruction that gets a full entropy extractor output mixed into every number, so it is ideal for seeding downstream PRNGs, hence the name RdSeed. That and a few other layers of attack prevention features is why it has remained secure for the past 7 years and there has been no sucessful attack against it.
David Johnston wow, thanks for those details!
Jonathan Nelson hey I was reffering that PRNG She mentioned is not cryptographycally safe and cannot be used in such context
This was cool topic! Can you do more videos on random or maybe even series of videos about random in mathematics and physics ^^
How to know which to use? Simple; it depends on application:
• non-cryptography (simulations, games etc) - use pseudo-random number generator like MT, xorshift or something else you fancy.
• cryptography (key generation, nonce generation etc) - why are you implementing cryptographic primitives‽ Stop and use existing libraries.
I've got a lot of Kahn academy to complete before I can begin to understand ANYTHING you EVER say. I'm 25 and I'm dumber than a 6th grader
hope in these 3 years you were able to complete some of those.
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.
I have seen some pseudo random number generators that use a bell-curve distribution, given its mean and the standard deviation. However, I don't quite understand how they generate the numbers, because they seem to be unbounded, differently from the first two algorithms shown in this video.
Many modern computers have hardware RNGs built into the CPU.
en.wikipedia.org/wiki/RdRand
I have actually written a PRNG that uses cryptographic hashes. Basically just take an initial seed (/dev/random works great for that, actually a whole RNG infrastructure in itself), find the SHA256 of it, then use the last (for example) 16 bits of it as your random number. To get the next random number, take the previous hash and run it through SHA256 again. Since the application was for test software, if it's desired to rerun a test with the same initial conditions, it's as simple as giving the seed that was saved in the logs.
Unfortunately, TLA agencies get chip makers to put in back-doors, so if you want to be safe, you should get some other sources of randomness as well.
That was a great video!
A few other methods...
x(n+1)=x(n)*a_larger_prime_number/a_smaller_prime_number
x(n+1)=sha2(x(n)) // or sha1, or md5 or...
On the later one since they generate a larger number of bits than you require for most ranges, you can take a sequence of bits from them, generating the next number when you run out of bits of the previous pool.
sha1/sha2 is a very good random number generation (passes diehard tests very well over any number of bits used en.wikipedia.org/wiki/Diehard_tests )
On my generator using sha2, when another pool of bits is required, I provide a callback method which can allow you to add entropy. This allows each call to add say the current clock tick to remove cycling. Even adding a simple incrementing number into the mix fixes cycling.
This was a very good video.
11:40 gaahh thats so obvious in hindsight. thanks.
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.
I can understand why you'd want to shy away from any of the more technical details about PRNGs like whether you can infer their state or not and if you can, how much output it takes before you can infer their state. That said, I don't think anyone would consider Mersenne Twister to be the "gold standard". Of course it's much better than an LCG but it's inferior to many other PRNGs and even more so when you consider the size of it state compared to much better PRNGs with smaller state.
Can Inverse Transform Sampling be used to transform a different distribution into a uniform distribution?
That was awesome.... Thank you so much.
4:57 Save the random numbers on disk, then on bugtesting, pipe them into the program.
Nice, but a few nits to pick
1. The thermal noise from passing à current through a semiconductor junction is genuinely random in QM. Don't need a geiger counter, so the implication that significant external equipment is needed is not entirely fair.
2. If you want a sequence to be repeatable for testing, this does not mean that you need a pseudo random deterministic generator, you could just store the run from the geiger, for example, and replay it.
3. Please don't say that a computer has a limited number of decimal places. Any Turing complete computer can do long division by the same iterative method as a human with paper and pencil. The limit is set by storage (paper) and time. On a modern machine if you have one hundredth of a second you can calculate to thousands of decimal places. People can easily be confused about that if they don't have the foundations, thinking it may be to do with hardware support for floating point, or that you would be bound to use floating point data types. Not so. I'm a bit distressed about this because it seems to be quite common on scientific channels, you actually want to challenge Turing?
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.
OK you just made me want to give up even thinking about math
The Middle Square Algorithm can't possibly generate all numbers between 0 and 9999. If it generated a single-digit number, the next number in the sequence would be 0000, which would square to 0000 and it would get stuck there forever.
I have to take issue with asking the audience which of two sequences appear more random. Humans are demonstrably incapable of discerning truly random sequences. Moreover the majority will claim that a truly random bit stream is not random, while a pseudorandom (especially with a low exponent such as 2^7-1) bit stream is truly random. It’s in human nature to do pattern finding, which brings an insurmountable bias to the table.
Please do more applied stats videos like these. This was amazing!
13:40 + Bad girl, don't steal our physics equations as background! They are fancy and they are ours....
Maths is the language of physics. Are you also going to tell language teachers they can't use literature?