What does it mean to be random? And how do you do it in a computer? Randomness is a weird kind of thing because
it's more defined by what it isn't than what it is. If you see something happening, and it's got
some kind of pattern to it, then you say, "Well, that's not random." If you can predict what's happening next,
if you can even just predict better than chance, what's going to happen next, then you say
"Well that's not random." So, something that's random is supposed to
not have a pattern, not be predictable. Well, that's a real problem for a computer,
because the entire way that we have designed, architected, and built computers, is so that
they will be deterministic. Serial determinism. The typical computer, the way it's designed,
it does one thing at a time. Step by step by step by step. Each step is guaranteed, as good as the quality
of the physical computer we can make, to be completely predictable, to be completely determined. The inputs determine the outputs. So in a computer program, if you can get all
of the same inputs, you're going to get the same output. And it might not seem that way, these days,
when, you know, you go to your social network and you click on it and everything's constantly
changing. You hit reload, it changes. But that's because there's all kinds of inputs
going into that program, that's producing that output, that we're not necessarily aware
of. If we could actually control all of the inputs
to the program, it would have to produce the same output. And if it didn't, the computer is broke. OK. So, if that's what computing is like -- step
by step, same input, same output -- then how could we ever get a computer to be random? How could we ever get it so that it would
be unpredictable? If we know the program, if we know the inputs,
we can totally predict. We can run another computer with the same
program, the same inputs -- we have to get the same output. So in computers we end up using what's called
'pseudorandomness'. It's not really random in the sense that if
you know all of the inputs, you can predict the output. So the 'unpredictability' part is unclear. But the idea that there's no pattern is what
pseudorandomness tries to get at. Let's look at a demo. All right. Here's a machine. I submit to you it's an amazing magical random
number generator machine. It's got a button down here that we can.. Alright, so we feed in the 'spark of execution'
and the machine cranks.. There! It produced a number. 90. It's a random number; it says it's a random
number. Let's make another one. Actually, let's just lock the switch down
so we'll make a bunch of them. Now, the first thing is, did you expect -- alright,
53 -- did you expect 90 to be a random number? As opposed to like 'heads', or 6, or 52 cards,
something like that? You can't even talk about randomness unless
you have some universe of possible events, some set of things that might happen. You can't even ask 'Give me a uniformly selected
random number between zero and infinity'. It doesn't make sense. So you already have to have some set of events
in mind. So this looks like, you know, two digit decimal
numbers perhaps. Now it's not, that might not be what you need. If you really just wanted a coin flip, heads
or tails, what are you going to do here? Well, I mean, you could say, you know, I'll
call even numbers 'heads' and odd numbers 'tails', like that. It's not up to me to use the whole number
that the thing is giving me. If it's really random, if it's really unpredictable,
if it's really got no pattern... Alright, well so 90. That's even, that would be heads. 53, that's odd, that would be tails. So heads, tails.. 74 is even, 81 is odd, 50 is even.. Wait a minute. 73 odd, 14 even: These are just alternating. Even, odd, even, odd, even odd. So how can that be random? It's a pattern. Well, this isn't random. Big surprise: It's running in a computer. Let's pop the hood. What we actually have under here is not a
random number generator in a 'real' randomness sense -- whatever that means. What we have is a pseudorandom number generator
PRNG. Pseudo Random Number Generator. And this particular one is called a 'Linear
Congruential Generator'. And this specific specific one is actually
a particularly bad linear congruential generator. But really, the LCG's are important, at least
historically, because they've been used for decades. They were the basis of much of what has been
done for computer simulations of all sorts of things, that could have lead to policy
decisions, could have lead to people thinking some things worked certain ways under the
assumption that these were decent random numbers. Well. Wait a minute. 90, 53, 74. Look at this. The first number was 90, here's another 90. The second number 53.. 74. 74, 50. Where's the 50, 73.. The next one's going to be 14. There it is. The next one's going to be 61. This has not only got a pattern to it, it's
predictable. I know the sequence that's coming here. That's why this is such a terrible random
number generator. OK. But still, let's pop the hood again, and actually
see what's going on inside here. Um. Alright. Single-stepping it now. So this is confusing looking, but it's really
very simple. We've got this red star that says what's going
to happen next. The first thing is we're going to do a multiplication. What do we multiply? This number, 4567, times this number, 93. And the result is going to be, I don't know
what it's going to be. The result is four hundred twenty four thousand
seven hundred and thirty one. OK, whatever. And then we move on to the next step. This is serial determinism. Step by step by step. The next step is to add this number, 23, to
that number, brup brup brup, and that's going to be four twenty four, seven fifty four,
right? Right. There it is. Execution moves on. Next step, do clock arithmetic.. You know, a hundred o'clock, here. Modulus operation with this number is going
to end up taking the last two digits, so that's going to give us a 54. And that 54 gets written back to this 'State'
box. And that's key. So what we have here is a cycle. The state gets read out, multiplied, added,
modded, and written back. OK? And then as the final step, that number gets
output as our random number. OK. And that's it. Let's go ahead again. So. That state variable did not get reset between
each cycle of producing a random number, and that's how it works. OK. The computer is deterministic -- same inputs,
same outputs. We thought this program didn't have any inputs. We thought we just sort of made it go, and
then it produced an endless stream of numbers. But really, the way we need to think about
it, is that that state variable is an additional input, that it writes and then reads back
in. As as result, we get a sequence of numbers
that changes over time, although in this case, it's not a very random sequence of numbers. Number 1: It alternates between even and odd. If we had different multipliers and increments,
we could get that to be different. Like, we could get them to be all even, as
if that's better. And in fact it loops; it has a period. No matter where it starts.. We can put it back at the beginning; that's
what this reset button does. Umm. Because.. which shows, by the way, that the
only thing that this thing has got going for it is that state. Once we reset it, which is called 'reseeding'
-- putting a seed -- because the beginning number that starts this whole process is called
the 'seed'. Setting the seed back to a known quantity
is called 'reseeding'. Now we're getting the same thing -- 90, 53,
and so on. Now, we could make this a little bit better
if we increased this limit, something like that. Now.. Because the state was limited to only two
digits, 0 to 99, before. Now it can go up to at least a thousand. Normally, when we make a linear congruential
generator, we let the modulus be something like in the billions. So we get these big things out, that look,
oooh, must be really random, but again they have these same flaws -- the last bit of it,
even-odd, even-odd, and so on. So, these are not, these are not great. OK, let's turn this off. And these random numbers, these are terrible. So let's get rid of them. The state of the art in random -- pseudorandom
number generation, has moved on quite a bit beyond the linear congruential generator. And today, you really do not want to be using
one. What do we use numbers for? Well, there's at least two big whole categories
of uses of random numbers in computers, and they're quite different, and we need to not
confuse them. One group is for models and simulations. Computer games, shuffling a deck in solitaire,
making a simulation of traffic flow where, when you come to a light, is the light going
to be green or red? Well, it depends on, you know, you throw a
random number, it's red 40%, 60% of the time, green 40% of the time, whatever it is. So in that case, we're using random numbers
to express, essentially, our ignorance. That if we had made a more detailed model
of that traffic simulation, well, whether the light was red or green was not actually
random. It depends on its circuitry and the timing,
and who pressed the buttons, and so on. And we could build a more complicated model
that would not have used randomness there. But in fact this is the way our brains work. When we have stuff that is extremely large,
we tend to assume it's constant. And when we have stuff that's incredibly tiny
and rapidly changing relative to what we care about, we tend to think it's random. And then the stuff in the middle, about the
size and the time scales that we're interested in, we tend to think there's causes for. One thing causes the next. So the big slow stuff constant, the small
fast stuff random, and then causality in the middle. So randomness is deeply tied to how we look
at the world. And when we build models in computers using
pseudorandom numbers, we're doing essentially that same process. We're deciding to say "OK, well this is causal
here -- I walk down to the corner because I'm walking to work. Whether the light is 'Walk' or 'Wait' is random
because I'm not really modeling that in detail." And so on. The second category of uses of randomness
is for secrecy, for encryption. And in that case, we have a very different
set of needs. When we're dealing with a deck of cards, the
stakes are low. Playing solitaire on the screen. On the other hand, when we're playing solitaire
in a video poker game in a casino, it's very different. If we could predict what was going to happen
we might be able to make money. The casino wouldn't like that. Similarly, if we're making keys, for our encryption,
to send messages, to secure our documents. If anybody can predict what those keys are
going to be, they can break our encryption. OK. So in essence, there's two views of randomness. One view says a random sequence must be completely
unpredictable, and if it can predicted, it can be broken. So the casino wants unpredictable, encryption
wants unpredictable. But then the bigger use, the more common use,
all we really care about is that whatever determines the sequence of numbers, it be
uncorrelated with the purpose that we're putting the numbers to. So even though there were patterns in that
LCG that we looked at -- that wasn't a good one. If we used those numbers to cause the simulated
traffic lights to turn red and green according to some odds, it's not clear that would actually
cause our simulation to be inaccurate, in the long run, on average. OK. But still, we would like, and this is the
whole crazy business of pseudorandomness. It's kind of -- it's not my words -- von Neumann
said that essentially if you ever try to produce random numbers in software, you're in a state
of sin. And what did he mean? Well, he meant because the whole points of
software is to be deterministic, is to be not random. So pseudorandomness is all about that hidden
state. OK. And so one of the reasons why this random
number generator is so bad, this pseudorandom number generator, is because it has a very
little bit of state. Once the state has repeated itself, the whole
sequence has to be repeating, because that's the only way, that's the only extra input
it's got. Here's a picture of a more modern pseudorandom
number generator called the 'Mersenne Twister'. It's been around for twenty years or something
now, and it's pretty good. I'm not going to show the whole step-by-step
of the algorithm because it's a little involved, but let's just look at how much state it's
got. OK? So we'll pop the hood here. This is the state of the Mersenne Twister. Represented with a white square for a zero
bit and a black square for a one bit. So. And here we're producing these numbers. You might see these colors moving through
here, those are saying stuff about how the algorithm is working internally. But the weird part is we're getting all these
numbers -- 2 billion, minus 100 billion, whatever it is -- not a hundred billion, that's too
big. But it doesn't look like the state is actually
changing anywhere. Except if you.. Let's speed this up a little bit. If you look up at the very beginning here,
you can see some stuff changing. Because what really goes on, that's a counter
up there. And all of this state, is 624, 625 numbers,
random numbers, that the Mersenne Twister has precomputed. So when you ask for the next number, it doesn't
actually change any of the state. But we're about to get to the end; when the
green bar gets to the end there, boom, then the whole state changes. OK. So it's all being batched up. And what that allows us to do -- it makes
it a little weird, because when you call for the random numbers, you get, you know, 624
of them very rapidly, and blap there's this big wait while it goes through and mixes all
the bits. And the reason it keeps so much state is that
when it's mixing the bits, we want to be able to mix them from far apart. Not just use the previous value of the state,
but I'm going to mix the current number with a number 397 calls to the random number generator
ago, or in the future, in the batch. Now, one of the things we can do here, is,
we can kind of cheat.. Again, this is a pseudorandom number generator. If we set the seed to a known quantity, and
get an output -- 1.7 billion, minus 12 million. If we set the seed back to the beginning,
1.7 billion, minus 12 million, and so on. So, reseed the array, the behavior is completely
predictable. Now, we can cheat. The Mersenne Twister is designed so that you
can't really set the seed to anything that isn't like this -- sort of a hash of black
and white. But I went in and I cheated. Here's where I initialized the entire state
array to be all zeroes except for one one right in the middle here. OK. And now -- again, regular Mersenne Twister
will never do this, but we've abused it. And now we're getting this output which is,
you know, zero zero zero zero, which is obviously not very random at all. But the reason I do this, let's speed it up. When it rebuilds itself, it gradually starts
to smear out the bits. And it takes quite a while. Let's speed it up still more. OK. Now, if you look at this, you might be able
to see it. There's this pattern, where it looks like
it's moving up and to the right, up and to the right. Can you see it? That's because what the Mersenne Twister is
essentially doing is using all of those nearly twenty thousand bits as a giant shift register,
where the bits move out of this guy, up into the next one, up to the top of the last column,
down to the first and so on, like that. So it's like a giant multiplication where
it then takes a bunch of stuff and adds it in. So it really is, in some loose sense, quite
similar to the multiply and the add of the simple linear congruential generator. It just has much much more state. And more carefully thought-out state as well. Alright. So that's it. Randomness is this weird thing because it's
about what it isn't. When you're using a random number generator
you gotta avoid the bug of seeding the number generator over and over again. The whole point of the seeding the generator
is to get the initial value of the state, and then you can ask for numbers, and let
the state inside the random number generator keep track. There's also random number generators, haven't
talked about, that are in computers, that are claimed to be real random number generators. And the way they work is by using timings
of mouse clicks and keyboard types and packets arriving and stuff coming from the disk, and
mix it all together under the assumption that there's no pattern to all of that stuff put
together. And it's probably true, it may be true, but
who knows? That's just saying there's state in the outside
world, there's state in the user's head, about the timing of when they do things, that we
can exploit to make numbers that are unpredictable. Finally, the bottom line, if you're in a position
where you're building a model of some sort, you're using random numbers, make sure you've
got the Mersenne Twister, or at least something reasonably modern. There are still bad random number generators
out there. Don't use them. OK, that's it.
That's a really neat visualization. Though I think there are more interesting algorithms for this than MT. He even skipped over one of the most interesting parts of MT (as far as watching the state): the array being reshuffled. Here's what that looks like:
https://nullprogram.com/video/?v=mt19937-shuffle
Source