>> DFB: San Francisco, weather. >> Brady: Why don't you draw us the Golden Gate bridge?
>> DFB: [laughs] I ccan't draw! >> Brady: C'mon give us the Golden Gate bridge! >> DFB: Oh Lord! I'm running out of space look!
For the sake of argument we'll say there's only four possibilities
It's sunny, cloudy, rainy or it's foggy. And all you've got to say is: "OK what's the
probability of these are they equally probable or is one more likely than the
other?" And for the sake of argument let's say that in San Francisco - you do get all
of these - it's amazing - every single one in about an equal proportion, roughly.
So let's say it's a quarter, and a quarter, and a quarter, and a quarter. And all
those of you who have been through high school statistics know, if these are
probabilities [you] add them all together.
It's got to add up to 1. 1 is certainty, hundred percent. So four quarters is 1.
Let's say therefore that
here am I in San Francisco and here is my friend in Reno. >> Brady: In Reno ! >> DFB: And we have got
an electronic buzzer.
You know one of those old-fashioned things that you see in wartime movies
where you tap out Morse code, or whatever. But this is going to be very, very simple.
At an agreed time in the day
I've got to transmit the state of the weather in San Francisco, from my weather
station to the guy in Reno as compactly as possible. Because this is the early days
of electronic transmission and each bit costs me a thousand dollars to send, OK [exaggeration!]
OK, so what's the minimum number of bits
I need, because when I'm going to encode it in 0s and 1s.
Well, you look at this. There's four states there, all
equally probable. How about something like this 00 for Sunny, 01 for Cloudy, 10
for Rainy and 11 for Foggy. Four completely separate, distinguishable, possibilities, Right?
So, if its sunny the guy here just goes
tap, tap, two short dots for two zeros and the guy at Reno knows, for only two thousand
dollars, that it's sunny at the weather station in San Francisco.
Can you do any better than that?
No. You can't. You've got four equally probable things.
There's no way in the world that, losslessly, you can get better than that.
Yeah?! However ... >> Brady: It sounds very defeatist!
>> DFB: Well, it is! But you asked, is there a limit? And there is! Right? So long as you want it
lossless there is a limit and you can't get below it. It's the entropy limit and
those who've done chemistry and physics will know you can't beat it.
All right? However if only things were more predictable -
this is not quite true but it's virtually true - Sahara Desert.
>> Brady: I'm not going to ask you draw a picture for that because there's no ....
>> DFB: Probability! The probability here is one
- it is always sunny in the Sahara Desert.
So if I've got my Sahara Desert
keypad here and have got a transatlantic line to Reno, Nevada, where [let's say] they gather all
of this data,
How many bits of information do I need to send to get that message
to Reno? The answer is, if the weather never changes,
you don't need to send any information at all! It's always sunny!
Why ask? But if you want to be absolutely sure let's just say: "Send a zero to be sure".
>> Brady: OK, so send a zero if it's sunny?
>> DFB: Send a zero if it's sunny. You didn't really need to because it always is. That's cost you
... well probably cost you at least a thousand dollars to send it again but, yeah, one bit.
One bit would be more than ample. Actually the information theory answer is zero
bits, because if it's certain you don't need to tell anybody!
This will kill you ... you can edit this out. But you do the Maths ones don't you ?
>> Brady: We edit nothing out here! Yeah! I do the Maths ones.
I do the Maths ones! >> DFB: OK, so what we remember, of course, is
that 1/4 is the same as 1 over 2 squared, which is the same as 2 to the
power minus 2. Number of bits you need equals probability of it happening.
times log of the probability of it happening [with a minus sign].
If you take log to the base 2, of 2 to the minus 2, the answer is -2. Turn it positive: 2.
What the log of that probability is telling you is the number of bits you
need [at the] minimum. >> Brady: So there is, for any piece of information,
there's a minimum number of bits? >> DFB: So if one of these was an 1/8th
how many bits would you need to encode it all? >> Brady: Why don't you tell me ?!
>> DFB: Well I ... y'know ... If if there were eight things, right
then what you could say is that 2 to the power minus 3 is 1/8, so it will be a
3-bit code. >> Brady: Are you auditioning for a place on "Numberphile" here aren't you, I can tell!
>> DFB: I don't know! >> Brady: that's what happened back there, yeah. We've got this minimum for this piece of information.
Is that only on the playing field of the system we use at the moment -
these zeros and ones? I mean is it possible if we use - came up with - a new
way of storing and transmitting information it would be a game changer?
Or is zeros and ones, you know ...
>> DFB: No, if we ... leaving aside weird quantum effects - who knows what might come out of
that - as of the real world as we have it,
this is just .... it's a showstopper. You can't get beyond
this entropy limit. When I was taught about entropy - this irreversible sort of
minimum that you can get - when you do it from the point of view of physics and
chemistry they love saying things like this, and it sort of works. You've got
a diamond close to absolute zero,
yeah, that is a very low entropy system. Low entropy means it is ultra-predictable.
There's the crystal it's vibrating but only just. You know where it is - it's not moving.
High entropy is when the probabilities are smeared out you don't know where it is.
So by the time you get a gas, with millions of molecules zooming here there and everywhere
that's a very mixed, random, high entropy system
Now you can see how I take the view that it's a lot easier, instead of starting
with 10 ^ 23 molecules in a gas, start with four weather states in San
Francisco and you get the idea. And then you can transfer it to physics and
chemistry and say Oh! well, in physics and chemistry unfortunately, we've got to use natural logs and
you've got to take a summation - not over four states, right, but over 10 ^ 24.
Because, you see, here ... >> Brady: I definitely can't figure that one out!
>> DFB: No here you can say average number of bits I need is the sum over all these p log p's
So it's a quarter times two bits, for that one, plus a quarter times two bits
plus a quarter times two bits plus a quarter times two bits - wow isn't this amazing!
The answer is that the average message length is two bits.
But if those were skewed a bit you can kind of instinctely see what you
would do. If one of these became a half
you'd want to give it a short code? Right? >> Brady: Because if it was
sunny more often
I would say: "Well let's make our code for sunny short and some obscure
weather like a tornado, I'll make it ....
>> DFB: Exactly! So like it was a half your theory here would say,
that's 2 to the minus 1, hey, let's try a 1-bit code there and let's use 2-bit
codes for the others.
So you could end up with something - if it's like Los Angeles is reputed to be -
that's Smoggy and that's Sunny, that's Rain,
that's Cloud. What you could then start saying: "Oh well, how about devoting the
code 0 to denoting smoggy, yeah? >> Brady: Because its more common ? >> DFB: Because its more common.
Anybody who's watched World War II movies and people tapping out Morse
codes and a lot of people i'm sure we'll know that the most common letter, 'e', has
got the shortest code?
It's a single dot in Morse code, whereas 'z' is quite long and so on.
So it applies, y'know,
all the way through this. So what you could say, therefore, is: "If I'm
going to start with 0 for Smoggy
then I'd better not confuse matters by starting a longer code for any of these
with 0". Right? Let's start them all with 1.
So let's say something like 10,
Sunny, but then you say: "Hmm! I'd better not start either of these with 10, otherwise
things will get confused". So let's start them with 11
Yeah but the trouble is, if I use 11, I'm then running out of what I can use for
Cloud. Can you see you'd have to say 110 and 111?k Because you've got to be able to
uniquely decode it. And if you're not very careful you will end up with
something that can't be uniquely unscrambled. Suppose to save telephone costs
you just sent a week's weather, all at once.
Seven things, one after another
How can you uniquely unscramble it into being these .... yeah! it happens with
telephone numbers!
It happens to me at home. This, and my telephone number, has to have the "prefix property".
I live in a village where my telephone number is a five-digit code.
Unfortunately some people in the village have got six-digit codes.
Yes, telephone codes have the prefix property. They connect the moment they've
been unambiguously satisfied.
So, if you have a legal five-digit telephone code
it cannot be the prefix of a longer code, because the telephone exchange goes "bang!"
and connects you the moment you give it something sensible.
Yeah, the trouble then is that the Ocado delivery system doesn't
understand this and thinks everybody's got to have six digits. So, do you know what I do?
>> Brady: So when you're ordering groceries you deliberately put a wrong number in ?!
>> DFB: Yes, at the very end
>> Brady: This might be a good tip for new players. If smeone won't accept your
phone number just add any digits at the end >> DFB: Just add any digits to the end.
>> Brady: If a weather condition was more common, like sunny weather in California,
you give that a shorter code to save information?
Did the people that invented the JPEG format, or do other people that are doing
compression, use probabilities in the same way?
>> DFB: Oh yes! >> Brady: So do they know that blue is more common in pictures, or how do they use them?
>> DFB: No, it doesn't quite come down to that. It's more - in the jJPEG standard that it's more,
as it were, spatially aware as well as colour aware in terms of what it's doing.
But, yeah, in one respect or another probabilities is at the root of all of
this and, like I say, that's particularly true if you want lossless compression
because you run up against
unstoppable entropy limits about how far you can compress and not lose anything
in in the compression.
>> Brady: Well I'm glad it's not my job to compress this video!