Why Information Theory is Important - Computerphile

Key Takeaways

we're going to be talking about information theory and a specific concept called shannon entropy named after claude shannon he was a great computer scientist right there at the beginning of the field but today we're going to talk about his most important contribution which is information theory so a lot of concepts in computer science are directly derived from this more general theoretic concept things like compression zip files network error correction codes or error detection posts things like that are all directly related to information theory now the simplest experiment that you can do that involves probability is flipping a coin so i have a penny here and i'm going to flip it and i'm going to ask you to make a prediction is it going to be heads or tails people say tails never fails but i'm going for heads just for two heads all right i'm gonna have a quick peek here now if i told you it was heads how surprised would you be a bit just one bit one bit one bit that's that's exactly right one bit and you are now one bit surprised it is heads um so what if instead i'm going to flip two coins right and i'm going to flip them in order to let them land here but i'll ask you to make a prediction um the coin on the left will be heads or tails i'll go heads for that one head and the one on the right let's be crazy and say tails tails okay coin one and coin two oh is that our tails i can't actually wear that so they're both tails oh how surprised would you have been if your prediction was completely right a bit a bit more that's right one bit more um so obviously there's a relationship between coin flips and bits i kind of gave it away but let's talk a little bit about the mathematics behind it so obviously the larger a probability is the less surprised you are by the outcome and the smaller a probability is the more surprised you would be if the outcome happens um and yeah you see that on lottery winners faces you see that on well it's a good thing you brought it up so we'll talk about the lottery in one minute so let's come up with a sort of reasonable formula to to express the amount of surprise that you have with a certain outcome so the symbol that is used for that is the capital letter i the i stands for information but we'll talk about why that is later for now it means surprisal and the surprisal of some event e is equal to the logarithm of one over the probability that e happens so why do we take one over the probability of e well because we're saying the less likely it is the more surprised we are right so a one in a million thing surprises us quite a bit more than a one in two thing so whatever is below the divisor is what we're interested in so that's why we're taking the inverse why do we take the logarithm so the logarithm is a function which has diminishing returns so if we're looking at the probability as an odds thing so one in two is an odd of two one in ten is odds of ten right the smaller the probability gets the larger the odds get but the idea is that if you double the odds you only increase the logarithm by one so you want this diminishing return of surprisal and that's why we use the logarithm so every time you halve the probability you only increase the amount you're surprised by by literally a bit otherwise if you got to a million you would be yeah off the scale right it would go off the scale way too quickly so that's why we're taking the logarithm um so one in a million and one in two million are sort of comparable in the amount that it would surprise us so this formula makes sense for coin flips and what we can do of course is we can plug in the numbers so let's do exactly that so the event here that we have was um heads if i'm not mistaken for a single coin flip so we're talking about the information content of a single coin flip being heads which is equal to the logarithm of one over the probability now what is the probability the probability is a half and this in other words is just log of two in computer science contrary to mathematics when we write down the logarithm we usually mean the logarithm base two so you can put a little two here but when we omit it in computer science we mean two if we want to have the natural logarithm we would write something else a base 10 logarithm we would put a little 10 there if there's nothing there log 2. so the log 2 of 2 is of course 1 and the quantity the unit is bit so it's one bit of surprisal and similarly if we plug in the double coin flip your prediction if i'm not mistaken was heads and tails yeah and the probability of that being right is of course one in four so we get a logarithm of 1 over 0.25 which is of course log four which is two bits so you're one bit surprised versus two bits surprised this works nicely for coin flips because all outcomes are sort of equally likely but what happens in the case that not all events are equally likely so you have an unbiased coin they're equally likely you have a biased coin they're different let's take an extreme example of um of a biased event winning the lottery right there's a tiny tiny tiny tiny chance that you win the jackpot and there is a very big chance that you don't win the jetpod keep it simple let's say that there's a one in billion chance you win the jackpot and when i say a billion i of course mean two to the power 30 which is roughly a billion as most computer scientists will know so we have two events you either win the lottery or you don't now if you win the lottery you'd be very very surprised right so let's plug that in i'd be extremely surprised since i've not bought a ticket in i don't know how long so i don't think it changes the probability that much does it so let's call the event winning w so that is log 1 over 1 over 2 to the power 30 so 2 to the power minus 30 and this is of course equal to log 2 to the power 30 which is 30 bits so if it happens you'd be extremely surprised but if it doesn't happen you're not surprised at all right so the probability of not winning so losing is log 1 over and then we get well a tiny number let's just write it as 1 minus 2 to the power minus 30 and that is roughly zero point zero zero zero zero zero zero zero zero zero 1 3 4 bits so i think it's safe to say you wouldn't be surprised even a single bit so what does this really mean what is more surprising on average flipping a coin where both events are not very surprising or the lottery where we have one very surprising result and one completely unsurprising result and this is the core idea of information theory so this is how a notion called entropy is defined it uses the letter h and what you do is you take the event so let's say p for postcode lottery because we've used the l for losing pretty much the same thing to be honest we take the probability of the event which is a tiny probability and that's the probability that you win and if you win you're 30 bit surprised if you lose which happens the rest of the time so that is 1 minus 1 over 2 to the power 13 you're basically not surprised at all so this tiny quantity in bits and this gives you the expected amount of surprisal and as you can imagine this formula basically simplifies to a tiny number right because this number will be tiny this number will be tiny the sum of two tiny numbers is a tiny number so actually the most surprised we can get with a event that only has two outcomes is actually flipping a coin which is one bit surprisal as soon as you introduce a bias the amount of surprisal goes down let's link this back to computer science the notion of information theory right so what i'm claiming is that what we're computing here is what information is um if i want to tell you the result of a coin flip what is the best way i can do it uh zero one zero or one so we need one bit to give you the result of a coin flip if i want to give you the outcome of a single lottery i'm still going to have to use one bit a zero for losing and a one for winning however it says here that we need fewer than one bits what does that mean well let's say that you play the lottery for a whole year and i want to communicate to you the results over the whole year what i could do is i agree with you that if i send you zero for the whole year it means you've lost every single time and if you did win one of them in the unlikely event that that happens i'll do a one followed by an integer that is the first time you won the lottery that year and then repeating that coding in case that there's another win even less likely right so there's a tiny tiny chance that we'll use more than one bit and a very big chance that we use exactly one bit so on average we're going to use about 1 in 365 bits per day now that is still a bigger number than this but what this is saying is that if you do this experiment infinitely often and you come up with the smartest best scheme that you can possibly come up with you're still going to have to use at least this many bids per lottery you can never do better than this on average is what it's saying this is like the absolute optimized to its absolute kind of yeah exactly and you can imagine that this is something that computer scientists are very interested in because if you want to compress a file and you know how much entropy there is in that type of file you know you cannot on average do better than a certain amount you can stop searching once you found it same thing with error correction codes if you know the throughput in bits of a channel so an electrical wire you know that there's no smart way of putting more information through it than whatever that number is and that's why information theory is so important for computer science 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 gap it's easier to find what the factorization is and then once you've factored it you can just do these steps to completely calculate the private key