Runtime Arguments
Conversations about technology between two friends who disagree on plenty, and agree on plenty more.
Runtime Arguments
38: The Claude Shannon Episode: Surprise, Entropy, and Bits
Use Left/Right to seek, Home/End to jump to start or end. Hold shift to jump forward or backward.
What is Information Theory?
- Information is not meaning
- Likely things need very few bits to communicate, maybe less than 1! Unlikely things need more bits.
- Entropy is in the eye of the beholder. It’s what you already know that informs your ability to extract meaning from a message. To one person, it’s just noise; to one who holds the encryption key, there may be way less information’s, but m much more valuable meaning.
- This is the plumbing behind everything you rely on: communication, storage, encryption, compression, error correction.
Come join us for lunch! Every Saturday, we and several of our friends meet for lunch at 11am at Biwako Sushi in Saline Twp, MI. It's just south of Ann Arbor. If you are in the area, we'd love to have you join us.
Hosts:
Jim McQuillan can be reached at jam@RuntimeArguments.fm
Wolf can be reached at wolf@RuntimeArguments.fm
Follow us on Mastodon: @RuntimeArguments@hachyderm.io
If you have feedback for us, please send it to feedback@RuntimeArguments.fm
Check out our webpage at http://RuntimeArguments.fm
Theme music:
Dawn by nuer self, from the album Digital Sky
Welcome to another episode of Runtime Arguments, the podcast where we talk about all kinds of neat tech stuff and… I don't know what else. Just… we do this all the time. Um, my name is Jim McQuillan, and with me today, as always, is my friend Wolf. Say hello, Wolf.
Wolf:Hey everybody and hey Jim. I'm so glad to be here with you, especially after a long day of work.
Jim McQuillan:At the end of a long week, right?
Wolf:At the end of a long week? At the start of a new month? After a long month?
Jim McQuillan:Yeah, yeah. Oh gosh, yeah, the the beginning of the 4th quarter. This is when the pedal hits the metal and we get stuff done, right? So today we're gonna be talking about Claude Shannon. The name of the episode is, I think it's gonna say this, the Claude Shannon episode, surprise. entropy and bits, and Wolf is gonna… Wolf is gonna delight us, uh, with everything to do with that, and I'm really looking forward to this one. Uh, before we get into that, though, let's, um… let's… let's cover the… the overhead that we do every time we do one of these things. This is our 39th episode, episode number 38. Um… Feedback. We love feedback. We got a little bit this time. We want feedback every episode. So please, if you have thoughts, have ideas, if we said something incorrect, if you just like what we're doing, send us some feedback. There's several channels to do that. You can find them in the show notes at the bottom of this episode in your player. You can go to our website. We'll remind you all this stuff at the end. Some of the feedback we got, the last episode we did was on the Unix year. 2038 problem. That was a fun episode, and I failed to mention that the whole idea for that episode came to us from our good friend Ron. He gave me that idea, gosh, probably nine months ago, and it turned out to be a lot of fun. We talked about not only the year 238 problem, but a little bit about Y2K and several other similar problems. issues, design issues, bugs, whatever you want to call it. Um, we also got some feedback from Marlin. Marlin is our genius friend that works at Meta. Um, whatever he…
Wolf:I'm jealous every time you say that.
Jim McQuillan:Yeah. Well… That's the, uh, that's the adjective that I think of when I think of Marlon. Um, he, uh, when he gives me feedback, first of all, I'm always nervous when he listens to the episode, because I know he's gonna, he's gonna find things, because he works at a whole different level than we do. And, uh, and he wanted to point out that, uh, while I said during the episode. that, um, uh… We don't worry so much about things like block sizes on disk and sector sizes, where I used to have to worry about it all the time, back when I was sort of coming up in the mid '80s. Boy, we had to be very careful about how we laid data out on disk. And I don't worry about that anymore. And that's what I said. But Marlon was very quick to point out that yes, that's still very, very important. The work he does at Meta, they're focusing on that all the time. And it's very important to make sure your data aligns on blocks. Now, I think the point that I was trying to make was, I don't have to worry about it anymore. I use a database. I don't have any control over that anyway. But the people that are designing the databases, those guys at Postgres and MySQL and all the others, they… take sector sizes and block sizes very, very seriously. Uh, you know, they're trying to…
Wolf:There is always somebody right on the medal.
Jim McQuillan:They're trying to be as if… Yeah, they're working with the metal. They wanna be as efficient as they can because if they're not. careful, they end up wasting disk space, wasting time, all those things. So yeah, block sizes are really important. And then you get into things like memory and how you lay out your structures and stuff. And you know, I work in a higher level language. I don't have to worry about structure layout, but the guys that are working in the lower level stuff, they focus on that stuff all the time.
Wolf:And the important thing is, any time, space. Storage speed that they waste? You waste.
Jim McQuillan:Yes.
Wolf:Everything they do is the limits of what you can do.
Jim McQuillan:Yeah, you can't do any better than they can do it.
Wolf:Right.
Jim McQuillan:It's some great stuff. So yeah, if you had feedback, please send it to us. We love hearing from people. That's how we know you're out there listening. You know, we get the statistics, and they always look good, the download stats and stuff, but knowing that you're actually listening. That helps us out quite a bit. So Wolf, how was your week?
Wolf:Uh, oh, there were lots of ups and downs. Uh, first of all, everybody knows, who's been listening, that I have been studying and practicing and preparing and learning for WEEKS to get ready for this big. match the Michigan sectionals, uh, that I shot at. And, um… my number one goal was to be safe, and my number two goal was not to DQ, and then after that, there was stuff about, you know, improving. And I did not even make it to number two. I DQ'd. And it was early. It was…
Jim McQuillan:DQ'd, you disqualified.
Wolf:I disqualified. And when you are at a USPSA match, and you disqualify, when you DQ, here's what happens. Um, you IMMEDIATELY stop shooting. Uh, you don't get to shoot anymore, at all, that day. There's no more. Uh, you pack up, and if you're a super good sport, uh, you stay. with no firearms, and you walk the stage with everybody else, and paste up holes, um, and, you know, do your share, because it's a volunteer sport. Um… And I'm, uh, ashamed to say that I did not even stay to paste, because I was exhausted, it was 2 hours from home, I hadn't had any… anyway. Uh, the important thing is, I did an unsafe thing, and I didn't. even know I was doing it. The reason it happened is because W, Wolf, uh, I'm, I'm last, usually, on the list, or close to last. And I spent most of the stage sitting next to an expert. And I had a plan, and my plan was safe. I'd gone through it, I'd gone over it, but the expert said, oh yeah, you don't want to do that. Uh, because that just wastes time. What you want to do is don't put anything back on your belt. This was an unloaded start. Just shh. Shoot some stuff, and then grab the other magazine and reload as you go left. His plan was better. It was an improvement over mine. Except… I never stopped to consider it. Is this a thing I can do? I had never practiced this reloading from right to left. I'm a right-handed shooter. It's unsafe if you haven't practiced it, because you turn in a way that makes you point your gun. towards human beings. Uh, so I started my reload, I'm like… Six seconds into the stage. Um, I'm starting to run to the left, and as loud as you can imagine, uh, one of the ROs shouts. Stop. Um… That's the word. When they say that, that's the end of your day. And you know, like they're…
Jim McQuillan:And an RO is what?
Wolf:An RO is a range officer. I'm actually a certified RO myself, but every stage there's three. There's a guy running the timer, there's a guy who's taking the score, and there's another guy who's standing in a third position just to see what's going on. And, um… I immediately froze in place, like freeze tag, and waited for the first RO to come up and give me instructions, which involved. unload and show clear, and if clear, holster, uh, hammer down and holster. I did those things. And then the RO who stopped me said, yeah, I was looking right down your barrel. And I had no idea. Um… I did this bad thing, it was wrong, it was unsafe, and he said, do you want to contest it? And I said, absolutely not! I'm… so happy that you stopped me because now I know better. Next time I'm going to come back and I'm not going to do this. If somehow I had gotten away with it, I might have done it again. Way more important to me. to be safe than it was to keep shooting for the rest of the day. And then he was very kind to me. He said this. He said, uh, you should know, it wasn't egregious. Um, so I felt good about that. But yeah, I did a bad thing, and the bad thing wasn't me pointing in the wrong direction, it was not thinking about advice. So…
Jim McQuillan:Sure.
Wolf:That was unfortunate. A lot of practice wasted.
Jim McQuillan:Well, so the bottom… the bottom line, did you learn something?
Wolf:I absolutely did.
Jim McQuillan:That it wasn't a waste.
Wolf:And I'm, I'm… Super glad about that. Okay, number two.
Jim McQuillan:Yeah.
Wolf:Um, I have been informed by many people over many years, uh, that the thing that sucks about talking to me, or at least asking me a question. is that I don't answer fast enough. And so I have a plan to answer faster. It's sort of based on the Equalizer movies. Um, okay. I'm going to start my stopwatch. And if I get to, like, 20 seconds or something, and I haven't told you the answer yet, it's time to reconsider my direction.
Jim McQuillan:To be clear, it's not that he's slow at answering. He starts the answer very quickly. It's just that there's an awful lot of words that come out of his mouth. Before he gets to the answer that I want to hear, so.
Wolf:Yeah.
Jim McQuillan:He's, uh, he's… Wolf is taking steps to, uh, to improve, and man, I appreciate that.
Wolf:Uh, yeah. Yeah, okay. Uh, number three is, uh, I published my personal ethics, at least. I started them. They're up there on GitHub. My GitHub account is github.com slash wolf. And, uh, that repo is called Ethics. And, um… It's sort of about if you see me say something or do something or why did I do that? Why did I say that? Maybe these ethics will tell you. They're not… Uh, perfect yet? I'm working towards it. Umm. 1Password. They contributed money towards fascism by supporting O'Markey and DHH, who I don't think describes himself as a Nazi, but a lot of people do, and I'm kind of. Indiana Jones in this situation. I hate these guys. So… Uh, the fact that 1Password did not… Take it back. They didn't rescind their funding. In fact, they kind of doubled down. I love 1Password, it might be my favorite piece of software, but… It does not agree with my values. And therefore, Bitwarden, here I come. And finally… I got some really great email from a young software engineer. Uh, by the name of Rama. Uh, I… Rama did not mention ever having heard our podcast. What he said was, he was on YouTube and saw, like, a… 8 or 12 second clip of me talking. Uh… having to do with General Magic. Um, this was an interview that happened at General Magic. Most of the clip was about Megan Smith, who was a hardware person, brilliant, ended up, uh, like. an important person in Washington, D.C, I think, in the Obama administration. She… I have to say, of the people at General Magic. There were so many who were so wonderful to work with. But Rama said nice things and he found value in some of the things I had said. I pointed him at our podcast. Uh, but, uh, yeah. he really gave me the feels. He said things that made me feel good about the work that I've done and we've done, and I really liked that. And that brings me around to the very final thing I want to say.
Jim McQuillan:That's nice.
Wolf:Which is, um… you mentioned Ron, we've talked about, uh, Marlon, uh, we have, uh, Jim Peterson, uh, our friend, uh, Robbie J. Dave, so many people.
Jim McQuillan:Now we got Dave, we got Jay.
Wolf:And I feel like I'm in trouble. Oh. When people give their Oscar speeches… And they say this thing, they say. you know, it is an honor just to be mentioned in the same breath as these people, and what they mean are the other nominees for that particular Oscar. I am 100% honored. just to be considered in the same breath as this group of people. Every one of this group of friends, they're all smart, they're all driven, they're all curious, they're all inventive. They're all doing fantastic stuff, and to be put in the same group with them? It's a privilege.
Jim McQuillan:And this group, what he's referring to is, you know, this whole podcast was born out of the fact that Wilf and I would have lunch every Saturday at a sushi place down just south of Ann Arbor. And we did this for years, and then we started inviting people, and they started showing up. And every week now, um, it's, uh, I think last week there was 5 of us, sometimes there's 8, sometimes it's just 2 of us. But we're there pretty much every Saturday, uh, 11 o'clock in a… in a place in Saline, Michigan, which is just south of Ann Arbor if you're in the area. Uh, the place is called Biwako. It's a… what do you call it? A sushi fusion…
Wolf:It's Korean-Japanese fusion and it's named Miwako Sushi and every single person there is nice.
Jim McQuillan:I don't know what your call is. Yes. Yes, so, this is our open invitation. Uh, if you are within driving distance, and you're available on a Saturday at 11 o'clock in the morning, come see us. Uh, just walk in, and uh, it'll be the table with a bunch of guys probably talking loudly, and uh… In fact, at any given moment, it's probably wolf talking, but come on in.
Wolf:That's sort of the sad part. I feel bad about that.
Jim McQuillan:We would love to see you. It's not sad. You've always got interesting stuff to talk about. So yeah, come.
Wolf:You know, a cool thing is about to happen. One of our good friends, Ron, and Ron's wife, Lynn. Umm. they are going to go with me to a Stop the Bleed class, uh, to be able to handle.
Jim McQuillan:Explain what that is.
Wolf:Stop the Bleed is, uh, it's a whole association, and they give these free classes everywhere. Um…
Jim McQuillan:Oh, what?
Wolf:where you are taught.
Jim McQuillan:I thought you were talking about stop the greed. Okay.
Wolf:I've never heard of that. Certainly not these days.
Jim McQuillan:It's something we all have to make happen in early November.
Wolf:Yah. Yeah, these are classes, um, that they give for free all over the place, and the idea is to teach the people who come.
Jim McQuillan:Yes.
Wolf:Umm. How to keep you alive. For the time it takes for emergency, uh, medical personnel to get there. Um, you know, something bad just happened. You fell on a piece of rebar, and it went through you. Or you got a terrible slash in your… whatever, it doesn't matter. Whatever bad thing happened. Can I keep you alive long enough for the ambulance to get here? Maybe I can do a little better than that. Maybe that's all I can do, but the steps to do to make somebody stay alive, I think this is vital, and it's a thing. I think everybody should know. Um… You ought to be able to keep somebody alive for 15 minutes.
Jim McQuillan:Sure.
Wolf:Uh, and he and his wife are gonna meet me there, and we're gonna do it together. I'm super excited.
Jim McQuillan:Sure.
Wolf:Umm. So that that's my week.
Jim McQuillan:That's good, that's that's a lot.
Wolf:surgery coming up, they're gonna operate on my wrist, I don't want that. But I do want it, but I… don't want it.
Jim McQuillan:Yeah, yeah. Now, this is not about last week. This is about next week. I'm going to Rochester, New York to deploy that software I've been working on since June. I mentioned it a few times. It's this big monster of a project. A lot of TypeScript, Node, database stuff. I'm gonna talk a lot more about it in our next episode after I've deployed it, after I have a story to tell, because it's a real fun project and I've been kind of vague on the details. But we'll talk about it in our next episode. Why don't we get on to the meat? Well. Are you ready?
Wolf:I am. Um… first, I want to remind everybody of my little pantheon of heroes, um, and I'm gonna give them in order. As far as I'm concerned, Richard Feynman, uh, that guy. rocks the world. Maybe the best teacher who ever lived, he discovered amazing things, he was curious, he learns… If I could go back in time and meet one person and have dinner with them and just ask questions non-stop. It would be him. Number two on my list is Claude Shannon. He's a contemporary. He did die in the 2000s, I think, if I've got that right. He is the father of what he called communication theory. but what we today call information theory. It's the core of everything we know. It's how we compress, it's how we encrypt, it's how we transmit, especially over noisy channels, that's a thing. It's how AI works underneath. Um, it's how you, uh, talk to your wife, believe it or not. It's everything. Information theory. Um, third on my list is Kurt Kernel, who, at 21 years old. Proved that you can't prove everything. Godel's incompleteness theorem. astounding. And finally, the latest addition to my little pantheon, Pierre Simon Laplace. who did the heavy lifting behind Bayes' theorem. Uh, these four guys. Today is the Claude Shannon episode. We're gonna talk about communication, and I am gonna promise you up front, no math. Umm. I'm my goal is I want to a. tell you the stuff that's the most interesting about it, and B not say any of the stuff that's boring. Uh, and if I can do that, maybe, uh, you'll come out with something new and interesting to you. So that's my plan. Does that sound like a reasonable plan to you, Jim?
Jim McQuillan:That is a great plan. I'm looking forward to this. I wanna learn about information.
Wolf:So I'm going to start with some. Curious. concepts, and then I'll dive into the real meat. Um… One thing that I'm not going to explain right this minute. But I am going to say to pique your interest. is… vet. Information? And meaning. are almost unrelated. Uh, if you turn the radio to a station that has only static. Guess what? That is a lot of information. It's surprise. It's brand new to you. Uhm… But also, it… Almost certainly has zero meaning. Um… And… How much information and meaning are in something? Uh, is very strongly related to who's watching. So, I've got two throwaway phrases. The sun rose today. does not contain very much information, or surprise, or noise, or anything. In fact. Is there a time you could have… NOT said that? It's been true every day so far. So it's not news. Umm.
Jim McQuillan:But that doesn't mean it's going to be true tomorrow.
Wolf:But! That is correct. So it's not 100% certain. That's something important. Here's another interesting statement. It snowed in Miami. Now that's very different than the first statement, because this one contains a lot of surprise. And the soul of information theory? is that a SUPER CERTAIN. Very high probability statement. Like that first one, the sun rose today? You can express in a very tiny number of bits. Maybe less than one. And a very surprising statement, like that second one. Takes a lot of bits to say. So… of everything in information theory, which for sure every one of you deals with in one way or another sooner or later. If I can help in any way at all, it's by… Teaching you the exact meaning and relationship between a couple of words you already know. But maybe don't know what they mean. Uh, and the first and most important one is the word surprise. Um, surprise is the thing we actually care about. That first statement about, uh, the sun rose today? That doesn't have very much surprise. And the second statement… Does. Surprise is a thing, uh, that we actually put numbers on, but I'm not gonna talk about the number. But we usually talk about it. per message. So, if you're listening to the Weather Channel. A message from the Weather Channel is "it snowed in Miami" or "the sun rose today". Each one of those is one message and we talk about the surprise in that message. There's another word that you've heard all the time and you can never, I know I can never, remember which direction this number goes and how it's related to surprise and that number is. That name is entropy. What is entropy? Well, entropy is exactly like surprise. Except, it's not surprise about… It snowed in Miami. It's surprise about everything you ever hear on the Weather Channel. Either, um, it's a high or low entropy source. The Weather Channel, um. has entropy that is like you calculating the average surprise across all the messages that you get. If it's low entropy, it's a TV station you don't want to listen to because it's not really telling you anything. If it's high entropy. and meaningful, uh, you do want to listen, because it's interesting to learn that it snowed in Miami. Umm. As long as you can extract meaning. News is sort of the everyday English word for the same idea. Dog bites man. Uh, not very surprising. Happens a lot. Man Bites Dog. Very surprising. One of those has a lot of news in it. So, news and surprise are almost the same thing. noise. Here's a brand new word, and super important for later when we start talking about noisy channels. Noise is the word that resolves this contradiction that you had in your mind. Um, noise has real entropy. Surprise! When you're listening to static, every new piece of static is genuinely surprising to you. You didn't know whether it was gonna be a one or a zero, so it's a surprise. But the fact that it's noise… Implies you aren't able to extract meaning. And, uh, finally.
Jim McQuillan:Or you're not interested in the meaning?
Wolf:Uh, actually, no. You can't extract the meaning.
Jim McQuillan:Okay.
Wolf:Like, interest doesn't play a role in this system. But being able to extract the meaning does, uh, because it turns out entropy is in the eye of the beholder. I'll give you an example.
Jim McQuillan:Okay.
Wolf:An encrypted message. You and me are both looking at this message in transit, so what we see is encrypted.
Jim McQuillan:Mmhm.
Wolf:I am the intended recipient. I have the key to this message. You are uninvolved in the transaction. You don't have the key. For you, looking at this message, the entropy is high! It's noise! You can't even tell what it is, because you don't have the key. I do have the key. So it's much lower entropy to me than it looks like to you. And the difference isn't interest. It can you extract the meaning?
Jim McQuillan:Okay, I…
Wolf:I have the key that lets me extract the meaning.
Jim McQuillan:Okay, you and I go to a party. There's 30 people at this party. There's 6 different conversations going on. Each one of those conversations, we can understand what they're talking about. We can find meaning in what they're talking about. But we don't care about 5 of those conversations. Those conversations are just noise to us.
Wolf:Um, I hear your words, I hear what you're saying, and the words you're saying are true in English. Um, we're basically ignoring them because they don't contain anything we care about.
Jim McQuillan:Right.
Wolf:And then you gave that the word noise. And that's a perfectly valid way to use the word noise. But it's not the way I'm using the word noise.
Jim McQuillan:That's not the noise we're talking about.
Wolf:Exactly.
Jim McQuillan:These are not the noise, yeah.
Wolf:Uh, but for sure, the thing you said is true, uh, but it's not related to this stuff.
Jim McQuillan:Right. These are not the noise we're looking for.
Wolf:Um… Right. So, those five words… surprise, entropy, news, noise, information… Just knowing which direction those things go, and what they mean, um… that more entropy means more surprise, except that entropy is measured across the entire source, the whole Weather Channel. And surprise is like this message and that information.
Jim McQuillan:Okay.
Wolf:Is a thing very strongly related to news? And noise has entropy, has surprise. But isn't necessarily information. That's the… that set of 5 words, that's the most valuable thing I can tell you.
Jim McQuillan:Okay.
Wolf:on. Does that all make sense?
Jim McQuillan:Yeah. Yeah, let's keep going.
Wolf:All right. In the old days, um… Before we invented the special magic. Um, we did stuff. Uh, this whole… another whole way to talk about what… Shannon called communication theory is you've got. Symbols, input symbols, your message, whatever it is. And you're going to transform it in some way to send it through a channel. And it's gonna come out the other side in this other set of symbols. I'll give you some examples. Morse code.
Jim McQuillan:Okay.
Wolf:Huffman coding. Umm. Both of these are really interesting. For a reason. Um… The oldest thing in the world with this communication stuff was when we used substitution ciphers. So you would have 7 symbols that you wanted to communicate to someone? You would apply your transformation cipher. And you'd send them seven brand new symbols. The interesting thing about, um, simple substitution ciphers is. Uh, in English, E… or maybe space, is the most common character. And you made a one-to-one transformation. that did not change the probability of seeing the thing that means E, or space, or whatever. And that's how we break substitution ciphers. You look at a giant block of ciphertext, and you notice, hey, I see Q. Four times more than I see anything else. I'll bet when they say Hugh, what they mean is E. And it turns out, a couple of hundred years later, um, after somebody had, you know, started breaking those ciphers that way. Claude Shannon showed. Here's why that works. Umm. But Huffman Codes and Morse Code? Already know something. They know E is super, super common. And Q is not. In Morse code, do you know what you send when you mean E?
Jim McQuillan:No.
Wolf:In Morse code, E is a single dot. And the Q is, I'm not sure I've got this exactly right, but I think it's dash dash dot dash. It's long! It's long because you don't have to say it very much. And that's a total reflection of the interesting thing I started with. Q is surprising, in a way that E is not. You expect to see a lot of E's, so you don't need as many bits to say it. Q. is surprising. So if you're efficient, you'll use more bits to say it. So, Morse code and Huffman codes, in exactly the same way. are not a one-to-one encoding. You start with some number of English alphabetic characters. And you transform into some other alphabet. And the number of symbols doesn't line up. Messages that have E's get one output symbol. Uh, messages that have queues get four. So the length of the output is different than the length of the input. If… Instead of, um… calculating from some just base text. Morse code. worked because Morse looked around and decided, from everything that he knew, E was the most popular, and so he just assigned dot means E. In other words, our underlying model of what's expected. And what's a surprise? is fixed in time. We expect E. E is a dot. Nobody ever argues about it. That's that. If you are looking at some specific corpus, a particular play by Shakespeare, or whatever, and you decide that you can analyze that text first. before you try to compress it by sending the minimum number of symbols, just like we did with Morse and Huffman. Umm. You can start by first figuring out what's the most common, and maybe you're even smarter than that, and you know about trigrams and digrams, whatever, it doesn't matter. You figure out the probabilities in advance, you turn that into a tiny little dictionary. And your message starts with the dictionary? And then you send symbols from the dictionary. It's not encryption. Anybody can look at your dictionary and do the right thing.
Jim McQuillan:Right.
Wolf:But now your probabilities aren't fixed. And because of those probabilities, your transformation makes the whole thing shorter. That's compression. In a nutshell. Not the best compression.
Jim McQuillan:Hmm.
Wolf:Pretty good compression. What if you don't send the dictionary? And what if the probabilities have nothing to do with the actual text? You just make it up. And you just send the message. With the same transformation. Guess what? That might not be compression, because you're not tying it to actually what's expected. But it is encryption. It's encryption because outside observers don't know what your model was. And it's unrelated to probability and length. And they can't tell. All they see is noise. But it's the same job underneath. Now, the thing that is exciting to me. Um… This is the whole reason. that I love information theory. Everything I've talked about so far is… Some integral number of symbols go into the pipe. And some integral number of symbols come out of the pipe. Maybe they're related, maybe they're not related, maybe they're different sizes, maybe… all that doesn't matter. What matters is… It's integral symbols to integral symbols, starting from the original one-to-one. But let me give you a new thing. What if… You built a model as you're looking at the message you're going to send. Uh, or you have one, or whatever. And that model, the particular model I'm thinking of in this case, is a Markov model. Um… But that model is nodes and edges. And a node is a place in time where… You've already covered some part of the message. And you're going to move forward with the rest of the message. And there are edges coming out of that node that you've traveled before. Those edges are weights. If you've been at this node and seen E five times before, the edge out of this node labeled E has a weight of five. Or maybe you only have edges for 0 and 1. But this gives you a brand new way to think about probability. Instead of saying, oh, it's 15% that I'll see an E, or whatever, because that's the statistics in English. Instead, I'm at this node, and at this node, having seen what I've seen. I've crossed the one edge 80 times. and the zero edge six times. And now you have a real number. A real number. Um… Fraction. of. At this point in time. What can I expect? Based on probability that you've shared, or not shared, or it could be secret, it doesn't matter. The point is… If you are looking at the number line from 0 to 1. And you can see, based on the transition edges out of your node. That. With 70% probability, the next thing you need to say is a 1? Instead of shipping off a 1 or a 1, it doesn't matter, forget that. Instead of doing that. Take the part of that number line that you're looking at. That represents the 70%. Because that's the symbol. Uh, that it turns out that you wanted to send. Shrink the edges. of that number line. to just highlight. That 70% that matters. Um, you know. If this was English… And you were saying cat. Your number line is divided up into 26 possible. slots of different widths, where E is really wide and… or whatever, but it turns out C is super, super, uh, probable based on where you are, you're gonna shrink that number line just down to C.
Jim McQuillan:Mmhm.
Wolf:Every time you see a new symbol, you shrink. You shrink, you shrink, you shrink. While you are doing that. Sooner or later. The edges of that shrinked area. Would that contain your message? are gonna stop moving. Moving. in terms of how you would represent them, what bits you would chip off. As soon as your precision fails. becomes higher. then those ends, suddenly those ends are, like, you don't care about them. You can ship them off now. They're done. They're never going to change. Um… No matter how much further you go, your message is absolutely starting with 0.4. You can send 0.4, and since you sent 0.4 already. You can now take that window you're looking at. and bit shifted. to get the 0.4 off the top. And now you're just focused on the part that's still changing. That… that sounds complicated. But the interesting thing is this. The Sea of Cat. was so probable. You didn't even need an entire bit. to represent it. Instead of sending a whole symbol. You sent a tenth of a bit, a hundredth of a bit. Or maybe it's Q and you needed 5 bits. The thing you are assembling with arithmetic coding. is not a brand new sequence of symbols. You are picking a single. Infinite Precision Floating Point Number. It is your message. You're not gonna send 10 new numbers, 10 new symbols, 10 new letters. You're going to send somebody one symbol. single floating point number. That is arithmetic encoding. And arithmetic encoding IS the magic. You can actually hit the entropy floor. for the message you want to send. You can send the minimum number of bits. Hussman Coding, Morse Code, they hinted. Yeah, look, you can send way less than you thought you could send. Arithmetic Coding says. This didn't even take an entire bit to express. You can do that. To me, that's a miracle. When I first read and understood. That you could send just a part of a bit to communicate your meaning? I ACTUAL. I actually laughed out loud.
Jim McQuillan:You LOL'd?
Wolf:I did this was I learned this from a book called. Text Compression by Bell, Cleary, and Witten, and this was in Chapter 5, which was named From Probability to Bits. I laughed out loud. To this day, I will re-read that chapter because of how amazing this idea and algorithm is. They have a way to use the minimum amount of. bits to express the message. And that minimum might be smaller than one.
Jim McQuillan:Hmm. Okay.
Wolf:To me, that is a miracle. So. Umm. I think those are the important things. There's other stuff that you care about, like… And is the model that is underneath it public? Does the model change as you're looking at the message? Um… Now, there's a ton of things that you might care about, and what your transformation does. is based on that model. If that model is secret and invisible and not related to actual probability, this is an encryption algorithm. If it's based on probability in some way. a good way, then it's a compression model. If you're going to do encryption. Almost certainly, except there are some hiccups I'm not going to talk about, you want to compress first. Um, so that what you have. is already as high entropy as possible, and then encrypt what's left. It should already look like noise. To anybody?
Jim McQuillan:Now, okay, okay, let's stop there for a second. You said compressing it will make it high entropy. Is that because uncompressed, you might have a long string of. the same character or a long string of zeros or something, and by compressing it, you…
Wolf:That's an example of why, but the why itself is. that uncompressed, um, information. is full of, uh, redundancy. It's got lots of very predictable stuff that you could just throw away and reconstruct.
Jim McQuillan:Yeah. Mmhm.
Wolf:For instance, the classic experiment, um, is that you and I have two. multi-megapixel images. One's a dog, one's a cat. Um, and we both have them.
Jim McQuillan:Mm-hmm.
Wolf:And, uh, it… we get to a point where you need to tell me. which image I should be using next. The naive thing is, you could send me the image of the dog. And that's 5 megapixels, or whatever. The smart way is to discard everything that's not actually real. Surprising. Because there's only two images. you could send me 0 and mean use the cat one, and a 1 to use… to mean use the dog one. And in fact. This is the exact example that Shannon used when he was describing this problem. Um… That's compression, because… All that information is now redundant. From our point of view, you and me, because we have the images, and we know what the pixels are.
Jim McQuillan:So.
Wolf:To some third party, a zero or a one?
Jim McQuillan:So we both… we both have the dictionary. We both agree on the dictionary. Our dictionary is two images, right?
Wolf:Exactly. That is 100% the right way to say it.
Jim McQuillan:Right, so now we can… Passed by reference.
Wolf:That is also right, a zero or a one.
Jim McQuillan:Yeah. See, I'm… I'm not asleep yet.
Wolf:End. Ha! And that also expresses, uh, the idea that entropy is relative to the observer. Um, the fact that you and I both have the two images. Some person who doesn't have the images. Uh, they don't get it. They don't know what we're communicating. To them, that 0 or 1 is just noise.
Jim McQuillan:Right. Right.
Wolf:We talked about compressing and then encrypting. Um… And I think there's almost. only one thing left that I want to talk about, and that is, the whole thing behind this was a thing people used to think. Uh, they use, there's, we talk about noisy channels and we have noisy channels everywhere. Wifi, um, the radio, um, everything, everything is a noisy channel. There's some amount of crap on it. that interferes. And before Shannon. Our idea was that the fact that a channel was noisy. Put a limit on how much information we can communicate across it. um… Certainly. Up. that we could get a message across. And Shannon proved. that, nope, you're wrong! Turns out, if you're willing to say it the right way, it almost doesn't matter how noisy your channel is. For me to actually prove this would require me to say math, and it's not important. What's important is. Shannon proved everybody was wrong. The channel doesn't limit how much you can say, almost entirely. Um, there's papers about this, uh, that talk about every single thing I said. Um… You can go find those papers, I'll reference some of them. But Claude Shannon himself? What an incredibly fascinating person. Uh, he was born in 1916 in Petoskey, Michigan. Um… He, uh… This stuff where he talked about switching circuits and stuff, that was from his 1937 MIT master's thesis. Uh, he went to work at Bell Labs, and in 1948, that's when he wrote the document that this whole… everything I've just said is about. And he called it a mathematical theory of communication. During World War II. He did a whole bunch of stuff he couldn't talk about for decades. He worked on cryptography at Bell Labs. Um, but… But he. He was riding around the hallways of Bell Labs. On a on a unicycle juggling. Um, he actually… knew some of these other people that mattered. Like they talked to each other and it was fascinating and interesting and. This is a thing, a person I would want to know. Um… But I absolutely love. When somebody says, oh, that's impossible, and the other person says, you know what? It's not. And I'll show you. And then they do.
Jim McQuillan:Yep.
Wolf:I think that's great. I think that is greatness. Right there in front of you. When someone proves your… The thing you thought was impossible isn't? That person's a hero for me. And that is why Shannon is in my pantheon of heroes. Um…
Jim McQuillan:Hmm. Okay.
Wolf:So. I guess let me close this out and then I'll let you close this out.
Jim McQuillan:Okay.
Wolf:But… The real thesis of this is that information was actually never about meaning, at least the way we use the word. It has always been about surprise. And surprise is always relative to the observer. What you know, what you believe. Um, just like probability, um, it's about. What you know, it has nothing to do with what will be. Um, a thing that almost nobody actually understands about probability. So. Umm. From your background. In. Uh, networking and infrastructure, everything you've done that does communication. Have you personally. Felt the noisy channel trade-off directly? Um, have you… seen stuff degrade gracefully? Have you increased the, um… redundancy in the encoding of something to give it the power to survive a noisy channel. Has this ever affected you?
Jim McQuillan:Well, the, you know, the thing I can think of is, uh, you know, back when, uh, you and I have been doing this for a long time, uh, back in the days of the dial-up modem.
Wolf:Did you ever have a noise problem?
Jim McQuillan:Right? There's some… there's some noise. And we used to have to fight that all the time, remember? And the way we started to do that was, uh, error correcting, uh, code.
Wolf:Mmhm.
Jim McQuillan:got put in place.
Wolf:Which falls right out of Shannon's, uh…
Jim McQuillan:Uh, to… Right. Yeah. Okay.
Wolf:work. Error-correcting codes, fascinating on their own. I love them. They are a direct. Um… piece of this, an error correcting code, adds specific. Uh, mathematically provable, deducible, and replicable. Redundancy. To make… Uh, otherwise sparse signals survive noisy channels.
Jim McQuillan:Yeah, you know, before that, just detecting that there was a problem, like parity bits, you know, it couldn't fix the problem, but it could point out that there's a problem, and then maybe a whole packet will get retransmitted or something.
Wolf:Yeah, you can ask you can ask for it again, but just noticing and it turns out the actual complexity of the ECC error correcting code influences how big a problem you can detect. detect. If you write a simple one, it might be you can notice a bit was flipped, but your code is fast.
Jim McQuillan:Sure.
Wolf:But if you raise the polynomial higher, you can see that up to three bits were flipped, even though those added up to something that would trick the lower polynomial. You can see it and ask for it.
Jim McQuillan:Right. Right.
Wolf:for it again. Uh, at 3, you know, using the right one, you could fix it. At 4, maybe you'd see it, and you could ask for it again, but at 6, you'd be like, oh shit, I should've used a better one. Um… So, here's your chance, push back, whatever, close us up, tell us what to do.
Jim McQuillan:Yeah. Yeah, this is… you know, as you were talking about Markov models and edges and stuff, it just had me thinking about. the conversations we've had recently about LLMs. And and, you know, you're. Yeah. Yeah. I don't understand how they work, but I.
Wolf:It is the same thing. Tokens are an input stream and states in the internal model are often represented as nodes where a node actually conforms to. uh, many tokens, and the edges out of a node, the same. And, you know, the thing, uh, silly people call the LLM thinking. is, uh, moving among the states according to probability. But what we have today isn't AGI, it's not close to anything like that. It's.
Jim McQuillan:Sure.
Wolf:It's prediction. It's walking around that network. It's autocomplete. It's super, super good autocomplete. I love it, and I don't want to live without it, but…
Jim McQuillan:And it's… but it's… it's super, super related to what we've been talking about today.
Wolf:Yep.
Jim McQuillan:Yeah, great. Great. So that was great, Wolf. I've been looking forward to this one. We have…
Wolf:Did I manage to skip the boring stuff?
Jim McQuillan:Well, or I slept through it. I don't remember it. There's a lot of information here. As always, we have show notes in our, you can find it in your podcast player or you can find them on the website. Within the show notes, Wolf's got a bunch of links and some. Some other information, uh, that you might want to take a look at, because he just couldn't go into everything today during the episode. If you want to find those show notes other than your podcast player, our website is runtimearguments.fm. If you go to that page, you'll see the list of episodes. Click on this episode.
Wolf:And remember, H-T-T-P, no S.
Jim McQuillan:It just doesn't have an SSL cert, yeah. Yeah. Um… and also in the show notes will be, uh, uh, information on how you can contact us, send us feedback, ask us questions, whatever. Um…
Wolf:Tell us what to talk about.
Jim McQuillan:And again. Yeah, tell us what you'd like to hear. And again, runtimearguments.fm. Wolf and I are both on Mastodon. Our Mastodon addresses are listed there. Our email address is listed there. So yeah, check out the show notes. Along with the show notes is a transcript. of this episode, like always. So yeah, check it out. Anything else you wanna say, Wolf, before we say bye-bye?
Wolf:I do. I want to thank all our listeners, of course, and our friends who give us so much feedback and ideas, and especially my brand new friend, Rama.
Jim McQuillan:Damn.
Wolf:I hope he is listening to this episode, or some episode, and um… I just appreciate his, um… uh, input on us and the stuff we've done. It was… hearing from him genu… genuinely, uh, was enchanting.
Jim McQuillan:It's, it's, uh, it sort of lifts your day, doesn't it? You know, I had, uh, I should have mentioned it earlier, I had a, um, I had a doctor's visit a couple of days ago, and, uh, my doctor told me she was proud of me, and boy, did that change my day!
Wolf:It really does.
Jim McQuillan:I had lost a little bit of weight, and boy, I… I was… I was walking on clouds for a couple of days. It's… it's nice to get a compliment like that.
Wolf:I love them.
Jim McQuillan:But yeah, I mean, she gives me feedback every time. Sometimes it's like that.
Wolf:I… I hate it when my doctor tells me stuff I can't do. Like, uh… I don't eat all that much, and my day is… in terms of food, um, I drink a protein shake in the morning, and I showed my doctor what I drink, and she's like, absolutely do not drink that. Um, that is a nightmare. Uh, you are drinking, like, I don't know why they don't just name it sugar. Because that's what you're having. It is not good for you, and your life is terrible because you're drinking this.
Jim McQuillan:Or poison, yeah. Yeah. All right. Hey, Wolf, as always, thanks for podcasting with me. It's always a pleasure. And goodbye, everybody.
Wolf:Right back at you, buddy. Bye.
People on this episode
Podcasts we love
Check out these other fine podcasts recommended by us, not an algorithm.
CoRecursive: Coding Stories
Adam Gordon Bell - Software Developer
Two's Complement
Ben Rady and Matt GodboltAccidental Tech Podcast
Marco Arment, Casey Liss, John Siracusa
Python Bytes
Michael Kennedy and Calvin Hendryx-Parker