Video 8-3: Pseudorandom generators

0:03 For the rest of this unit, uh I I want to take you on a slightly longer detour through some slightly more recent but also slightly more involved topics. Uh but I think the uh the main message behind them is so powerful that it's it's just interesting to look into them even if at some points we'll not dig through all the technical details. That's the idea of uh pseudo random generators. I guess the term will be familiar to programmers. Usually uh different people mean different things by calling them calling something a pseudo rand a pseudo random generator. Uh programmers would understand pseudo random number generators as meaning some relatively simple function that you give a seed and then uh And certainly this is um the term is inspired by this use but we'll see that there's some some important differences in the details. So you put some random seed in and you suppose that this is chosen somehow with real randomness. In reality it's often just the number of seconds since midnight. So it's it's not actually random by any uh definition of randomness but it is different or different runs of the uh program and so it could be good enough. Um and then it generates many more numbers Uh and one thing that these pseudo random generators um have is that they're actually a deterministic function of the seed. If you keep the seed, if you put the same seed in tomorrow again, you'll get the same uh pseudo random numbers.

2:35 And I think this is where the pseudo comes from. They're not actually random. At least if uh if the seed wasn't really random, then the numbers certainly won't. Even if the seed is random, looking at a lot of those numbers will eventually reveal that it's it's not random because they're simply computed from the seed in some more or less sophisticated way to look random. So often these are some linear concurrential method at the very uh simplistic end and then mer twister is I guess somewhere in between but no longer state-of-the-art either. uh and you you just try to build functions that make numbers that look random according to statistical tests. So usually here we would say um a good pseudo random generator is output passes statistical tests for randomness.

3:48 And often these are relatively simple things. One simple statistic could be that the number of zeros and ones if these are binary numbers should be roughly the same. We don't expect it to be exactly the same. We expect it to be roughly a a binomial distribution maybe. And so it should roughly reflect that distribution. That's the kind of things where this is used. And that's often good enough for say uh numerical simulations.

4:15 Now here we'll uh we'll look at this from a different perspective and start us off let's let's do the intuitive version first. Suppose we have an algorithm from this BPP class which is a two-sided error Monte Carlo algorithm with bounded error. Um we uh also uh and because it's BPP we assume the running time is is polomial that also means the number of random bits are bounded because we can only use one random bit in each time step. So there the number of of different random bits that we can give the algorithm is also bounded. It's two to the number of random bits that I'm using. Every bit can be one zero or one that's all. So in principle I can completely dandomize this algorithm A by just running it on all these possible random seeds. Indeed our probabilistic Turing machine model didn't even have randomness in itself. It just relied on having this uh random bit tape being filled with um uniform random inputs.

5:30 So we could simply do that um and output the majority as as before and unlike before this majority has to be exactly correct because we're trying all possible outputs and we're just picking the one that occurred most often. So if the algorithm uh is a BPP algorithm, bounded error, two-sided error, two-sided error, Monte Cara algorithm, then this majority must be correct. Of course, this uh two to the random bits is an exponential blow up. That means most of the time this is not interesting. But if for some reason the algorithm very scarcely uses random bits specifically uh at most c times log n bits then two to that is same as as 2 to the log n to the c and that's n to the c which is just a polomial factor. So if all we're looking at is can we get a polomial time algorithm from a polomial randomized algorithm that's deterministic then here the answer is yes because that's again a polomial it's the product of two polomials.

6:48 So this sounds like a potential route except of course most randomized algorithms wouldn't just use login bits because you can actually do very little with that. Essentially you can guess one random number between between one and n or maybe a constant number of such numbers but you cannot uh you cannot do uh many interesting things like guessing say uh a subset in a of vertices in a graph or anything like that. So typically they use at least a linear number of random bits. So this seems not to work. The question now is can we make it work? Because how would a typical algorithm even know whether the bits that it gets are truly random? Uh among programmers, this is XKCD. That's popular. Uh of course, randomness is a real tricky thing. Uh once you decide it, once you chose the random outcome, all randomness is gone. So what does this really mean uh to need the randomness?

7:58 If you go back, I mean maybe you want to philosophize and puzzle over this definition. If you look at what we need for BPP and the random the dandomization here is actually quite clear. We just need that this dandomization works which means it's okay if um the algorithm is somehow wrong or behaves differently for what we spit what we put in instead of the real numbers for a few of the runs but it should be most of the time doing the same. Okay, from the perspective of this kind of uh more rantine uh working against each other, the algorithm and the pseudo random number generator. Uh the question of how the algorithm could distinguish random from non-random numbers should also be defined by can you find a measurable difference in the outputs of the algorithm.

9:07 So um abstractly we would somehow like to keep inputs that are sufficiently random whatever that means. And um a breakthrough uh idea in in theoretical computer science was this notion of pseudo random generators in the specific sense we'll see where we essentially use uh that an efficient algorithm cannot distinguish them from truly random. And that's a key difference to the more practically focused view on pseudo random numbers where you say okay there's some statistical tests and if these are all if these all pass then probably it'll be fine. Um this is in a way more direct but also more demanding. You say no efficient algorithm that you could possibly build can uh distinguish them. That of course includes all statistical tests because all statistical tests I know are such that you can relatively quickly compute them. Maybe there's some some that don't fulfill this definition. Uh the the key will be to pick um a model of computation so that this uh whole machinery can be made to work.

10:21 And that's why the whole chapter is a bit of a a longer detour. But then the question still is do these even exist? Like is this uh are we talking about the empty set? Maybe it's not possible to generate many random numbers from just a small seed without efficient algorithms noticing them.

10:41 Uh in particular uh this phrase here may be uh a bit dangerous right? If you look at what we what we want, we can deal with login truly random bits. Then 2 to the login is still a polomial with a constant. If you have a linear number of bits, that's exponentially more than login. So in a way uh we're trying to get from very few random bits, a lot of bits, exponentially many more so that you still cannot distinguish them by any efficient algorithm. Sounds like a um wishful thinking land promise that maybe doesn't exist.

11:29 The somewhat surprising answer that goes hand inhand with this theory is that we have strong evidence that these should exist or might exist. There's no proof um but there's also no proof that NP hard problems are really hard. Uh it's it's roughly in the same vein and um we'll rely again on some complexity theory assumptions but is is likely that they exist.