In Our Time - Random and Pseudorandom

Episode Date: January 13, 2011

Melvyn Bragg and his guests discuss randomness and pseudorandomness.Randomness is the mathematics of the unpredictable. Dice and roulette wheels produce random numbers: those which are unpredictable and display no pattern. But mathematicians also talk of 'pseudorandom' numbers - those which appear to be random but are not. In the last century random numbers have become enormously useful to statisticians, computer scientists and cryptographers. But true randomness is difficult to find, and mathematicians have devised many ingenious solutions to harness or simulate it. These range from the Premium Bonds computer ERNIE (whose name stands for Electronic Random Number Indicator Equipment) to new methods involving quantum physics.Digital computers are incapable of behaving in a truly random fashion - so instead mathematicians have taught them how to harness pseudorandomness. This technique is used daily by weather forecasters, statisticians, and computer chip designers - and it's thanks to pseudorandomness that secure credit card transactions are possible.With:Marcus du SautoyProfessor of Mathematics at the University of OxfordColva Roney-DougalSenior Lecturer in Pure Mathematics at the University of St AndrewsTimothy GowersRoyal Society Research Professor in Mathematics at the University of CambridgeProducer: Thomas Morris.

This BBC podcast is supported by ads outside the UK. Thanks for downloading the In Our Time podcast. For more details about In Our Time and for our terms of use, please go to BBC.co.com.uk forward slash radio four. I hope you enjoy the program. Hello, a little earlier today I rolled a single die ten times. This is what I got. 6.1. 3. 4.4.4. 1.2. 1.4. 1.4.

That's a sequence of random numbers between one and six. Random because there's no pattern to them. It's impossible to predict the next number in the sequence. Randomness will be familiar to anybody who's bought a lottery ticket or shoveled a pack of cards. A key feature of randomness is that what you do one time has no effect on what you do the next time. But there's also a phenomenon known as pseudo-randomness, numbers which look random but aren't. Sudo-random numbers are essential in statistics. Drug trials, trials, medical trials.

generally and opinion poles would be all but impossible without them. Cryptography and electrical engineering at just a couple of the many other fields where pseudo-randomness is highly valued. With me to discuss randomness and pseudo-randomness are Marketsu Sotoi, Professor of Mathematics at the University of Oxford and Cimony Professor at Public Understanding of Science, Colvert Roney-Dougall, Senior Lecturer in Pure Mathematics at the University of St Andrews,

and Timothy Gowers, Royal Society Research Professor in Mathematics at the University of Cambridge. Marcus De Soto, I've just mentioned throwing a die, but can you give us another example of randomness, and what precisely is meant by the word? Well, I suppose the lottery is a very good example of randomness, and it's exactly the point you mentioned in the introduction, that you shouldn't be able to work out what the balls are

that will come out next Saturday from the balls that come out the previous Saturdays, and that's the key aspect of randomness, this inability to work out what's going to happen next, is non-determinism. I suppose the roulette wheel as well. Gambling is somewhere where they depend on randomness that people coming into the casino can't tell what's going to happen next. But actually it's quite a slippery subject

because something like the roulette wheel, for example, well, is it truly random? If you know the initial setup of this thing, perhaps you can make predictions about find a pattern to what's going to happen to the ball as it falls into the roulette wheel. In fact, there's a case where, where three Eastern Europeans at the Ritz walked away with over a million pounds

because they'd been able to assess what was happening in the roulette wheel and make a prediction. So actually randomness is about something where you can't make a prediction, but actually finding something which is truly random is actually quite difficult. They made a prediction those three men based on narrowing the odds, but is that really, as it were, a sailing randomness? The odds are 36 to 1 in a roulette wheel, aren't they? That's right. By working things out, 37 to 1.

37. And they reduced it to six to one, and they had mobile phones now banned at the Ridge Casino to make this work. They weren't charged because they hadn't interfered with the mechanism itself. But is that just narrowing the odds? Is that really attacking randomness? I think it is. It's on the way to attacking randomness because they were able to limit the area that it would arrive in. And ultimately, you think, if rolling the dice that you rolled this morning,

if you knew the initial conditions of that dice and exactly the laws of physics, you put those in, you should be able to work out where that dice will land. But the point is that we don't have enough information such that it is unpredictable. And I think you'll mention a pattern is really important here, because the point is can you spot a pattern in the behaviour before you're trying to see what happens next, which can help you to predict what's going to come out of the lottery next week? And something like the lottery and the casino are trying to produce randomness such you cannot spot a pattern. You seem to me,

because it isn't in your nose or any more. You see you need to be saying that we're calling random something that we also think is on the way to being solved if we knew more. Well, I think that if you think of the universe as being deterministic, I think, this is a good word, deterministic, I think, for randomness, because randomness is something which is non-deterministic. You cannot work out what's going to happen from the previous information. And ultimately, sort of Newtonian physics,

if you knew exactly the initial setup of the universe, I mean, Newtonian physics says it would run like clockwork and because a dice basically works on Newtonian physics. I mean, I think we're going to come a little later to the involvement of quantum physics, which is interesting in this respect. But essentially, if you know the initial setup of a dice exactly, then you should be able to work out where it lands.

But the point is that we can never know exactly the initial setup of a dice. So it means that it then becomes non-deterministic. There's not enough information to be able to determine. in what's going to happen next. Colvaroni Duhl, can you give us some historical perspective on this? Let's go back to the Greeks. I met a lady once who said, if you said, let's go back to the Greeks once more, she would lose the will to live.

But still, let's go back to the Greeks. They were interested in numbers in this area, weren't they? Yes, so the Greeks didn't have a mathematical discussion about randomness, but what they did have was quite a lot of philosophical discussions about the nature of randomness. So, for example, in the writings of Democritus, who's probably most famous for the atomic theory of matter, believing that everything's made up of tiny and divisible atoms, he deduced from that that the entire universe was deterministic, and hence there is no such thing as randomness. He said that all we're saying when we talk about randomness is measuring our lack of knowledge. And he gave the example of two men who send their servants to the well at the same time. They do it so that their servants will meet at the well deliberately because they'd like them to speak to each other. But the two servants not knowing this think that they've met at the well by chance. So he thought that if we could properly understand the way the whole universe works,

there would no longer be any such thing as randomness. Now, about 200 years later... And no such thing as coincidence, everything happens for a reason and could be predicted in advance. About 200 years later, Epicurus is writing, and he also believes in the atomic theory of matter, but he fundamentally disagrees with Democritus on the nature of randomness. He believes that the atoms swerve randomness.

randomly in their pods, completely randomly in their pods, and that this is an irreducible source of unpredictability in randomness in the universe. So no matter how well we understand the physical world around us, there will always be random effects that we can't measure and predict. So discussion of the nature of randomness, but no mathematicising of it. For example, Aristotle, a third writer on randomness, divided all the events in the world into certain things which will definitely happen, probable, things which are very likely to happen

unless something unexpected intervenes and unknowable. And he does write briefly about games of chance, so in this case it would have been throwing of knuckle bones and so forth, but he believes that the outcome of those events falls into the category of unknowable, and he makes no attempt to connect it to mathematics. We have to jump as far as I can gather from your notes,

because not much happened in this area, until the Renaissance. Indeed. About almost 2,000 years later. And we come to one of the first. the people who come to is a gambler. Indeed. Gambling and random have been happily associated

or mostly, I suppose, unhappily associated, for many years. So can you talk about that? Yeah, sure. So the gambler you're referring to is Gerolama Cardano, who's famous for a great many things. He was a famous medic. He once travelled to St Andrews in Scotland to cure the then-archbishop of asthma. He was a very well-known mathematician, and we've talked about him on this show before.

But in this context, what's important is he's the first person to correctly write down. and this is as late as the 15th century to correctly write down the probabilities for throwing one dice and getting one, two, three, four, five and six, and to say that all cases are equally likely, so you'll get one sixth for two dice and do the various combinations, how likely am I to get a double six, and for three dice. Even at this late stage, there's no beginning of a general concept of how probability might work. He's writing a handbook for gamblers.

He gambled so much that he had to pawn his wife's jewelry. and they had to pawn their furniture and they wound up in the poor house at one point. But over the course of his life, he eventually decided that some little kind of notebook, roughly telling gamblers how much they ought to be willing to bet on certain things, would be worth writing.

The beginning of the actual full mathematical theory of probability starts about 100 years later after that. Can we follow Cardana for a moment? Sure. He's absolutely fascinating. I mean, he, because his book was published much later and it was a very, very important and interesting book. And yet it didn't work, did it?

Ended up in the poor house with his wife with... Well, he did recover from the poor house at that point. I mean, he... So he was born illegitimate, and I think a lot of the... One may trace a lot of his problems to a desperate attempt to gain respectability, gain prestige, whilst being pushed out

and was quite argumentative. Apparently, in a row over dice throwing at one point, he'd cut a man across the face. They were arguing as to whether or not the dice were biased. Right, I'm going to get back to, my fault, can we get back to his, did he advance the notion of study of random numbers in this book that was eventually published over 100 years after his death? Well, he was the first person to correctly notice that if you're throwing two dice,

the fact that you can throw seven in more than one way, that you can get a six on one and a one on the other, or that you can get a three on one and a four on the other is more significant than, that that makes you more likely to throw a seven than you are to throw other numbers. So it was the very beginning of actually properly mathematicising probability. And you were going to push on 100 years?

Yeah, so Thirma and Pascal, Pascal, who's more famous for his ponces, were the first people to actually develop a proper theory of probability and that they were the first people to say, well, if we can divide any situation into a number of equally probable events, Suppose I can divide throwing a dice into six equally probable events.

That's each of the possible numbers that could come up. Or I can divide a roulette wheel into 37 equally probable events. That's each of the numbers that can come up. Then there is this thing called a probability, which says the chance of any of them coming up is one over the number of them. So one sixth for a dice, one over 37 for a roulette wheel. And that's the beginning of properly conceptualising a way of assigning numbers to randomness. Tim Giles, we've heard a bit about random numbers

But what are pseudo-random numbers? Well, it's a little easy to talk about pseudo-random sequences of numbers Right. So let's imagine you had a sequence of noughts and ones. If, say, they were all noughts, you could be pretty confident that they hadn't been produced by somebody tossing a coin and writing down nought whenever you had a head and one whenever you had a tail

because that would mean a coin had come up heads every single time. So you can imagine little tests that you might do to see whether you think that the sequence has been produced randomly. And so a very simple test is that the number of heads should be roughly the same as a number of tails. But if it just went 0-1, 0-1, 0-1, you'd still think that it wasn't random. So there's too much of a pattern there.

But you can do another test that defeats that. You could say that roughly half the time when you've got a head, you should get another head immediately following it. As in heads and tails. Heds and tails. Yes, indeed, yes. I'll go to noughts and ones then. So half the time after a nought, there should be a nought, or roughly half the time,

and roughly half the time there should be a one. And then there are a number of other tests. You can have increasingly sophisticated tests, and statisticians have these tests for randomness. But it turns out that there are some completely deterministic ways, sort of mathematical formula that you can write down, ways of producing sequences of noughts and ones, that fool all the tests that the statisticians do.

So there are sequences that are produced in a completely deterministic way and yet they pass all the randomness tests that you throw at them. And so we call them pseudo-random. Pseudorandum basically just means they look like random sequences. Why do you call them pseudo-random? Why is it important to distinguish them from what you're trying to get at as truly random? Well, what you want from it in a way is that they shouldn't be too easy to distinguish from random. In other words, if you're using them, you want them not to be distinguished.

So the difference is just in how they're produced. Randomness, as Marcus has already said, is a slippery thing, and it's difficult to get hold of. And sometimes you think you've got something in nature that behaves randomly. And on closer inspection, you find that it's not quite as random as you thought. And if you'll say using random bits in a computer program, it's not very convenient to use some physical source of randomness. So you want to come up with some mathematical things. that will mimic randomness for you.

And so that's where pseudo-randomness is useful. So it's not exactly important to distinguish from the point of view of actually using them, but the theoretical distinction is very important. Can you give us a good example of a pseudo-random number and how it works? Well, an interesting example is the number pi. That is not random at all.

It's defined to be... For people who... I'm going to say, so it's the ratio of the length of the circumference of a circle to the length of the diameter of a circle, and it's a little bit over three. In fact, the decimal expansion starts 3.14-15926. There couldn't be anything more deterministic than that. I've told you exactly what Pi is, and you can work out what all the digits are. But if you go off and Google the first 10,000 digits of Pi, there are lots of websites where you can find this, and if you're you. you bring up one of those websites and look at the sequence of digits you get,

it looks to all intents and purposes like a completely random sequence of numbers between nought and nine. It really does look as though someone's taken a ten-sided dye and rolled it over and over again and just written down what they've got. And more sophisticatedly, you can say, well, if you just apply these tests that statisticians apply, you do find things like that the number seven in the decimal expansion of pi occurs roughly 10% of the time, just as you would expect, if it was completely random. and seven followed by five happens roughly 1% of the time and so on. Having said all that, it is a rather fascinating fact about Pi

that although looking at the first sort of even millions of digits of pie, you observe this random like behaviour, nobody knows how to prove anything about it at all. Nobody knows that there isn't some point beyond which there are no more sevens or something like that. The sevens, as I read from those, sevens have been disappearing as you get into the billions of, point such and such?

Well, I expect if that's the case, they will reappear quickly. Because it would be very big news if it turned out that there were... One of you said the seven had been disappearing lately, but it'll have a comeback. Sorry, I interrupted you. I don't think so, actually. I think you've finished.

Marcus, another place where pseudo-random numbers crop up is in prime numbers, which is something that obsesses you. I was going to say fascinized. It wasn't strong enough. Can you prime number is a number that can be divided by one or by itself and that's all like 5, 11, 17.

And it goes on and on and on and on prime numbers. Exactly. And like pi, you can't make a number not prime if it is. I mean 100 is not prime and 101 is prime. They're the most sort of deterministic things in mathematics what they're what mathematics is built from.

But on the other hand, similarly to pi, if you start to try and predict where the next prime will be, try to find a pattern, it seems very hard to spot a pattern. They seem to be laid out, almost pass this test for pseudo-randomness again. They seem to be laid out very much as if they were rolled by a dice. And that's actually a model that we've been using to make predictions about the primes. The primes thin out, so the dice is sort of getting larger and larger number of sides. but we actually have been able to prove something called the prime number theorem,

which says how many sides are on the sort of prime number dice for a number with 100 digits, a thousand digits. But it's interesting that the way they're laid out seems to be in that random manner that, you know, you don't expect with a toss of a coin to get exactly half heads and exactly half tails. If I toss a coin a million times, well, I can get some error either side of that. and a truly random process, a coin which isn't biased, will give me about roughly the square root of the number of tosses, which is in this case a thousand.

I can have an error of about a thousand either side of halfway, and that's acceptable for a random process. The prime seems to be behaving in exactly the same way. This prime number dice seems to be laying them out, making them rarer and rarer, but our greatest unsolved problem, the Riemann hypothesis, is actually a statement about the, fact that this dice does not seem to be biased, the way the primes are laid out, seem to be

in this kind of random manner. And you can use this to make amazing predictions about the primes. The primes are not random. We must, you know, really emphasize this. They're not random. But amazingly, they look random. They have this characteristic of random. And if you then analyze, okay, what happens with a random process. For example, you get clumping. In your dice roll this morning, you've got three fours in a row, which you might think, oh, that's, perhaps it's biased. But no, we know. We know. that randomness is very likely to cause this clumping, that's, that's, uh, randomness is quite counterintuitive and that's what the mathematicisation of randomness is about spotting these

characteristics and these tests, which Timothy mentioned, that you've got to pass. Primes as well tend to clump and have big spaces, something called the twin primes conjecture that you get two primes sort of, uh, with just, uh, an even number between, something like 17 and 19. That's what we would expect that sort of, that to happen. infinitely often as we look through the primes. Colner, how is it possible for a mathematician to look at a set of numbers and decide whether or not they're random following what Marcus has thoroughly confused this? No, you're not confused. I used to confuse the wrong word.

Use the one complicated issue. So we can never decide for sure that a number's random, but what we can do is apply an increasing number of tests and treat our sequence of numbers as innocent until proved guilty, basically. So I'm going to do some tests of increasing complexity. And if they pass enough of them, then I'll stop and say this sequence of numbers is random. So Tim's mentioned one of them already. I would look to see, suppose I was generating numbers 1 to 6, dice throws.

I would look to see whether roughly 1-6th of them were 1s, roughly 1-6th were 2s and so on. That's called the frequency analysis. I'm looking at the frequency of the 1s, the frequency of the 2s. After that, we would look at consecutive pairs. So I should see a 1 followed by a 6 as often as I see a 1 followed by a 1. so I could look at all of the ordered pairs, the first number with the second, the third with the fourth, and check that all of these pairs were coming out equally often. After that, there's a series of more bizarrely named tests.

One of my favourite is the poker test, where you analyse the numbers in groups of five, and you break them down into the kind of hands you get in poker. So are they all different? Do I have a single pair? Do I have two pairs? Do I have three of a kind? Do I have some kind of full-house situation where I've got, say, three-ones and two-threes? and I can analyse in advance the frequencies of the different poker hands I should expect to see

and check that I'm getting roughly the same frequency in the bunch of numbers I've got. So each of these will give me some kind of how well do they match measure? Do I have one-sixth ones? And what I do after that is to apply a test called the Kai Squared test, which was invented by the British mathematician Carl Pearson in 1905. And what that does is gives me a way of saying how likely it is, given the proportion of ones, twos and threes that I've seen, that these really did come from chance

and that it really was an unbiased dice that I was throwing. But I should emphasise again, I could never prove that a sequence of numbers is random. I could only say that it looks and smells random, given all the tests I've been able to apply so far. It's entirely possible, of course, that the dice will give you, this morning you did 10 fours in a row. I mean, that is as likely as the particular throw that you did.

And you would say, well, that's not round, That's not a random sequence of numbers. And so these tests, this is why this subject is quite slippery, because with a finite sequence of numbers to say, you know, well, I can spot a pattern in that or or, but each one is equally likely to have been produced by a random dice. So what's happened one time? There's no bearing what happens the next. Yeah, that's the point.

Somehow those, if you've got 10 fours in a row, it still wouldn't help you. You'd say, oh, well, I'm going to put all my money on there being a four on the 11th threat. but a truly random process will one in six chance. Tim Giles, I'm told that one of the great unsolved problems in mathematics is Goldbach's conjecture. Now, how does that fit into the discussion? Well, first of all, what Goldbach's conjecture says is very, very simple indeed. It says that every even number can be written as a sum of two prime numbers. So if we take an even number like 20, say, you can write that as three plus 17, and three and 17 are both prime numbers.

So 20 satisfies the conjecture. And in fact, it satisfies it in two ways, because you can also write it as 7 plus 13. But nobody knows how to prove that that is the case for all even numbers. It's been checked up to very, very high numbers of intensity, millions and far beyond. Now, where randomness comes in is, Marcus has already mentioned, that you can model the primes in a random way. You can think of them as though they were random. If you do that, you can then predict, not just, you can look at an even number and say,

well, how many times would I expect to be able to write that as a sum of two primes? And it turns out that for even numbers when they get large, you'd in fact expect not just that it's possible, but it's possible in many ways. So the prime numbers allow you to, or the randomness of the primes, the seeming randomness of the primes, allows you to make predictions. Now, you might think if you're trying to prove goldbasker, objector that what you should do is to come up with some formula for how to write your even number as a sum of two prime numbers. But as Marcus has said, the primes are very, very resistant to anything

to do with formula. They seem random. So no formula will even be guaranteed always to produce primes. So instead what we do is we sort of embrace the randomness of the primes. What one tries to do is to prove completely rigorously that the primes are pseudo-random in a sufficient way that that will mimic the behavior that you would expect if they were random. and although this, I mean, I'm saying all this and you might think it's a bit of a waste of time because it's still an unsolved problem. But there is a closely related problem

which is actually a theorem, which says that every sufficiently large odd number is a sum of three primes and that is actually a theorem due to Vina Groddorf and one of the highlights of 20th century mathematics and it was proved by roughly this strategy. You show rigorously that the primes are pseudo-random in a certain sense.

They pass certain tests for randomness and you use that information to demonstrate that every sufficiently large odd number is a sum of three primes. It's not an easy argument, but the strategy, the general strategy, does work for that problem. So what essentially is unsolved?

It just simply is the case that there might be some incredibly large, even number that is the sum of two... Sorry, not a sum of two prime numbers and just nobody knows how to rule that possibility out. And if that were to be the case, what would that lead to?

It would just lead to the solution of a very famous problem. Now that Fermat's last theorem has been solved, it's perhaps the most famous, easy to state. It's the one I get most letters about it. People who think they've proved it. So it'd be very big news, even if it's not going to change the way the internet works or something like that.

Marcus, another field that has benefited, well, one field that does benefit of randomness is statistics. Can you develop that, please? Absolutely, because in statistics, what you're often looking for is testing whether there's a connection between two things, or perhaps you're trying to poll the population to see what they're going to vote. And often you need to have randomness. You don't want to put bias in it by choosing a proportion of the population that have a particular quality about them. And a very famous example of this was the US election in 1936, where they were polling people to see what they were going to vote.

and it seemed to be a landslide for the Republicans. And then Roosevelt won with a landslide for him. And the point was they had not chosen the people they were polling randomly. They'd phoned people up. And they'd randomly chosen the phone numbers, but of course the people with phone numbers were in that period, 1936, were a very particular class of people. And so nowadays that probably would be a good way of randomising things.

Most people have a telephone. So when you're trying to look for a connection between things, the population and what they're going to vote, randomness, for example, is very important in taking a poll. It's also important, for example, in medical tests. If you're randomly assigning a drug versus a placebo to the people that you're testing the drug on, you truly need randomness in order, if you don't have randomness, you're going to get a bias which will disrupt seeing whether there's a connection between the drug and curing something.

Can you develop that even a bit more? Why is randomness, can you just say more about that? Yes, because randomness is making sure there isn't some sort of a pattern that is going to force the experiment to go, or the statistical thing you're trying to analyse, are going in a particular direction. So if you've actually not been able to choose your sample set in a random way, you might have chosen all men or something.

and if it actually behaves very differently for women, then you're going to have biased your actual experiment. As a really concrete example, if you come back to the idea of you're going to take a telephone poll, that's probably fairly acceptable now because most people have telephone numbers. So imagine you've got the phone book of Great Britain and you've got everybody's phone number.

Well, what you certainly shouldn't do is pick the first thousand phone numbers because they'll probably all have fairly similar surnames and you may have just picked one extended family and asked all of them how they're going to vote. What you need instead is a source of random numbers to let you go through this massive list of phone numbers and pick people who are going to be unconnected to each other. There grew the attempt with the growth of statistics in the late 19th century,

particularly in this country or in this country, any sort of, to manufacture random numbers. Can you give us some of the methods that were discovered and employed? Sure. So this really began in the 19th century, and it began with people generating random numbers for their own use, So statisticians and biologists in particular needing random numbers for studying hereditary and evolution. And the early attempts would simply throwing dice, as you might try yourself at home.

And that ran into massive problems because, as we've already hinted, particular dice have a tendency to be biased. So they're more likely to come up with certain numbers. So by the biologist Weldon and his wife spent evening after evening throwing dice, and it turned out after they'd done 10,000 throws that their dice were giving too many sixes. those dice were not perfect. So at the beginning of the 20th century there was a real push to try and get proper random numbers. The first book of random numbers was published in 1927

by somebody called Tippett. And what he used was the census data. So a census had recently been conducted and he took the middle digits of the areas of parishes. So the areas of parishes, presumably in square miles or something, had been published in this census. And he took the middle digits from those as his... random numbers. Shortly after that, in the 30s, Fisher and Yates, who were working at the Rothamstead

Research Station doing breeding studies on snails, needed random numbers for analysing their statistics. And what they did was they used two packs of cards to select numbers from logarithm tables. So we used to publish tables of logarithms for doing addition, for doing multiplication. They used two packs of cards, first of all to pick which table and then to pick which number from the table and then they took the 15th to the 19th digits of these logarithms that were appearing. But that ran into problems too. They had too many sixes again. It keeps being too many sixes. So what they did was they selected 56es at random and replaced them with other digits, which left people slightly uncomfortable by the use of these tables because they'd been definitely fiddled

with after the fact, if you like, to meet these tests that both I and Tim have referred to. So what we do now, and which started in the late 30s and through into the 40s, is there's various machines that are used to generate random numbers. Can I ask you to them, guys, why can't people just sit down and draw a list of random numbers themselves? Why are we having, as Colvo is about to go into increasingly complicated, sophisticated machines, which will continue with? But why can't you just sit down and say, look, 5, 7, 8,000, 48, 38, 58, 55. Well, a good answer to that is just to try it. Just try it with just noughts and ones.

And have a look at what you've done afterwards. The reason it's difficult is that there's just a lot to keep track of. I've talked about all these tests. You've not only got to make sure you have roughly the same number of noughts and ones, but also that you've got roughly the same number of nought noughts pairs, 0, 0,0 pairs, 0, 0,0 pairs and then 0, 00 pairs, 0, and so on. and the chances are I think most people will fall if not at the first hurdle if they don't already have a slight tendency to say more noughts and ones or more ones and noughts

will definitely fall at the second hurdle they won't have enough pairs where they're the same or pairs where they're different or something like that It's just because people get tired or because there's something about our brains that can't do this. It's not just because we're tired or stupid or anything like that it's because there just is an awful lot of information

that you have to be keeping track of in order to make sure that all the tests are passed. I think it's also our sort of total addiction to patterns that we do tend to pattern the world. And so when we're trying to come up with a random selection numbers for the lottery or something, we will latch on to certain patterns in producing them. And again, I think it's that randomness can often be very counterintuitive.

I think that run of fours that you had with your dice roll is not, people just would not put three fours in a row. if they were choosing things, if they thought they were choosing things randomly. And you can see this in the lottery, because in the lottery, half the numbers that can come out will have two consecutive numbers in them. But you look at the people who choose their lottery tickets, not half the population chooses two consecutive numbers in their choices of lottery cars. So we are very bad at doing randomness, partly because I think we have mathematical brains. We're constantly searching for patterns. Peter Coles has a lovely example of this.

He's a physicist from Oxford, and he's got two pictures, so just dots scattered around on a plane. One of them's been produced by a genuinely random process, so you see clumps and streaks and so forth. And the other's been produced by a process where if you have a dot in one area, you're slightly less close to get another dot near it, so everything's slightly smoothed out.

And he shows them in lecture after lecture and says that consistently, the vast majority of the audience, think that the smoothed out picture is the random picture. and the random picture, which has all sorts of clumps and patterns appearing in it, they think that is the non-random picture. What did this Russian mathematician, Kolmogorov, add to the... Tim, could you talk about that? Well, there's a definition called Kolmogorov complexity.

And roughly speaking, the complexity of a sequence of noughts and ones is the shortest description of that sequence. So if you have a sequence that goes nought-1, 0-1, 0-1, something like that. that, you could describe it by saying alternate noughts and ones, and that's a very short description. If you tossed a coin a million times, wrote down the resulting sequence of noughts and ones, and then tried to specify that sequence, you wouldn't have much choice other than just to write out the whole sequence. And so then that would be a very, very long specification. So that was, the second one would have extremely high comagor of complexity, whereas the first

one would have very low comagos. Yeah, and so it seems that that's a measure of randomness. And I think your sequence of dyes, you know, I wonder how many listeners, they heard that right at the beginning. How many listeners can remember the ten numbers? Now, if those ten numbers have been one, one, one, one, one, one, one, one, one, they would have remembered that. And so this Cornel Magorov complexity is almost

can you find a pattern which reduces the sort of sequence so I can actually remember this thing? And one of the unexpected things that was proved about Karl-Mogorah of complexity, one of the reasons we use it is you can prove that given something whose Coromagor of complexity says that it should be random, that it will in fact pass

every single computable statistical test for randomness. There's an unexpected connection I'm told probably by you, Marcus, between quantum physics and random numbers. Can you develop that? Yes, I think because a question has been hiding behind all of this right from the beginning, is is there anything truly random? Because that dice, okay, I might not know exactly how it's set up, and that's the point that I don't have enough information, as you pointed out. It seems to be about, isn't it a lack of information?

And so if I knew exactly how the dice was set up, I should be able to make a prediction. It's a deterministic system. The only thing we have in sort of the physical world, which seems to be truly probabilistic, is quantum physics. Because this is about the strange physics that electron doesn't quite know where it is until you observe it. So it can be in two places at the same time. And then when you observe the electron, it seems to probabilistically decide whether it's in one place or another. So a good example of a random number generate. for example, is to use a piece of radioactive material, which over time releases a little bit of

radioactivity. But when it's going to release that bit of radioactivity, it seems to be genuinely random. And again, quantum physics, the model for quantum physics that we have is a probabilistic one. We do not know what it's going to do. We have a probability model for when it should do that and it satisfies that model. Again, this might be the fact that quantum physics, the model at the moment, this probabilistic model, is about the fact that we don't understand the physics that are very small. But I would say that

producing something truly random, the only way that we have at the moment is probably tapping into quantum physics. Tim Giles, mathematicians eventually discovered they could use simple tricks to generate sequences of apparently random numbers. Could you listen to some notion of that? Well, there are all sorts of different methods for doing it.

But one of the simplest was invented by John von Neumann in 1946. It's called the Middle Squares method. What you do is you start with a long number, say 100 digits or something like that. That doesn't have to be random. You can do it however you like. You might call the seed.

And then you square this number. If it starts off as 100 digits, the square will have roughly 200 digits. And then you take the middle digits or the middle hundred digits of this square. So everything from the 50. digit to the 149th digit, say. That produces for you a new number, which is a very scrambled version of the original number. And then you just repeat this process. You square your new 100-digit

number, you get a new 200-digit number, take the middle digits of that, and keep on squaring. And this turns out to be an incredibly good shuffling technique. It produces in no time at all sequences of numbers that really don't have any discernible pattern to them at all. Let's try to get back to the notion that why do we, why a random number so? important in various areas. They're important, as we mentioned in Marcus in Opinion Pills, we're told they're important in medical trials, in electrical engineering. So you're nodding to all that, Colbert. Can you confirm that and then talk about, let's go back to gambling, how it works with Ernie the Premium Bond computer? Ah, yes, so Ernie the Premium Bond computer. So the thing with

Ernie is he really does need to be properly random. The first Ernie was built in 1957 and we're now up to the fourth Ernie, he can't be pseudo-random. If he was pseudo-random, somebody might be able to get the formula that was being used to generate premium bond numbers and they would know whether to sell their bonds or buy more bonds or whatever. If Timothy, if you knew Timothy's starting number, you'd be able to work out everything after that. Yeah. So Ernie has to be non-deterministic. He can't just look and smell random. He must be truly random. So there's a chip inside Ernie, which uses what's called thermal noise from the electrons. So anything that's, that's not at absolute zero.

The electrons are going to be moving around a little bit. And that randomly moving around a little bit of the electrons can be used to measure voltage randomly going backwards and forwards a little bit. Now that random going backwards and forwards is then turned into numbers. First of all, the government statisticians check that those numbers pass the frequency test, pass the pairs of numbers test and so forth. And then only after that does this long string of numbers get chopped up into numbers of the right length to possibly be premium bond numbers,

and then only after that are they compared with existing premium bonds to see whether or not who's one and whether they are genuinely premium bond numbers or whether we need to make more random numbers, but Ernie must be non-deterministic. I think there are lots of examples in the physical world. We need randomness to try and model things. There's randomness everywhere.

I mean, the way that the gas in this room is behaving is random. If we want to make predictions about what it's doing and model it, we need random numbers in order to do experiments and make predictions about what's going to happen, the way cells work in our body is random. So we need random numbers in order to try to actually model the world. But it's also a good example of pure mathematics turning into practical results,

because I've mentioned electrical engineering and medical assessments and so on. So it's out there as well, isn't it? Yeah, we certainly need. And it's interesting that a computer, will need some way of generating random numbers in order to be able to do sort of experiments. One classic example that people probably don't realize they're using

is when they're sending their credit card across the internet. They need random prime numbers in order to be able to keep this credit card secure. If they're not random, somebody's going to be able to crack into their credit card. So we all sort of need randomness, for example, in cryptography. To be able to... Cryptography depends on not being able to work out what your sort of key that's locked you're. credit card is. Do you want to take this on, Tim Giles?

Well, another point is that it's not just random numbers that we need or we can use random numbers in order to produce random other things. So going back to electrical engineering, if you've got some very complicated electrical circuit, one of the properties you want of that

circuit often is a sort of robustness. You want if one of the components fails, or even if half a dozen of the components fail, you don't want the whole circuit to become completely disconnected. So you want to devise some sort of network of components and wires in such a way that if a few of the components fail, the network will remain connected. That turns out to be a hard thing to design if you just sit down and try

to design it. If you choose your connections randomly, it turns out that almost miraculously, it works incredibly well. I think it's wonderful this tension between, you know, using pure mathematics, as you said Melbourne, which is something incredibly deterministic to produce something which has this quality of randomness, this pseudo-randomness. It's incredibly deterministic, but we can use it to create randomness. Colva. One final incredibly practical application of random numbers is they're used by the Met Office for weather forecasting.

So weather, as we've heard about, is chaotic. We can't say exactly what's going to happen, but the Met Office run an awful lot of simulations with very minor fluctuations in the input data so that they can say there's a 60% chance of floods tomorrow in such and such an area.

Yes, but they're still, the most minor alterations in the tiny, like the moving And I think that comes back to your dice Because your dice is essentially chaotic You cannot know the exact setup of that dice And so that's why that sequence of numbers You toss before the thing

It has that quality of randomness to it Well thank you very much Colva Roney Dougal Marcus Isotoy And Tim Giles Next week we'll be talking about The Mexican Revolution of 1910 Enter Zapatte Thank you for listening

If you've enjoyed this Radio 4 podcast why not try others, such as Thinking Aloud, where Laurie Taylor discusses the latest social science research. To find out more, visit BBC.co.com.uk forward slash Radio 4.