# From Twenty Questions to Entropy and Huffman Compression > A concrete introduction to information theory through binary questions. Eight equally likely outcomes establish the bit, then an unequal distribution shows why likely symbols deserve shorter descriptions. Repeated halving leads to self-information and the entropy formula. The same probabilities are used to build a Huffman tree one rarest-pair merge at a time, producing an average length of 2.60 bits per symbol against an entropy of about 2.522. The lecture closes with the binary tree capacity argument behind the entropy lower bound and explains why predictable English text compresses while independent random bytes generally do not. - Canonical watch page: [From Twenty Questions to Entropy and Huffman Compression](https://academa.ai/lectures/entropy-as-twenty-questions) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-29T00:36:55.000Z - Updated: 2026-08-29T00:36:55.000Z - Duration: PT865S (14 minutes 25 seconds) - Chapters: 5 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TXDQBTMXE7F1ES780ET6G/2/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TXDQBTMXE7F1ES780ET6G/2/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TXDQBTMXE7F1ES780ET6G/2/dark/poster.jpg) ## Description Derive entropy from twenty questions, build a Huffman code, compare its length with the limit, and explain when files can compress. ## Chapters - [00:00–01:59.253 · Questions Are Bits](https://academa.ai/lectures/entropy-as-twenty-questions?t=0) - [01:59.253–04:15.641 · Likelihood Changes the Questions](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668) - [04:15.641–06:57.784 · From Question Counts to Entropy](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667) - [06:57.784–09:29.11 · Build the Huffman Tree](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625) - [09:29.11–14:25 · The Bound and the Files We Compress](https://academa.ai/lectures/entropy-as-twenty-questions?t=569.1103333333333) ## Transcript ### [00:00 · Questions Are Bits](https://academa.ai/lectures/entropy-as-twenty-questions?t=0) Suppose I secretly choose one of these eight letters. You may ask only questions whose answer is yes or no. Your job is to identify my letter with certainty. How many answers do you need? Because the letters are equally likely, the sensible first question cuts the possibilities into equal halves. Ask whether the letter lies in A through D. One answer leaves the upper four; the other leaves the lower four. The first answer has taken us from eight candidates to four. It has not named the symbol, but it has removed exactly half of the uncertainty. Ask another balanced question inside the surviving half. Four candidates become two. The same yes-or-no answer has again divided the remaining possibilities by two. A third question separates the final pair. Eight leaves now stand at the ends of the tree, and every letter is reached by exactly three answers. The count is not an accident. Three binary answers can form eight distinct answer strings, because two choices made three times give two cubed. Turn that relation around. The number of binary questions needed to choose among eight equal possibilities is log base two of eight, which is three. We give one balanced binary answer a unit of information and call that unit a bit. A bit is not merely a zero stored in memory. It is the distinction between two alternatives that were both still possible. With q binary answers there are two to the q possible answer strings. Therefore identifying one of N equally likely outcomes requires log base two of N bits. Next we will make the letters unequally likely. That one change will lead us first to entropy, the ideal average question count, and then to Huffman coding, a way to build an actual binary description close to that ideal. ### [01:59.253 · Likelihood Changes the Questions](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668) Keep the same eight symbols, but change their likelihoods. A now occurs forty percent of the time. B occurs twenty percent. C and D each occur ten percent, and the final four symbols each occur five percent. A alone occupies forty percent of the probability bar. It is twice as likely as B, and four times as likely as either C or D. C and D together occupy another twenty percent. They are less common individually, but they still matter much more often than any one of the four symbols at the narrow end. The final four slices are equal and rare. Each accounts for only one twentieth of the messages. If we keep the old balanced tree, every outcome still costs three questions. That treats a five-percent event exactly like the event that appears forty percent of the time. Instead, ask the most useful question first: is the symbol A? When the answer is yes, which happens forty percent of the time, the search ends after one bit. If it was not A, the next question can separate B. B then takes two answers. The commonest sixty percent of all symbols have received the two shortest paths. The price is that C and D now require four questions. That sounds worse than the old three, but each of those symbols appears only one time in ten. The four rarest outcomes take five questions each. Long answers are not free, but we pay for them on only twenty percent of the symbols. Now average the question counts using their probabilities. A contributes point four times one. B contributes point two times two. C and D together contribute point two times four, and the rare group contributes point two times five. The result is two point six questions per symbol. Some individual outcomes became more expensive, but the outcomes we see most often became much cheaper. The equal-depth plan cost exactly three questions. Exploiting likelihood saves point four of a question per symbol on average. Over a million symbols, that becomes roughly four hundred thousand fewer binary answers. ### [04:15.641 · From Question Counts to Entropy](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667) For eight equal outcomes, three halvings isolate one outcome because one eighth equals one over two cubed. Now replace one eighth by a general probability p. Imagine a very large collection of equally detailed possibilities. An event with probability p occupies the fraction p of them. To isolate that fraction by balanced binary questions, we keep halving. After q balanced questions, one answer path identifies about one part in two to the q. To match an event occupying fraction p, two to the q must be about one over p. Solve for q. The ideal question count is log base two of one over p. Equivalently, it is minus log base two of p. This quantity measures surprise. A likely event has a large p and a small information value. A rare event has a small p and needs a longer answer path to distinguish it. For A, p is point four, so the ideal length is about one point three two two bits. For a five-percent symbol, it is about four point three two two bits. These are not yet legal single-symbol code lengths. A single binary question cannot be split into a fraction. But across a long stream, common and rare symbols can share a description strategy, and a fractional average becomes meaningful. To find the ideal average, weight each symbol's question count by the probability of seeing that symbol, then add. This weighted average is the quantity we call entropy. Now calculate it for our distribution. A contributes about point five two nine bits per source symbol. That is its ideal length multiplied by the forty-percent frequency with which we pay it. B contributes about point four six four. C and D together contribute about point six six four. The four five-percent symbols each carry more surprise, and together they contribute about point eight six four bits. Adding every group gives an entropy of about two point five two two bits per symbol. Here is another way to read the same number. In a long block of n symbols, the probability pattern concentrates most messages among roughly two to the n H typical sequences. Distinguishing that many likely messages needs about the log of their count, which is n H binary answers. Entropy is therefore not an arbitrary formula. It is the question count forced by the number of likely messages. ### [06:57.784 · Build the Huffman Tree](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625) Huffman coding turns the probability list into a binary tree. Begin with one leaf for every symbol. The only repeated instruction is to merge the two smallest weights. The first two rarest leaves are E and F, each with weight five. Join them under a new node of weight ten. G and H are the next equal pair. Merge their five-percent weights into a second node of weight ten. C and D each have weight ten. Merge those two leaves into a node of weight twenty. The two ten-weight branches made from E through H are now the smallest pair. Their merge produces another weight twenty. Three weights of twenty are available. Ties may be resolved consistently in more than one way. Merge these two compound branches to make forty. B has weight twenty and the compound branch has weight forty. They are the two smallest remaining items, so their parent has weight sixty. Finally merge A, with weight forty, and the remaining weight sixty. Their root has weight one hundred, and the Huffman tree is complete. Assign zero to the upper branch and one to the lower branch at each split. A codeword is the sequence encountered while walking from the root to a leaf. A is reached immediately by code zero, so the most likely symbol costs only one bit. B follows one then zero, so it costs two bits. C and D sit deeper, with codes one one zero zero and one one zero one. Each requires four bits. The four rarest symbols lie one level deeper still. Their codes share the prefix one one one, then use two more bits to select the leaf. No codeword is the beginning of another codeword. That prefix property lets a decoder read the stream from left to right and know exactly when each symbol ends. Compute the average length. A pays one bit forty percent of the time. B pays two bits twenty percent of the time. C and D pay four, and the final four symbols pay five. The Huffman code therefore uses two point six bits per symbol on average. The merging rule has recovered the likelihood-aware question plan, and it has guaranteed that no other binary prefix code has a smaller average length for these individual symbols. ### [09:29.11 · The Bound and the Files We Compress](https://academa.ai/lectures/entropy-as-twenty-questions?t=569.1103333333333) Put the two numbers on one scale. Entropy for our source is about two point five two two bits per symbol. The Huffman code uses two point six. The gap is only point zero seven eight of a bit per symbol. Huffman coding is not merely better than the fixed three-bit code. It is very close to the information-theoretic target. Two questions remain. Why can no lossless prefix code move the green point to the left of entropy? And if the bound is unbeatable, why is Huffman allowed to sit slightly above it? A binary prefix code is a set of nonoverlapping leaves in a binary tree. A codeword of length l occupies one part in two to the l of the tree's capacity. Add those occupied fractions over all symbols. They cannot exceed one. This is the tree-capacity inequality, often called Kraft's inequality. Now compare the actual average length L with entropy H. Their difference can be written as this weighted logarithmic ratio. The log-sum inequality says that weighted ratio is at least minus the log of the tree capacity. Since the capacity is at most one, that quantity is nonnegative. Therefore every binary prefix code has average length at least H. Shorter paths for some outcomes consume more tree capacity and force compensating longer paths elsewhere. The average cannot cross the entropy bound. Entropy supplies ideal lengths such as one point three two two bits. Real codewords have whole-number lengths. Huffman chooses those integers optimally, and its average is always less than one bit above entropy for a memoryless symbol source. When probabilities are exact powers of one half, the ideal lengths are integers and Huffman can meet entropy exactly. Otherwise it rounds through the tree, as our small point zero seven eight gap demonstrates. There is also a way to make the rounding cost per symbol smaller. Encode blocks of symbols together. One possible extra bit is then shared by the whole block rather than charged to every symbol. Now return to files. Typical English text is structured. Spaces and common letters occur more often than rare punctuation, so even the one-byte distribution is uneven. English also has dependencies across positions. After the letters q and u, some next letters are far more plausible than others. Words, phrases, indentation, and repeated substrings create further predictability. A compressor turns that predictability into short descriptions. Huffman coding exploits a probability distribution. More advanced compressors also exploit context, repeated strings, and predictions from earlier data. Independent random bytes are different. Each of the two hundred fifty-six byte values has probability one over two hundred fifty-six, and the next byte is not predicted by the bytes before it. There is no statistical redundancy to exploit. The entropy is eight bits per byte, exactly the size already used by an ordinary byte. There are two hundred fifty-six possible byte values, which is two to the eighth. If they are equally likely, identifying one requires eight bits. For an n-byte file there are two to the eight n possible inputs. There are not enough shorter binary strings to give every input a unique shorter lossless description. Some individual random-looking file may shrink by chance, but most will not, and compressor metadata can make them larger. Already compressed or encrypted files often behave similarly because their byte patterns have been deliberately made difficult to predict. The whole story now fits into four steps. First, a bit is one resolved binary choice. Second, repeated halving says an event of probability p carries about log base two of one over p bits. Averaging that surprise gives entropy. Third, Huffman coding repeatedly merges rare events so likely symbols end near the root. Its integer code lengths approach the entropy limit without ever beating that lower bound. Finally, compression is possible when data contains predictable structure. English supplies redundancy and context. Independent random bytes do not. Entropy measures that difference, and coding turns the available predictability into fewer stored bits. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TXDQBTMXE7F1ES780ET6G/2/semantic.json) Record version: 1. Render attempt: 2. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [Questions Are Bits](https://academa.ai/lectures/entropy-as-twenty-questions?t=0) Span: 00:00–01:59.253 (0s–119.25329166666668s). #### Objects - binary\_note: a Math \[text\] that says "$q thin upright("binary questions") arrow.r 2^q thin upright("possible answers")$" - bit\_definition: a Panel that says "One bit is the information supplied by one answer to a binary question, when either answer remains possible." - bit\_line: a Math \[text\] that says "$log\_2 8 = 3 thin upright("bits")$" - count\_line: a Math \[text\] that says "$8 arrow.r 4 arrow.r 2 arrow.r 1$" - destination: a Text \[text\] that says "Our destination is a number called entropy and a practical construction called Huffman coding. Both answer the same question: how short can the average description of a symbol be?" - first\_edges: a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)) - first\_edges\_2: a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)) - heading: a Heading that says "One Answer, One Bit" - heading\_2: a Heading that says "Where the Questions Lead" - leaves: a Point \[blue\] labelled "A" drawn in tree (location=(5.5, 3.75)) - leaves\_2: a Point \[blue\] labelled "B" drawn in tree (location=(5.5, 3.25)) - leaves\_3: a Point \[blue\] labelled "C" drawn in tree (location=(5.5, 2.75)) - leaves\_4: a Point \[blue\] labelled "D" drawn in tree (location=(5.5, 2.25)) - leaves\_5: a Point \[blue\] labelled "E" drawn in tree (location=(5.5, 1.75)) - leaves\_6: a Point \[blue\] labelled "F" drawn in tree (location=(5.5, 1.25)) - leaves\_7: a Point \[blue\] labelled "G" drawn in tree (location=(5.5, 0.75)) - leaves\_8: a Point \[blue\] labelled "H" drawn in tree (location=(5.5, 0.25)) - level\_one: a Point \[yellow\] drawn in tree (location=(1.8, 3.0)) - level\_one\_2: a Point \[yellow\] drawn in tree (location=(1.8, 1.0)) - level\_two: a Point \[green\] drawn in tree (location=(3.15, 3.5)) - level\_two\_2: a Point \[green\] drawn in tree (location=(3.15, 2.5)) - level\_two\_3: a Point \[green\] drawn in tree (location=(3.15, 1.5)) - level\_two\_4: a Point \[green\] drawn in tree (location=(3.15, 0.5)) - power\_line: a Math \[text\] that says "$8 = 2^3$" - question: a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?" - root: a Point \[red\] drawn in tree (location=(0.45, 2.0)) - second\_edges: a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 3.5)) - second\_edges\_2: a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 2.5)) - second\_edges\_3: a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 1.5)) - second\_edges\_4: a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 0.5)) - third\_edges: a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.75)) - third\_edges\_2: a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.25)) - third\_edges\_3: a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.75)) - third\_edges\_4: a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.25)) - third\_edges\_5: a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.75)) - third\_edges\_6: a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.25)) - third\_edges\_7: a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.75)) - third\_edges\_8: a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.25)) - tree: a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)) #### Beats ##### [00:00](https://academa.ai/lectures/entropy-as-twenty-questions?t=0) Narration: Suppose I secretly choose one of these eight letters. You may ask only questions whose answer is yes or no. Your job is to identify my letter with certainty. How many answers do you need? Board: Empty. Actions: - [00:00](https://academa.ai/lectures/entropy-as-twenty-questions?t=0): question is shown on the screen, written out. - [00:11.738](https://academa.ai/lectures/entropy-as-twenty-questions?t=11.738): question moves to a new place on the board. ##### [00:12.338](https://academa.ai/lectures/entropy-as-twenty-questions?t=12.338) Narration: Because the letters are equally likely, the sensible first question cuts the possibilities into equal halves. Ask whether the letter lies in A through D. One answer leaves the upper four; the other leaves the lower four. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?" Actions: - [00:12.338](https://academa.ai/lectures/entropy-as-twenty-questions?t=12.338): tree is shown on the screen, written out. - [00:12.338](https://academa.ai/lectures/entropy-as-twenty-questions?t=12.338): root is shown on the screen, written out. - [00:18.142](https://academa.ai/lectures/entropy-as-twenty-questions?t=18.141999999999996): level\_one is shown on the screen, written out. - [00:18.142](https://academa.ai/lectures/entropy-as-twenty-questions?t=18.141999999999996): level\_one\_2 is shown on the screen, written out. - [00:18.142](https://academa.ai/lectures/entropy-as-twenty-questions?t=18.141999999999996): first\_edges is shown on the screen, written out. - [00:18.142](https://academa.ai/lectures/entropy-as-twenty-questions?t=18.141999999999996): first\_edges\_2 is shown on the screen, written out. ##### [00:26.648](https://academa.ai/lectures/entropy-as-twenty-questions?t=26.6485) Narration: The first answer has taken us from eight candidates to four. It has not named the symbol, but it has removed exactly half of the uncertainty. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?"; tree — a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)); root — a Point \[red\] drawn in tree (location=(0.45, 2.0)); level\_one — a Point \[yellow\] drawn in tree (location=(1.8, 3.0)); level\_one\_2 — a Point \[yellow\] drawn in tree (location=(1.8, 1.0)); first\_edges — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)); first\_edges\_2 — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)) Actions: - [00:28.622](https://academa.ai/lectures/entropy-as-twenty-questions?t=28.621999999999996): tree moves to a new place on the board. - [00:28.622](https://academa.ai/lectures/entropy-as-twenty-questions?t=28.621999999999996): count\_line is shown on the screen, written out. - [00:29.517](https://academa.ai/lectures/entropy-as-twenty-questions?t=29.517): count\_line (the "4" part) is indicated — a transient flash. ##### [00:35.724](https://academa.ai/lectures/entropy-as-twenty-questions?t=35.7245) Narration: Ask another balanced question inside the surviving half. Four candidates become two. The same yes-or-no answer has again divided the remaining possibilities by two. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?"; tree — a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)); count\_line — a Math \[text\] that says "$8 arrow.r 4 arrow.r 2 arrow.r 1$"; root — a Point \[red\] drawn in tree (location=(0.45, 2.0)); level\_one — a Point \[yellow\] drawn in tree (location=(1.8, 3.0)); level\_one\_2 — a Point \[yellow\] drawn in tree (location=(1.8, 1.0)); first\_edges — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)); first\_edges\_2 — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)) Actions: - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): level\_two is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): level\_two\_2 is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): level\_two\_3 is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): level\_two\_4 is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): second\_edges is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): second\_edges\_2 is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): second\_edges\_3 is shown on the screen, written out. - [00:40.717](https://academa.ai/lectures/entropy-as-twenty-questions?t=40.717): second\_edges\_4 is shown on the screen, written out. - [00:45.976](https://academa.ai/lectures/entropy-as-twenty-questions?t=45.976): count\_line (the "2" part) is indicated — a transient flash. ##### [00:47.447](https://academa.ai/lectures/entropy-as-twenty-questions?t=47.4465) Narration: A third question separates the final pair. Eight leaves now stand at the ends of the tree, and every letter is reached by exactly three answers. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?"; tree — a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)); count\_line — a Math \[text\] that says "$8 arrow.r 4 arrow.r 2 arrow.r 1$"; root — a Point \[red\] drawn in tree (location=(0.45, 2.0)); level\_one — a Point \[yellow\] drawn in tree (location=(1.8, 3.0)); level\_one\_2 — a Point \[yellow\] drawn in tree (location=(1.8, 1.0)); first\_edges — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)); first\_edges\_2 — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)); level\_two — a Point \[green\] drawn in tree (location=(3.15, 3.5)); level\_two\_2 — a Point \[green\] drawn in tree (location=(3.15, 2.5)); level\_two\_3 — a Point \[green\] drawn in tree (location=(3.15, 1.5)); level\_two\_4 — a Point \[green\] drawn in tree (location=(3.15, 0.5)); second\_edges — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 3.5)); second\_edges\_2 — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 2.5)); second\_edges\_3 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 1.5)); second\_edges\_4 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 0.5)) Actions: - [00:49.351](https://academa.ai/lectures/entropy-as-twenty-questions?t=49.351): count\_line (the "1" part) is indicated — a transient flash. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_2 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_3 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_4 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_5 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_6 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_7 is shown on the screen, written out. - [00:50.906](https://academa.ai/lectures/entropy-as-twenty-questions?t=50.906): leaves\_8 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_2 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_3 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_4 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_5 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_6 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_7 is shown on the screen, written out. - [00:55.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=55.515): third\_edges\_8 is shown on the screen, written out. ##### [00:57.497](https://academa.ai/lectures/entropy-as-twenty-questions?t=57.497) Narration: The count is not an accident. Three binary answers can form eight distinct answer strings, because two choices made three times give two cubed. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?"; tree — a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)); count\_line — a Math \[text\] that says "$8 arrow.r 4 arrow.r 2 arrow.r 1$"; root — a Point \[red\] drawn in tree (location=(0.45, 2.0)); level\_one — a Point \[yellow\] drawn in tree (location=(1.8, 3.0)); level\_one\_2 — a Point \[yellow\] drawn in tree (location=(1.8, 1.0)); first\_edges — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)); first\_edges\_2 — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)); level\_two — a Point \[green\] drawn in tree (location=(3.15, 3.5)); level\_two\_2 — a Point \[green\] drawn in tree (location=(3.15, 2.5)); level\_two\_3 — a Point \[green\] drawn in tree (location=(3.15, 1.5)); level\_two\_4 — a Point \[green\] drawn in tree (location=(3.15, 0.5)); second\_edges — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 3.5)); second\_edges\_2 — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 2.5)); second\_edges\_3 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 1.5)); second\_edges\_4 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 0.5)); leaves — a Point \[blue\] labelled "A" drawn in tree (location=(5.5, 3.75)); leaves\_2 — a Point \[blue\] labelled "B" drawn in tree (location=(5.5, 3.25)); leaves\_3 — a Point \[blue\] labelled "C" drawn in tree (location=(5.5, 2.75)); leaves\_4 — a Point \[blue\] labelled "D" drawn in tree (location=(5.5, 2.25)); leaves\_5 — a Point \[blue\] labelled "E" drawn in tree (location=(5.5, 1.75)); leaves\_6 — a Point \[blue\] labelled "F" drawn in tree (location=(5.5, 1.25)); leaves\_7 — a Point \[blue\] labelled "G" drawn in tree (location=(5.5, 0.75)); leaves\_8 — a Point \[blue\] labelled "H" drawn in tree (location=(5.5, 0.25)); third\_edges — a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.75)); third\_edges\_2 — a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.25)); third\_edges\_3 — a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.75)); third\_edges\_4 — a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.25)); third\_edges\_5 — a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.75)); third\_edges\_6 — a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.25)); third\_edges\_7 — a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.75)); third\_edges\_8 — a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.25)) Actions: - [00:57.497](https://academa.ai/lectures/entropy-as-twenty-questions?t=57.497): power\_line is shown on the screen, written out. - [01:5.868](https://academa.ai/lectures/entropy-as-twenty-questions?t=65.868): power\_line (the "2^3" part) is indicated — a transient flash. ##### [01:7.536](https://academa.ai/lectures/entropy-as-twenty-questions?t=67.536) Narration: Turn that relation around. The number of binary questions needed to choose among eight equal possibilities is log base two of eight, which is three. Board: question — a Panel that says "I secretly choose one symbol from $A,B,C,D,E,F,G,H$. How many yes-or-no questions are needed to identify it?"; tree — a Figure (x\_range=(0.0, 6.5), y\_range=(0.0, 4.0), aspect=(6.5, 4.0)); count\_line — a Math \[text\] that says "$8 arrow.r 4 arrow.r 2 arrow.r 1$"; power\_line — a Math \[text\] that says "$8 = 2^3$"; root — a Point \[red\] drawn in tree (location=(0.45, 2.0)); level\_one — a Point \[yellow\] drawn in tree (location=(1.8, 3.0)); level\_one\_2 — a Point \[yellow\] drawn in tree (location=(1.8, 1.0)); first\_edges — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 3.0)); first\_edges\_2 — a Line \[yellow\] drawn in tree (start=(0.45, 2.0), end=(1.8, 1.0)); level\_two — a Point \[green\] drawn in tree (location=(3.15, 3.5)); level\_two\_2 — a Point \[green\] drawn in tree (location=(3.15, 2.5)); level\_two\_3 — a Point \[green\] drawn in tree (location=(3.15, 1.5)); level\_two\_4 — a Point \[green\] drawn in tree (location=(3.15, 0.5)); second\_edges — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 3.5)); second\_edges\_2 — a Line \[green\] drawn in tree (start=(1.8, 3.0), end=(3.15, 2.5)); second\_edges\_3 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 1.5)); second\_edges\_4 — a Line \[green\] drawn in tree (start=(1.8, 1.0), end=(3.15, 0.5)); leaves — a Point \[blue\] labelled "A" drawn in tree (location=(5.5, 3.75)); leaves\_2 — a Point \[blue\] labelled "B" drawn in tree (location=(5.5, 3.25)); leaves\_3 — a Point \[blue\] labelled "C" drawn in tree (location=(5.5, 2.75)); leaves\_4 — a Point \[blue\] labelled "D" drawn in tree (location=(5.5, 2.25)); leaves\_5 — a Point \[blue\] labelled "E" drawn in tree (location=(5.5, 1.75)); leaves\_6 — a Point \[blue\] labelled "F" drawn in tree (location=(5.5, 1.25)); leaves\_7 — a Point \[blue\] labelled "G" drawn in tree (location=(5.5, 0.75)); leaves\_8 — a Point \[blue\] labelled "H" drawn in tree (location=(5.5, 0.25)); third\_edges — a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.75)); third\_edges\_2 — a Line \[blue\] drawn in tree (start=(3.15, 3.5), end=(5.5, 3.25)); third\_edges\_3 — a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.75)); third\_edges\_4 — a Line \[blue\] drawn in tree (start=(3.15, 2.5), end=(5.5, 2.25)); third\_edges\_5 — a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.75)); third\_edges\_6 — a Line \[blue\] drawn in tree (start=(3.15, 1.5), end=(5.5, 1.25)); third\_edges\_7 — a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.75)); third\_edges\_8 — a Line \[blue\] drawn in tree (start=(3.15, 0.5), end=(5.5, 0.25)) Actions: - [01:14.943](https://academa.ai/lectures/entropy-as-twenty-questions?t=74.94300000000001): bit\_line is shown on the screen, written out. - [01:16.778](https://academa.ai/lectures/entropy-as-twenty-questions?t=76.77799999999999): bit\_line (the "3" part) is indicated — a transient flash. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): bit\_line is hidden from the screen — left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): count\_line is hidden from the screen — left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): power\_line is hidden from the screen — left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): question is hidden from the screen — left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): tree is hidden from the screen — left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): root is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_one is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_one\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): first\_edges is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): first\_edges\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_two is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_two\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_two\_3 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): level\_two\_4 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): second\_edges is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): second\_edges\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): second\_edges\_3 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): second\_edges\_4 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_3 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_4 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_5 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_6 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_7 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): leaves\_8 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_2 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_3 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_4 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_5 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_6 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_7 is hidden from the screen — tree left the board. - [01:17.695](https://academa.ai/lectures/entropy-as-twenty-questions?t=77.69500000000001): third\_edges\_8 is hidden from the screen — tree left the board. ##### [01:18.295](https://academa.ai/lectures/entropy-as-twenty-questions?t=78.295) Narration: We give one balanced binary answer a unit of information and call that unit a bit. A bit is not merely a zero stored in memory. It is the distinction between two alternatives that were both still possible. Board: Empty. Actions: - [01:23.009](https://academa.ai/lectures/entropy-as-twenty-questions?t=83.009): bit\_definition is shown on the screen, written out. ##### [01:32.073](https://academa.ai/lectures/entropy-as-twenty-questions?t=92.07300000000001) Narration: With q binary answers there are two to the q possible answer strings. Therefore identifying one of N equally likely outcomes requires log base two of N bits. Board: bit\_definition — a Panel that says "One bit is the information supplied by one answer to a binary question, when either answer remains possible." Actions: - [01:32.665](https://academa.ai/lectures/entropy-as-twenty-questions?t=92.66499999999999): binary\_note is shown on the screen, written out. - [01:34.325](https://academa.ai/lectures/entropy-as-twenty-questions?t=94.325): binary\_note (the "2^q" part) is emphasized. - [01:42.998](https://academa.ai/lectures/entropy-as-twenty-questions?t=102.998): binary\_note is hidden from the screen — left the board. - [01:42.998](https://academa.ai/lectures/entropy-as-twenty-questions?t=102.998): bit\_definition is hidden from the screen — left the board. - [01:42.998](https://academa.ai/lectures/entropy-as-twenty-questions?t=102.998): binary\_note (the "2^q" part) is no longer emphasized. ##### [01:43.598](https://academa.ai/lectures/entropy-as-twenty-questions?t=103.59800000000001) Narration: Next we will make the letters unequally likely. That one change will lead us first to entropy, the ideal average question count, and then to Huffman coding, a way to build an actual binary description close to that ideal. Board: Empty. Actions: - [01:49.264](https://academa.ai/lectures/entropy-as-twenty-questions?t=109.26400000000001): destination is shown on the screen, written out. - [01:49.264](https://academa.ai/lectures/entropy-as-twenty-questions?t=109.26400000000001): destination (the "entropy" part) is emphasized. - [01:52.932](https://academa.ai/lectures/entropy-as-twenty-questions?t=112.932): destination (the "Huffman coding" part) is emphasized. - [01:52.932](https://academa.ai/lectures/entropy-as-twenty-questions?t=112.932): destination (the "entropy" part) is no longer emphasized. - [01:57.962](https://academa.ai/lectures/entropy-as-twenty-questions?t=117.96162500000001): destination (the "Huffman coding" part) is no longer emphasized. - [01:58.212](https://academa.ai/lectures/entropy-as-twenty-questions?t=118.21162500000001): destination is hidden from the screen — left the board. ### Scene 2: [Likelihood Changes the Questions](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668) Span: 01:59.253–04:15.641 (119.25329166666668s–255.6412916666667s). #### Objects - bar: a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)) - comparison: a Math \[text\] that says "$3.00 - 2.60 = 0.40 thin upright("question saved on average")$" - distribution: a Table \[text\] that says "Symbol Probability A 40% B 20% C 10% D 10% E 5% F 5% G 5% H 5%" (rows=(('Symbol', 'Probability'), ('A', '40%'), ('B', '20%'), ('C', '…, header=True) - expected\_work: a Derivation \[text\] that says "$L = 0.4(1) + 0.2(2) + 0.2(4) + 0.2(5) \\ L = 2.60 thin upright("questions")$" - heading\_distribution: a Heading that says "The Same Symbols, Different Likelihoods" - heading\_plan: a Heading that says "Spend Short Answers on Likely Symbols" - labels: a Point \[red\] labelled "A thin 40%" drawn in bar (location=(20.0, 0.5), show\_marker=False) - labels\_2: a Point \[blue\] labelled "B thin 20%" drawn in bar (location=(50.0, 0.5), show\_marker=False) - labels\_3: a Point \[green\] labelled "C thin 10%" drawn in bar (location=(65.0, 0.5), show\_marker=False) - labels\_4: a Point \[green\] labelled "D thin 10%" drawn in bar (location=(75.0, 0.5), show\_marker=False) - labels\_5: a Point \[yellow\] labelled "E thin 5%" drawn in bar (location=(82.5, 0.5), show\_marker=False) - labels\_6: a Point \[yellow\] labelled "F thin 5%" drawn in bar (location=(87.5, 0.5), show\_marker=False) - labels\_7: a Point \[yellow\] labelled "G thin 5%" drawn in bar (location=(92.5, 0.5), show\_marker=False) - labels\_8: a Point \[yellow\] labelled "H thin 5%" drawn in bar (location=(97.5, 0.5), show\_marker=False) - plan: a Table \[text\] that says "Symbol $p$ $q$ A 40% 1 B 20% 2 C 10% 4 D 10% 4 E 5% 5 F 5% 5 G 5% 5 H 5% 5" (rows=(('Symbol', '$p$', '$q$'), ('A', '40%', '1'), ('B', '20%', '2')…, header=True) - regions: a Polygon \[red\] drawn in bar (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45) - regions\_2: a Polygon \[blue\] drawn in bar (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45) - regions\_3: a Polygon \[green\] drawn in bar (vertices=((60.0, 0.0), (70.0, 0.0), (70.0, 1.0), (60.0, 1.0)), fill\_opacity=0.45) - regions\_4: a Polygon \[green\] drawn in bar (vertices=((70.0, 0.0), (80.0, 0.0), (80.0, 1.0), (70.0, 1.0)), fill\_opacity=0.45) - regions\_5: a Polygon \[yellow\] drawn in bar (vertices=((80.0, 0.0), (85.0, 0.0), (85.0, 1.0), (80.0, 1.0)), fill\_opacity=0.45) - regions\_6: a Polygon \[yellow\] drawn in bar (vertices=((85.0, 0.0), (90.0, 0.0), (90.0, 1.0), (85.0, 1.0)), fill\_opacity=0.45) - regions\_7: a Polygon \[yellow\] drawn in bar (vertices=((90.0, 0.0), (95.0, 0.0), (95.0, 1.0), (90.0, 1.0)), fill\_opacity=0.45) - regions\_8: a Polygon \[yellow\] drawn in bar (vertices=((95.0, 0.0), (100.0, 0.0), (100.0, 1.0), (95.0, 1.0)), fill\_opacity=0.45) #### Beats ##### [01:59.253](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668) Narration: Keep the same eight symbols, but change their likelihoods. A now occurs forty percent of the time. B occurs twenty percent. C and D each occur ten percent, and the final four symbols each occur five percent. Board: Empty. Actions: - [01:59.253](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668): heading\_distribution is shown on the screen, written out. - [01:59.253](https://academa.ai/lectures/entropy-as-twenty-questions?t=119.25329166666668): distribution is shown on the screen, written out. - [02:1.447](https://academa.ai/lectures/entropy-as-twenty-questions?t=121.44729166666669): bar is shown on the screen, written out. ##### [02:14.749](https://academa.ai/lectures/entropy-as-twenty-questions?t=134.74879166666668) Narration: A alone occupies forty percent of the probability bar. It is twice as likely as B, and four times as likely as either C or D. Board: bar — a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)); heading\_distribution — a Heading that says "The Same Symbols, Different Likelihoods" Actions: - [02:15.155](https://academa.ai/lectures/entropy-as-twenty-questions?t=135.15529166666667): distribution is shown on the screen, written out. - [02:16.687](https://academa.ai/lectures/entropy-as-twenty-questions?t=136.68729166666668): regions is shown on the screen, written out. - [02:16.687](https://academa.ai/lectures/entropy-as-twenty-questions?t=136.68729166666668): labels is shown on the screen, written out. - [02:20.182](https://academa.ai/lectures/entropy-as-twenty-questions?t=140.18229166666669): regions\_2 is shown on the screen, written out. - [02:20.182](https://academa.ai/lectures/entropy-as-twenty-questions?t=140.18229166666669): labels\_2 is shown on the screen, written out. - [02:20.182](https://academa.ai/lectures/entropy-as-twenty-questions?t=140.18229166666669): distribution is shown on the screen, written out. ##### [02:24.404](https://academa.ai/lectures/entropy-as-twenty-questions?t=144.4042916666667) Narration: C and D together occupy another twenty percent. They are less common individually, but they still matter much more often than any one of the four symbols at the narrow end. Board: bar — a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)); heading\_distribution — a Heading that says "The Same Symbols, Different Likelihoods"; regions — a Polygon \[red\] drawn in bar (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45); labels — a Point \[red\] labelled "A thin 40%" drawn in bar (location=(20.0, 0.5), show\_marker=False); regions\_2 — a Polygon \[blue\] drawn in bar (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45); labels\_2 — a Point \[blue\] labelled "B thin 20%" drawn in bar (location=(50.0, 0.5), show\_marker=False) Actions: - [02:24.752](https://academa.ai/lectures/entropy-as-twenty-questions?t=144.75229166666668): regions\_3 is shown on the screen, written out. - [02:24.752](https://academa.ai/lectures/entropy-as-twenty-questions?t=144.75229166666668): labels\_3 is shown on the screen, written out. - [02:24.752](https://academa.ai/lectures/entropy-as-twenty-questions?t=144.75229166666668): distribution is shown on the screen, written out. - [02:25.24](https://academa.ai/lectures/entropy-as-twenty-questions?t=145.24029166666668): regions\_4 is shown on the screen, written out. - [02:25.24](https://academa.ai/lectures/entropy-as-twenty-questions?t=145.24029166666668): labels\_4 is shown on the screen, written out. - [02:25.24](https://academa.ai/lectures/entropy-as-twenty-questions?t=145.24029166666668): distribution is shown on the screen, written out. ##### [02:35.209](https://academa.ai/lectures/entropy-as-twenty-questions?t=155.20929166666667) Narration: The final four slices are equal and rare. Each accounts for only one twentieth of the messages. Board: bar — a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)); heading\_distribution — a Heading that says "The Same Symbols, Different Likelihoods"; regions — a Polygon \[red\] drawn in bar (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45); labels — a Point \[red\] labelled "A thin 40%" drawn in bar (location=(20.0, 0.5), show\_marker=False); regions\_2 — a Polygon \[blue\] drawn in bar (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45); labels\_2 — a Point \[blue\] labelled "B thin 20%" drawn in bar (location=(50.0, 0.5), show\_marker=False); regions\_3 — a Polygon \[green\] drawn in bar (vertices=((60.0, 0.0), (70.0, 0.0), (70.0, 1.0), (60.0, 1.0)), fill\_opacity=0.45); labels\_3 — a Point \[green\] labelled "C thin 10%" drawn in bar (location=(65.0, 0.5), show\_marker=False); regions\_4 — a Polygon \[green\] drawn in bar (vertices=((70.0, 0.0), (80.0, 0.0), (80.0, 1.0), (70.0, 1.0)), fill\_opacity=0.45); labels\_4 — a Point \[green\] labelled "D thin 10%" drawn in bar (location=(75.0, 0.5), show\_marker=False) Actions: - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): regions\_5 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): labels\_5 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): regions\_6 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): labels\_6 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): regions\_7 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): labels\_7 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): regions\_8 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): labels\_8 is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): distribution is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): distribution is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): distribution is shown on the screen, written out. - [02:36.115](https://academa.ai/lectures/entropy-as-twenty-questions?t=156.11529166666668): distribution is shown on the screen, written out. ##### [02:42.334](https://academa.ai/lectures/entropy-as-twenty-questions?t=162.33429166666667) Narration: If we keep the old balanced tree, every outcome still costs three questions. That treats a five-percent event exactly like the event that appears forty percent of the time. Board: bar — a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)); heading\_distribution — a Heading that says "The Same Symbols, Different Likelihoods"; regions — a Polygon \[red\] drawn in bar (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45); labels — a Point \[red\] labelled "A thin 40%" drawn in bar (location=(20.0, 0.5), show\_marker=False); regions\_2 — a Polygon \[blue\] drawn in bar (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45); labels\_2 — a Point \[blue\] labelled "B thin 20%" drawn in bar (location=(50.0, 0.5), show\_marker=False); regions\_3 — a Polygon \[green\] drawn in bar (vertices=((60.0, 0.0), (70.0, 0.0), (70.0, 1.0), (60.0, 1.0)), fill\_opacity=0.45); labels\_3 — a Point \[green\] labelled "C thin 10%" drawn in bar (location=(65.0, 0.5), show\_marker=False); regions\_4 — a Polygon \[green\] drawn in bar (vertices=((70.0, 0.0), (80.0, 0.0), (80.0, 1.0), (70.0, 1.0)), fill\_opacity=0.45); labels\_4 — a Point \[green\] labelled "D thin 10%" drawn in bar (location=(75.0, 0.5), show\_marker=False); regions\_5 — a Polygon \[yellow\] drawn in bar (vertices=((80.0, 0.0), (85.0, 0.0), (85.0, 1.0), (80.0, 1.0)), fill\_opacity=0.45); labels\_5 — a Point \[yellow\] labelled "E thin 5%" drawn in bar (location=(82.5, 0.5), show\_marker=False); regions\_6 — a Polygon \[yellow\] drawn in bar (vertices=((85.0, 0.0), (90.0, 0.0), (90.0, 1.0), (85.0, 1.0)), fill\_opacity=0.45); labels\_6 — a Point \[yellow\] labelled "F thin 5%" drawn in bar (location=(87.5, 0.5), show\_marker=False); regions\_7 — a Polygon \[yellow\] drawn in bar (vertices=((90.0, 0.0), (95.0, 0.0), (95.0, 1.0), (90.0, 1.0)), fill\_opacity=0.45); labels\_7 — a Point \[yellow\] labelled "G thin 5%" drawn in bar (location=(92.5, 0.5), show\_marker=False); regions\_8 — a Polygon \[yellow\] drawn in bar (vertices=((95.0, 0.0), (100.0, 0.0), (100.0, 1.0), (95.0, 1.0)), fill\_opacity=0.45); labels\_8 — a Point \[yellow\] labelled "H thin 5%" drawn in bar (location=(97.5, 0.5), show\_marker=False) Actions: - [02:48.743](https://academa.ai/lectures/entropy-as-twenty-questions?t=168.7432916666667): distribution (the "row=6" part) is emphasized. - [02:51.483](https://academa.ai/lectures/entropy-as-twenty-questions?t=171.48329166666667): distribution (the "row=2" part) is emphasized. - [02:51.483](https://academa.ai/lectures/entropy-as-twenty-questions?t=171.48329166666667): distribution (the "row=6" part) is no longer emphasized. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): bar is hidden from the screen — left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_2 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_2 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_3 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_3 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_4 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_4 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_5 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_5 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_6 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_6 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_7 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_7 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): regions\_8 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): labels\_8 is hidden from the screen — bar left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): distribution is hidden from the screen — left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): heading\_distribution is hidden from the screen — left the board. - [02:53.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.1432916666667): distribution (the "row=2" part) is no longer emphasized. ##### [02:53.743](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.7432916666667) Narration: Instead, ask the most useful question first: is the symbol A? When the answer is yes, which happens forty percent of the time, the search ends after one bit. Board: Empty. Actions: - [02:53.743](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.7432916666667): heading\_plan is shown on the screen, written out. - [02:53.743](https://academa.ai/lectures/entropy-as-twenty-questions?t=173.7432916666667): plan is shown on the screen, written out. - [02:58.178](https://academa.ai/lectures/entropy-as-twenty-questions?t=178.17829166666667): plan is shown on the screen, written out. - [03:3.658](https://academa.ai/lectures/entropy-as-twenty-questions?t=183.65829166666668): plan (the "1" part) is indicated — a transient flash. ##### [03:5.198](https://academa.ai/lectures/entropy-as-twenty-questions?t=185.1982916666667) Narration: If it was not A, the next question can separate B. B then takes two answers. The commonest sixty percent of all symbols have received the two shortest paths. Board: heading\_plan — a Heading that says "Spend Short Answers on Likely Symbols" Actions: - [03:8.159](https://academa.ai/lectures/entropy-as-twenty-questions?t=188.1592916666667): plan is shown on the screen, written out. - [03:10.202](https://academa.ai/lectures/entropy-as-twenty-questions?t=190.2022916666667): plan (the "2" part) is emphasized. - [03:15.915](https://academa.ai/lectures/entropy-as-twenty-questions?t=195.9147916666667): plan (the "2" part) is no longer emphasized. ##### [03:16.515](https://academa.ai/lectures/entropy-as-twenty-questions?t=196.5147916666667) Narration: The price is that C and D now require four questions. That sounds worse than the old three, but each of those symbols appears only one time in ten. Board: Unchanged from the preceding beat in this scene. Actions: - [03:17.71](https://academa.ai/lectures/entropy-as-twenty-questions?t=197.7102916666667): plan is shown on the screen, written out. - [03:18.151](https://academa.ai/lectures/entropy-as-twenty-questions?t=198.1512916666667): plan is shown on the screen, written out. - [03:19.08](https://academa.ai/lectures/entropy-as-twenty-questions?t=199.0802916666667): plan (the "row=4" part) is emphasized. - [03:19.08](https://academa.ai/lectures/entropy-as-twenty-questions?t=199.0802916666667): plan (the "row=5" part) is emphasized. - [03:23.573](https://academa.ai/lectures/entropy-as-twenty-questions?t=203.5732916666667): plan (the "row=4" part) is no longer emphasized. - [03:25.965](https://academa.ai/lectures/entropy-as-twenty-questions?t=205.9652916666667): plan (the "row=5" part) is no longer emphasized. ##### [03:26.565](https://academa.ai/lectures/entropy-as-twenty-questions?t=206.5652916666667) Narration: The four rarest outcomes take five questions each. Long answers are not free, but we pay for them on only twenty percent of the symbols. Board: Unchanged from the preceding beat in this scene. Actions: - [03:27.087](https://academa.ai/lectures/entropy-as-twenty-questions?t=207.0872916666667): plan is shown on the screen, written out. - [03:27.087](https://academa.ai/lectures/entropy-as-twenty-questions?t=207.0872916666667): plan is shown on the screen, written out. - [03:27.087](https://academa.ai/lectures/entropy-as-twenty-questions?t=207.0872916666667): plan is shown on the screen, written out. - [03:27.087](https://academa.ai/lectures/entropy-as-twenty-questions?t=207.0872916666667): plan is shown on the screen, written out. - [03:28.492](https://academa.ai/lectures/entropy-as-twenty-questions?t=208.4922916666667): plan (the "column=3" part) is emphasized. - [03:35.099](https://academa.ai/lectures/entropy-as-twenty-questions?t=215.0987916666667): plan (the "column=3" part) is no longer emphasized. ##### [03:35.699](https://academa.ai/lectures/entropy-as-twenty-questions?t=215.6987916666667) Narration: Now average the question counts using their probabilities. A contributes point four times one. B contributes point two times two. C and D together contribute point two times four, and the rare group contributes point two times five. Board: Unchanged from the preceding beat in this scene. Actions: - [03:36.256](https://academa.ai/lectures/entropy-as-twenty-questions?t=216.2562916666667): expected\_work is shown on the screen, written out. - [03:39.402](https://academa.ai/lectures/entropy-as-twenty-questions?t=219.40229166666668): expected\_work (the "0.4(1)" part) is emphasized. - [03:41.887](https://academa.ai/lectures/entropy-as-twenty-questions?t=221.88729166666667): expected\_work (the "0.2(2)" part) is emphasized. - [03:41.887](https://academa.ai/lectures/entropy-as-twenty-questions?t=221.88729166666667): expected\_work (the "0.4(1)" part) is no longer emphasized. - [03:44.441](https://academa.ai/lectures/entropy-as-twenty-questions?t=224.44129166666667): expected\_work (the "0.2(2)" part) is no longer emphasized. - [03:44.441](https://academa.ai/lectures/entropy-as-twenty-questions?t=224.44129166666667): expected\_work (the "0.2(4)" part) is emphasized. - [03:47.935](https://academa.ai/lectures/entropy-as-twenty-questions?t=227.93529166666667): expected\_work (the "0.2(4)" part) is no longer emphasized. - [03:47.935](https://academa.ai/lectures/entropy-as-twenty-questions?t=227.93529166666667): expected\_work (the "0.2(5)" part) is emphasized. - [03:50.49](https://academa.ai/lectures/entropy-as-twenty-questions?t=230.49029166666668): expected\_work (the "0.2(5)" part) is no longer emphasized. ##### [03:51.09](https://academa.ai/lectures/entropy-as-twenty-questions?t=231.0902916666667) Narration: The result is two point six questions per symbol. Some individual outcomes became more expensive, but the outcomes we see most often became much cheaper. Board: Unchanged from the preceding beat in this scene. Actions: - [03:51.636](https://academa.ai/lectures/entropy-as-twenty-questions?t=231.6362916666667): expected\_work is shown on the screen, written out. - [03:52.205](https://academa.ai/lectures/entropy-as-twenty-questions?t=232.20529166666668): expected\_work (the "2.60" part) is indicated — a transient flash. ##### [04:1.106](https://academa.ai/lectures/entropy-as-twenty-questions?t=241.10579166666668) Narration: The equal-depth plan cost exactly three questions. Exploiting likelihood saves point four of a question per symbol on average. Over a million symbols, that becomes roughly four hundred thousand fewer binary answers. Board: Unchanged from the preceding beat in this scene. Actions: - [04:6.086](https://academa.ai/lectures/entropy-as-twenty-questions?t=246.08629166666668): comparison is shown on the screen, written out. - [04:8.478](https://academa.ai/lectures/entropy-as-twenty-questions?t=248.4782916666667): A box is drawn around comparison. - [04:14.6](https://academa.ai/lectures/entropy-as-twenty-questions?t=254.59962500000003): comparison is hidden from the screen — left the board. - [04:14.6](https://academa.ai/lectures/entropy-as-twenty-questions?t=254.59962500000003): expected\_work is hidden from the screen — left the board. - [04:14.6](https://academa.ai/lectures/entropy-as-twenty-questions?t=254.59962500000003): heading\_plan is hidden from the screen — left the board. - [04:14.6](https://academa.ai/lectures/entropy-as-twenty-questions?t=254.59962500000003): plan is hidden from the screen — left the board. ### Scene 3: [From Question Counts to Entropy](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667) Span: 04:15.641–06:57.784 (255.6412916666667s–417.7835625s). #### Objects - block\_bits: a Math \[text\] that says "$log\_2 2^(n H) = n H thin upright("bits")$" - block\_count: a Math \[text\] that says "$2^(n H) thin upright("typical length-n messages")$" - c2: a Math \[text\] that says "$I(p) = -log\_2 p$" - contributions: a Table \[text\] that says "Group Probability each Ideal bits Total contribution A 0.40 1.322 0.529 B 0.20 2.322 0.464 C, D 0.10 3.322 0.664 E, F, G, H 0.05 4.322 0.864" (rows=(('Group', 'Probability each', 'Ideal bits', 'Total contributio…, header=True) - count\_derivation: a Derivation \[text\] that says "$2^q approx frac(1, p) \\ q approx log\_2 frac(1, p) \\ I(p) = -log\_2 p$" - entropy\_formula: a Math \[text\] that says "$H = sum\_i p\_i log\_2 frac(1, p\_i)$" - entropy\_value: a Math \[text\] that says "$H approx 2.522 thin upright("bits per symbol")$" - fractional\_note: a Text \[text\] that says "An ideal length may be fractional. It is a long-run average target, not a literal fraction of one yes-or-no answer." - heading\_blocks: a Heading that says "Count Long Messages Instead of Single Symbols" - heading\_entropy: a Heading that says "Average the Ideal Question Count" - heading\_ideal: a Heading that says "How Many Halves Reach Probability $p$?" - mass: a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)) - pieces: a Polygon \[red\] drawn in mass (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45) - pieces\_2: a Polygon \[blue\] drawn in mass (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45) - pieces\_3: a Polygon \[green\] drawn in mass (vertices=((60.0, 0.0), (70.0, 0.0), (70.0, 1.0), (60.0, 1.0)), fill\_opacity=0.45) - pieces\_4: a Polygon \[green\] drawn in mass (vertices=((70.0, 0.0), (80.0, 0.0), (80.0, 1.0), (70.0, 1.0)), fill\_opacity=0.45) - pieces\_5: a Polygon \[yellow\] drawn in mass (vertices=((80.0, 0.0), (85.0, 0.0), (85.0, 1.0), (80.0, 1.0)), fill\_opacity=0.45) - pieces\_6: a Polygon \[yellow\] drawn in mass (vertices=((85.0, 0.0), (90.0, 0.0), (90.0, 1.0), (85.0, 1.0)), fill\_opacity=0.45) - pieces\_7: a Polygon \[yellow\] drawn in mass (vertices=((90.0, 0.0), (95.0, 0.0), (95.0, 1.0), (90.0, 1.0)), fill\_opacity=0.45) - pieces\_8: a Polygon \[yellow\] drawn in mass (vertices=((95.0, 0.0), (100.0, 0.0), (100.0, 1.0), (95.0, 1.0)), fill\_opacity=0.45) #### Beats ##### [04:15.641](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667) Narration: For eight equal outcomes, three halvings isolate one outcome because one eighth equals one over two cubed. Now replace one eighth by a general probability p. Board: Empty. Actions: - [04:15.641](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667): heading\_ideal is shown on the screen, written out. - [04:15.641](https://academa.ai/lectures/entropy-as-twenty-questions?t=255.6412916666667): mass is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_2 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_3 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_4 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_5 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_6 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_7 is shown on the screen, written out. - [04:24.221](https://academa.ai/lectures/entropy-as-twenty-questions?t=264.2212916666667): pieces\_8 is shown on the screen, written out. ##### [04:26.121](https://academa.ai/lectures/entropy-as-twenty-questions?t=266.1212916666667) Narration: Imagine a very large collection of equally detailed possibilities. An event with probability p occupies the fraction p of them. To isolate that fraction by balanced binary questions, we keep halving. Board: mass — a Figure (x\_range=(0.0, 100.0), y\_range=(0.0, 1.5), aspect=(10.0, 2.0)); heading\_ideal — a Heading that says "How Many Halves Reach Probability $p$?"; pieces — a Polygon \[red\] drawn in mass (vertices=((0.0, 0.0), (40.0, 0.0), (40.0, 1.0), (0.0, 1.0)), fill\_opacity=0.45); pieces\_2 — a Polygon \[blue\] drawn in mass (vertices=((40.0, 0.0), (60.0, 0.0), (60.0, 1.0), (40.0, 1.0)), fill\_opacity=0.45); pieces\_3 — a Polygon \[green\] drawn in mass (vertices=((60.0, 0.0), (70.0, 0.0), (70.0, 1.0), (60.0, 1.0)), fill\_opacity=0.45); pieces\_4 — a Polygon \[green\] drawn in mass (vertices=((70.0, 0.0), (80.0, 0.0), (80.0, 1.0), (70.0, 1.0)), fill\_opacity=0.45); pieces\_5 — a Polygon \[yellow\] drawn in mass (vertices=((80.0, 0.0), (85.0, 0.0), (85.0, 1.0), (80.0, 1.0)), fill\_opacity=0.45); pieces\_6 — a Polygon \[yellow\] drawn in mass (vertices=((85.0, 0.0), (90.0, 0.0), (90.0, 1.0), (85.0, 1.0)), fill\_opacity=0.45); pieces\_7 — a Polygon \[yellow\] drawn in mass (vertices=((90.0, 0.0), (95.0, 0.0), (95.0, 1.0), (90.0, 1.0)), fill\_opacity=0.45); pieces\_8 — a Polygon \[yellow\] drawn in mass (vertices=((95.0, 0.0), (100.0, 0.0), (100.0, 1.0), (95.0, 1.0)), fill\_opacity=0.45) Actions: - [04:33.273](https://academa.ai/lectures/entropy-as-twenty-questions?t=273.2732916666667): pieces is indicated — a transient flash. ##### [04:40.143](https://academa.ai/lectures/entropy-as-twenty-questions?t=280.1427916666667) Narration: After q balanced questions, one answer path identifies about one part in two to the q. To match an event occupying fraction p, two to the q must be about one over p. Board: Unchanged from the preceding beat in this scene. Actions: - [04:44.88](https://academa.ai/lectures/entropy-as-twenty-questions?t=284.88029166666666): mass moves to a new place on the board. - [04:44.88](https://academa.ai/lectures/entropy-as-twenty-questions?t=284.88029166666666): count\_derivation is shown on the screen, written out. - [04:44.88](https://academa.ai/lectures/entropy-as-twenty-questions?t=284.88029166666666): count\_derivation (the "2^q" part) is indicated — a transient flash. - [04:51.323](https://academa.ai/lectures/entropy-as-twenty-questions?t=291.3232916666667): count\_derivation (the "frac(1, p)" part) is indicated — a transient flash. ##### [04:53.328](https://academa.ai/lectures/entropy-as-twenty-questions?t=293.3282916666667) Narration: Solve for q. The ideal question count is log base two of one over p. Equivalently, it is minus log base two of p. Board: Unchanged from the preceding beat in this scene. Actions: - [04:53.665](https://academa.ai/lectures/entropy-as-twenty-questions?t=293.6652916666667): count\_derivation is shown on the screen, written out. - [04:58.878](https://academa.ai/lectures/entropy-as-twenty-questions?t=298.87829166666666): count\_derivation is shown on the screen, written out. ##### [05:3.025](https://academa.ai/lectures/entropy-as-twenty-questions?t=303.0247916666667) Narration: This quantity measures surprise. A likely event has a large p and a small information value. A rare event has a small p and needs a longer answer path to distinguish it. Board: Unchanged from the preceding beat in this scene. Actions: - [05:5.851](https://academa.ai/lectures/entropy-as-twenty-questions?t=305.85129166666667): pieces is indicated — a transient flash. - [05:10.554](https://academa.ai/lectures/entropy-as-twenty-questions?t=310.5542916666667): pieces\_8 is indicated — a transient flash. ##### [05:15.937](https://academa.ai/lectures/entropy-as-twenty-questions?t=315.9372916666667) Narration: For A, p is point four, so the ideal length is about one point three two two bits. For a five-percent symbol, it is about four point three two two bits. These are not yet legal single-symbol code lengths. Board: Unchanged from the preceding beat in this scene. Actions: - [05:18.747](https://academa.ai/lectures/entropy-as-twenty-questions?t=318.7472916666667): count\_derivation is indicated — a transient flash. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): count\_derivation is hidden from the screen — left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): heading\_ideal is hidden from the screen — left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): mass is hidden from the screen — left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_2 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_3 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_4 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_5 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_6 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_7 is hidden from the screen — mass left the board. - [05:30.74](https://academa.ai/lectures/entropy-as-twenty-questions?t=330.7402916666667): pieces\_8 is hidden from the screen — mass left the board. ##### [05:31.94](https://academa.ai/lectures/entropy-as-twenty-questions?t=331.94029166666667) Narration: A single binary question cannot be split into a fraction. But across a long stream, common and rare symbols can share a description strategy, and a fractional average becomes meaningful. Board: Empty. Actions: - [05:31.94](https://academa.ai/lectures/entropy-as-twenty-questions?t=331.94029166666667): heading\_entropy is shown on the screen, written out. - [05:41.808](https://academa.ai/lectures/entropy-as-twenty-questions?t=341.8082916666667): fractional\_note is shown on the screen, written out. ##### [05:44.893](https://academa.ai/lectures/entropy-as-twenty-questions?t=344.8927916666667) Narration: To find the ideal average, weight each symbol's question count by the probability of seeing that symbol, then add. This weighted average is the quantity we call entropy. Board: fractional\_note — a Text \[text\] that says "An ideal length may be fractional. It is a long-run average target, not a literal fraction of one yes-or-no answer."; heading\_entropy — a Heading that says "Average the Ideal Question Count" Actions: - [05:46.53](https://academa.ai/lectures/entropy-as-twenty-questions?t=346.5302916666667): entropy\_formula is shown on the screen, written out. - [05:47.459](https://academa.ai/lectures/entropy-as-twenty-questions?t=347.4592916666667): entropy\_formula (the "log\_2 frac(1, p\_i)" part) is emphasized. - [05:48.457](https://academa.ai/lectures/entropy-as-twenty-questions?t=348.4572916666667): entropy\_formula (the "log\_2 frac(1, p\_i)" part) is no longer emphasized. - [05:48.457](https://academa.ai/lectures/entropy-as-twenty-questions?t=348.4572916666667): entropy\_formula (the "p\_i" part) is emphasized. - [05:54.936](https://academa.ai/lectures/entropy-as-twenty-questions?t=354.93579166666666): entropy\_formula (the "p\_i" part) is no longer emphasized. ##### [05:55.536](https://academa.ai/lectures/entropy-as-twenty-questions?t=355.5357916666667) Narration: Now calculate it for our distribution. A contributes about point five two nine bits per source symbol. That is its ideal length multiplied by the forty-percent frequency with which we pay it. Board: entropy\_formula — a Math \[text\] that says "$H = sum\_i p\_i log\_2 frac(1, p\_i)$"; fractional\_note — a Text \[text\] that says "An ideal length may be fractional. It is a long-run average target, not a literal fraction of one yes-or-no answer."; heading\_entropy — a Heading that says "Average the Ideal Question Count" Actions: - [05:56.151](https://academa.ai/lectures/entropy-as-twenty-questions?t=356.1512916666667): contributions is shown on the screen, written out. - [05:58.473](https://academa.ai/lectures/entropy-as-twenty-questions?t=358.4732916666667): contributions is shown on the screen, written out. - [05:59.564](https://academa.ai/lectures/entropy-as-twenty-questions?t=359.5642916666667): contributions (the "0.529" part) is emphasized. - [06:7.099](https://academa.ai/lectures/entropy-as-twenty-questions?t=367.0992916666667): contributions (the "0.529" part) is no longer emphasized. ##### [06:7.699](https://academa.ai/lectures/entropy-as-twenty-questions?t=367.6992916666667) Narration: B contributes about point four six four. C and D together contribute about point six six four. Board: Unchanged from the preceding beat in this scene. Actions: - [06:8.047](https://academa.ai/lectures/entropy-as-twenty-questions?t=368.0472916666667): contributions is shown on the screen, written out. - [06:9.36](https://academa.ai/lectures/entropy-as-twenty-questions?t=369.3602916666667): contributions (the "0.464" part) is indicated — a transient flash. - [06:11.182](https://academa.ai/lectures/entropy-as-twenty-questions?t=371.1822916666667): contributions is shown on the screen, written out. - [06:13.47](https://academa.ai/lectures/entropy-as-twenty-questions?t=373.4702916666667): contributions (the "0.664" part) is indicated — a transient flash. ##### [06:15.533](https://academa.ai/lectures/entropy-as-twenty-questions?t=375.5327916666667) Narration: The four five-percent symbols each carry more surprise, and together they contribute about point eight six four bits. Adding every group gives an entropy of about two point five two two bits per symbol. Board: Unchanged from the preceding beat in this scene. Actions: - [06:16.067](https://academa.ai/lectures/entropy-as-twenty-questions?t=376.06729166666673): contributions is shown on the screen, written out. - [06:25.749](https://academa.ai/lectures/entropy-as-twenty-questions?t=385.7492916666667): entropy\_value is shown on the screen, written out. - [06:27.526](https://academa.ai/lectures/entropy-as-twenty-questions?t=387.5262916666667): A box is drawn around entropy\_value. - [06:28.501](https://academa.ai/lectures/entropy-as-twenty-questions?t=388.5012916666667): contributions is hidden from the screen — left the board. - [06:28.501](https://academa.ai/lectures/entropy-as-twenty-questions?t=388.5012916666667): entropy\_formula is hidden from the screen — left the board. - [06:28.501](https://academa.ai/lectures/entropy-as-twenty-questions?t=388.5012916666667): entropy\_value is hidden from the screen — left the board. - [06:28.501](https://academa.ai/lectures/entropy-as-twenty-questions?t=388.5012916666667): fractional\_note is hidden from the screen — left the board. - [06:28.501](https://academa.ai/lectures/entropy-as-twenty-questions?t=388.5012916666667): heading\_entropy is hidden from the screen — left the board. ##### [06:29.701](https://academa.ai/lectures/entropy-as-twenty-questions?t=389.7012916666667) Narration: Here is another way to read the same number. In a long block of n symbols, the probability pattern concentrates most messages among roughly two to the n H typical sequences. Board: Empty. Actions: - [06:29.701](https://academa.ai/lectures/entropy-as-twenty-questions?t=389.7012916666667): heading\_blocks is shown on the screen, written out. - [06:38.408](https://academa.ai/lectures/entropy-as-twenty-questions?t=398.4082916666667): block\_count is shown on the screen, written out. ##### [06:41.703](https://academa.ai/lectures/entropy-as-twenty-questions?t=401.7027916666667) Narration: Distinguishing that many likely messages needs about the log of their count, which is n H binary answers. Entropy is therefore not an arbitrary formula. It is the question count forced by the number of likely messages. Board: block\_count — a Math \[text\] that says "$2^(n H) thin upright("typical length-n messages")$"; heading\_blocks — a Heading that says "Count Long Messages Instead of Single Symbols" Actions: - [06:45.255](https://academa.ai/lectures/entropy-as-twenty-questions?t=405.2552916666667): block\_bits is shown on the screen, written out. - [06:46.799](https://academa.ai/lectures/entropy-as-twenty-questions?t=406.7992916666667): A box is drawn around block\_bits. - [06:56.742](https://academa.ai/lectures/entropy-as-twenty-questions?t=416.7418958333334): block\_bits is hidden from the screen — left the board. - [06:56.742](https://academa.ai/lectures/entropy-as-twenty-questions?t=416.7418958333334): block\_count is hidden from the screen — left the board. - [06:56.742](https://academa.ai/lectures/entropy-as-twenty-questions?t=416.7418958333334): heading\_blocks is hidden from the screen — left the board. ### Scene 4: [Build the Huffman Tree](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625) Span: 06:57.784–09:29.11 (417.7835625s–569.1103333333333s). #### Objects - average\_work: a Derivation \[text\] that says "$L = 0.40(1) + 0.20(2) + 0.20(4) + 0.20(5) \\ L = 2.60 thin upright("bits per symbol")$" - codes: a Table \[text\] that says "Symbol Probability Code Length A 0.40 0 1 B 0.20 10 2 C 0.10 1100 4 D 0.10 1101 4 E 0.05 11100 5 F 0.05 11101 5 G 0.05 11110 5 H 0.05 11111 5" (rows=(('Symbol', 'Probability', 'Code', 'Length'), ('A', '0.40', '0'…, header=True) - edge\_40: a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 3.0)) - edge\_40\_2: a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 1.25)) - edge\_60: a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 4.05)) - edge\_60\_2: a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 2.05)) - edge\_cd: a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)) - edge\_cd\_2: a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)) - edge\_ef: a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)) - edge\_ef\_2: a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)) - edge\_efgh: a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)) - edge\_efgh\_2: a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)) - edge\_gh: a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)) - edge\_gh\_2: a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)) - edge\_root: a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 5.35)) - edge\_root\_2: a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 2.55)) - heading\_build: a Heading that says "Merge the Two Rarest, Again and Again" - heading\_code: a Heading that says "Read Zero and One from Root to Leaf" - leaf\_a: a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)) - leaf\_b: a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)) - leaf\_c: a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)) - leaf\_d: a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)) - leaf\_e: a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)) - leaf\_f: a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)) - leaf\_g: a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)) - leaf\_h: a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)) - merges: a Table \[text\] that says "Step Two smallest weights Merged weight 1 E 5 + F 5 10 2 G 5 + H 5 10 3 C 10 + D 10 20 4 10 + 10 20 5 20 + 20 40 6 B 20 + 40 60 7 A 40 + 60 100" (rows=(('Step', 'Two smallest weights', 'Merged weight'), ('1', 'E 5 …, header=True) - node\_40: a Point \[yellow\] labelled "40" drawn in tree (location=(3.35, 2.05)) - node\_60: a Point \[yellow\] labelled "60" drawn in tree (location=(2.0, 2.55)) - node\_cd: a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)) - node\_ef: a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)) - node\_efgh: a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)) - node\_gh: a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)) - node\_root: a Point \[red\] labelled "100" drawn in tree (location=(0.55, 3.0)) - tree: a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)) #### Beats ##### [06:57.784](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625) Narration: Huffman coding turns the probability list into a binary tree. Begin with one leaf for every symbol. The only repeated instruction is to merge the two smallest weights. Board: Empty. Actions: - [06:57.784](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625): heading\_build is shown on the screen, written out. - [06:57.784](https://academa.ai/lectures/entropy-as-twenty-questions?t=417.7835625): merges is shown on the screen, written out. - [07:1.093](https://academa.ai/lectures/entropy-as-twenty-questions?t=421.09256250000004): tree is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_a is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_b is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_c is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_d is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_e is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_f is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_g is shown on the screen, written out. - [07:3.113](https://academa.ai/lectures/entropy-as-twenty-questions?t=423.1125625): leaf\_h is shown on the screen, written out. ##### [07:9.552](https://academa.ai/lectures/entropy-as-twenty-questions?t=429.55206250000003) Narration: The first two rarest leaves are E and F, each with weight five. Join them under a new node of weight ten. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)) Actions: - [07:10.087](https://academa.ai/lectures/entropy-as-twenty-questions?t=430.0865625): merges is shown on the screen, written out. - [07:14.649](https://academa.ai/lectures/entropy-as-twenty-questions?t=434.6485625): edge\_ef is shown on the screen, written out. - [07:14.649](https://academa.ai/lectures/entropy-as-twenty-questions?t=434.6485625): edge\_ef\_2 is shown on the screen, written out. - [07:17.18](https://academa.ai/lectures/entropy-as-twenty-questions?t=437.17956250000003): node\_ef is shown on the screen, written out. ##### [07:18.581](https://academa.ai/lectures/entropy-as-twenty-questions?t=438.58106250000003) Narration: G and H are the next equal pair. Merge their five-percent weights into a second node of weight ten. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)) Actions: - [07:18.93](https://academa.ai/lectures/entropy-as-twenty-questions?t=438.92956250000003): merges is shown on the screen, written out. - [07:22.099](https://academa.ai/lectures/entropy-as-twenty-questions?t=442.0985625): edge\_gh is shown on the screen, written out. - [07:22.099](https://academa.ai/lectures/entropy-as-twenty-questions?t=442.0985625): edge\_gh\_2 is shown on the screen, written out. - [07:25.153](https://academa.ai/lectures/entropy-as-twenty-questions?t=445.15256250000004): node\_gh is shown on the screen, written out. ##### [07:26.484](https://academa.ai/lectures/entropy-as-twenty-questions?t=446.4835625) Narration: C and D each have weight ten. Merge those two leaves into a node of weight twenty. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)) Actions: - [07:26.786](https://academa.ai/lectures/entropy-as-twenty-questions?t=446.7855625): merges is shown on the screen, written out. - [07:29.816](https://academa.ai/lectures/entropy-as-twenty-questions?t=449.8155625): edge\_cd is shown on the screen, written out. - [07:29.816](https://academa.ai/lectures/entropy-as-twenty-questions?t=449.8155625): edge\_cd\_2 is shown on the screen, written out. - [07:32.219](https://academa.ai/lectures/entropy-as-twenty-questions?t=452.2185625): node\_cd is shown on the screen, written out. ##### [07:33.736](https://academa.ai/lectures/entropy-as-twenty-questions?t=453.7360625) Narration: The two ten-weight branches made from E through H are now the smallest pair. Their merge produces another weight twenty. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)) Actions: - [07:34.247](https://academa.ai/lectures/entropy-as-twenty-questions?t=454.24656250000004): merges is shown on the screen, written out. - [07:39.158](https://academa.ai/lectures/entropy-as-twenty-questions?t=459.15756250000004): edge\_efgh is shown on the screen, written out. - [07:39.158](https://academa.ai/lectures/entropy-as-twenty-questions?t=459.15756250000004): edge\_efgh\_2 is shown on the screen, written out. - [07:40.493](https://academa.ai/lectures/entropy-as-twenty-questions?t=460.4925625): node\_efgh is shown on the screen, written out. ##### [07:42.01](https://academa.ai/lectures/entropy-as-twenty-questions?t=462.0100625) Narration: Three weights of twenty are available. Ties may be resolved consistently in more than one way. Merge these two compound branches to make forty. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)); node\_efgh — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)); edge\_efgh — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)); edge\_efgh\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)) Actions: - [07:48.582](https://academa.ai/lectures/entropy-as-twenty-questions?t=468.5815625): merges is shown on the screen, written out. - [07:50.648](https://academa.ai/lectures/entropy-as-twenty-questions?t=470.6475625): node\_40 is shown on the screen, written out. - [07:50.648](https://academa.ai/lectures/entropy-as-twenty-questions?t=470.6475625): edge\_40 is shown on the screen, written out. - [07:50.648](https://academa.ai/lectures/entropy-as-twenty-questions?t=470.6475625): edge\_40\_2 is shown on the screen, written out. ##### [07:52.107](https://academa.ai/lectures/entropy-as-twenty-questions?t=472.10706250000004) Narration: B has weight twenty and the compound branch has weight forty. They are the two smallest remaining items, so their parent has weight sixty. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)); node\_efgh — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)); edge\_efgh — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)); edge\_efgh\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)); node\_40 — a Point \[yellow\] labelled "40" drawn in tree (location=(3.35, 2.05)); edge\_40 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 3.0)); edge\_40\_2 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 1.25)) Actions: - [07:52.456](https://academa.ai/lectures/entropy-as-twenty-questions?t=472.45556250000004): merges is shown on the screen, written out. - [07:59.248](https://academa.ai/lectures/entropy-as-twenty-questions?t=479.2475625): edge\_60 is shown on the screen, written out. - [07:59.248](https://academa.ai/lectures/entropy-as-twenty-questions?t=479.2475625): edge\_60\_2 is shown on the screen, written out. - [08:0.06](https://academa.ai/lectures/entropy-as-twenty-questions?t=480.0595625): node\_60 is shown on the screen, written out. ##### [08:1.542](https://academa.ai/lectures/entropy-as-twenty-questions?t=481.54206250000004) Narration: Finally merge A, with weight forty, and the remaining weight sixty. Their root has weight one hundred, and the Huffman tree is complete. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); heading\_build — a Heading that says "Merge the Two Rarest, Again and Again"; leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)); node\_efgh — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)); edge\_efgh — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)); edge\_efgh\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)); node\_40 — a Point \[yellow\] labelled "40" drawn in tree (location=(3.35, 2.05)); edge\_40 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 3.0)); edge\_40\_2 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 1.25)); node\_60 — a Point \[yellow\] labelled "60" drawn in tree (location=(2.0, 2.55)); edge\_60 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 4.05)); edge\_60\_2 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 2.05)) Actions: - [08:1.891](https://academa.ai/lectures/entropy-as-twenty-questions?t=481.8905625): merges is shown on the screen, written out. - [08:2.39](https://academa.ai/lectures/entropy-as-twenty-questions?t=482.3895625): edge\_root is shown on the screen, written out. - [08:2.39](https://academa.ai/lectures/entropy-as-twenty-questions?t=482.3895625): edge\_root\_2 is shown on the screen, written out. - [08:7.092](https://academa.ai/lectures/entropy-as-twenty-questions?t=487.0915625): node\_root is shown on the screen, written out. - [08:10.598](https://academa.ai/lectures/entropy-as-twenty-questions?t=490.59756250000004): tree moves to a new place on the board. - [08:10.598](https://academa.ai/lectures/entropy-as-twenty-questions?t=490.59756250000004): heading\_build is hidden from the screen — left the board. - [08:10.598](https://academa.ai/lectures/entropy-as-twenty-questions?t=490.59756250000004): merges is hidden from the screen — left the board. - [08:10.598](https://academa.ai/lectures/entropy-as-twenty-questions?t=490.59756250000004): codes is shown on the screen, written out. ##### [08:11.798](https://academa.ai/lectures/entropy-as-twenty-questions?t=491.7975625) Narration: Assign zero to the upper branch and one to the lower branch at each split. A codeword is the sequence encountered while walking from the root to a leaf. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)); node\_efgh — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)); edge\_efgh — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)); edge\_efgh\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)); node\_40 — a Point \[yellow\] labelled "40" drawn in tree (location=(3.35, 2.05)); edge\_40 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 3.0)); edge\_40\_2 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 1.25)); node\_60 — a Point \[yellow\] labelled "60" drawn in tree (location=(2.0, 2.55)); edge\_60 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 4.05)); edge\_60\_2 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 2.05)); node\_root — a Point \[red\] labelled "100" drawn in tree (location=(0.55, 3.0)); edge\_root — a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 5.35)); edge\_root\_2 — a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 2.55)) Actions: - [08:11.798](https://academa.ai/lectures/entropy-as-twenty-questions?t=491.7975625): heading\_code is shown on the screen, written out. - [08:19.566](https://academa.ai/lectures/entropy-as-twenty-questions?t=499.5655625): node\_root is indicated — a transient flash. ##### [08:21.605](https://academa.ai/lectures/entropy-as-twenty-questions?t=501.60456250000004) Narration: A is reached immediately by code zero, so the most likely symbol costs only one bit. B follows one then zero, so it costs two bits. Board: tree — a Figure (x\_range=(0.0, 8.2), y\_range=(0.0, 6.0), aspect=(4.0, 3.0)); leaf\_a — a Point \[blue\] labelled "A thin 40%" drawn in tree (location=(2.0, 5.35)); leaf\_b — a Point \[blue\] labelled "B thin 20%" drawn in tree (location=(3.35, 4.05)); leaf\_c — a Point \[blue\] labelled "C thin 10%" drawn in tree (location=(6.05, 3.45)); leaf\_d — a Point \[blue\] labelled "D thin 10%" drawn in tree (location=(6.05, 2.65)); leaf\_e — a Point \[blue\] labelled "E thin 5%" drawn in tree (location=(7.45, 1.95)); leaf\_f — a Point \[blue\] labelled "F thin 5%" drawn in tree (location=(7.45, 1.35)); leaf\_g — a Point \[blue\] labelled "G thin 5%" drawn in tree (location=(7.45, 0.85)); leaf\_h — a Point \[blue\] labelled "H thin 5%" drawn in tree (location=(7.45, 0.25)); node\_ef — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 1.65)); edge\_ef — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.95)); edge\_ef\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 1.65), end=(7.45, 1.35)); node\_gh — a Point \[yellow\] labelled "10" drawn in tree (location=(6.05, 0.75)); edge\_gh — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.85)); edge\_gh\_2 — a Line \[yellow\] drawn in tree (start=(6.05, 0.75), end=(7.45, 0.25)); node\_cd — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 3.0)); edge\_cd — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 3.45)); edge\_cd\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 3.0), end=(6.05, 2.65)); node\_efgh — a Point \[yellow\] labelled "20" drawn in tree (location=(4.75, 1.25)); edge\_efgh — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 1.65)); edge\_efgh\_2 — a Line \[yellow\] drawn in tree (start=(4.75, 1.25), end=(6.05, 0.75)); node\_40 — a Point \[yellow\] labelled "40" drawn in tree (location=(3.35, 2.05)); edge\_40 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 3.0)); edge\_40\_2 — a Line \[yellow\] drawn in tree (start=(3.35, 2.05), end=(4.75, 1.25)); node\_60 — a Point \[yellow\] labelled "60" drawn in tree (location=(2.0, 2.55)); edge\_60 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 4.05)); edge\_60\_2 — a Line \[yellow\] drawn in tree (start=(2.0, 2.55), end=(3.35, 2.05)); node\_root — a Point \[red\] labelled "100" drawn in tree (location=(0.55, 3.0)); edge\_root — a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 5.35)); edge\_root\_2 — a Line \[red\] drawn in tree (start=(0.55, 3.0), end=(2.0, 2.55)); heading\_code — a Heading that says "Read Zero and One from Root to Leaf" Actions: - [08:21.953](https://academa.ai/lectures/entropy-as-twenty-questions?t=501.9525625): codes is shown on the screen, written out. - [08:23.857](https://academa.ai/lectures/entropy-as-twenty-questions?t=503.8565625): codes (the "0" part) is emphasized. - [08:27.608](https://academa.ai/lectures/entropy-as-twenty-questions?t=507.60756250000003): codes is shown on the screen, written out. - [08:27.608](https://academa.ai/lectures/entropy-as-twenty-questions?t=507.60756250000003): codes (the "0" part) is no longer emphasized. - [08:28.339](https://academa.ai/lectures/entropy-as-twenty-questions?t=508.3385625): codes (the "10" part) is emphasized. - [08:31.16](https://academa.ai/lectures/entropy-as-twenty-questions?t=511.1595625): codes (the "10" part) is no longer emphasized. ##### [08:31.76](https://academa.ai/lectures/entropy-as-twenty-questions?t=511.7595625) Narration: C and D sit deeper, with codes one one zero zero and one one zero one. Each requires four bits. Board: Unchanged from the preceding beat in this scene. Actions: - [08:32.108](https://academa.ai/lectures/entropy-as-twenty-questions?t=512.1075625): codes is shown on the screen, written out. - [08:32.55](https://academa.ai/lectures/entropy-as-twenty-questions?t=512.5495625): codes is shown on the screen, written out. - [08:38.923](https://academa.ai/lectures/entropy-as-twenty-questions?t=518.9225625): codes (the "column=4" part) is indicated — a transient flash. ##### [08:40.602](https://academa.ai/lectures/entropy-as-twenty-questions?t=520.6020625) Narration: The four rarest symbols lie one level deeper still. Their codes share the prefix one one one, then use two more bits to select the leaf. Board: Unchanged from the preceding beat in this scene. Actions: - [08:41.137](https://academa.ai/lectures/entropy-as-twenty-questions?t=521.1365625000001): codes is shown on the screen, written out. - [08:41.137](https://academa.ai/lectures/entropy-as-twenty-questions?t=521.1365625000001): codes is shown on the screen, written out. - [08:41.137](https://academa.ai/lectures/entropy-as-twenty-questions?t=521.1365625000001): codes is shown on the screen, written out. - [08:41.137](https://academa.ai/lectures/entropy-as-twenty-questions?t=521.1365625000001): codes is shown on the screen, written out. - [08:45.398](https://academa.ai/lectures/entropy-as-twenty-questions?t=525.3975625): codes (the "column=3" part) is emphasized. - [08:49.31](https://academa.ai/lectures/entropy-as-twenty-questions?t=529.3095625000001): codes (the "column=3" part) is no longer emphasized. ##### [08:49.91](https://academa.ai/lectures/entropy-as-twenty-questions?t=529.9095625) Narration: No codeword is the beginning of another codeword. That prefix property lets a decoder read the stream from left to right and know exactly when each symbol ends. Board: Unchanged from the preceding beat in this scene. Actions: - [08:50.468](https://academa.ai/lectures/entropy-as-twenty-questions?t=530.4675625): codes (the "0" part) is indicated — a transient flash. - [08:51.594](https://academa.ai/lectures/entropy-as-twenty-questions?t=531.5935625000001): codes (the "10" part) is indicated — a transient flash. ##### [08:59.983](https://academa.ai/lectures/entropy-as-twenty-questions?t=539.9830625000001) Narration: Compute the average length. A pays one bit forty percent of the time. B pays two bits twenty percent of the time. C and D pay four, and the final four symbols pay five. Board: Unchanged from the preceding beat in this scene. Actions: - [09:0.912](https://academa.ai/lectures/entropy-as-twenty-questions?t=540.9115625000001): average\_work is shown on the screen, written out. - [09:2.305](https://academa.ai/lectures/entropy-as-twenty-questions?t=542.3045625): average\_work (the "0.40(1)" part) is emphasized. - [09:5.347](https://academa.ai/lectures/entropy-as-twenty-questions?t=545.3465625): average\_work (the "0.20(2)" part) is emphasized. - [09:5.347](https://academa.ai/lectures/entropy-as-twenty-questions?t=545.3465625): average\_work (the "0.40(1)" part) is no longer emphasized. - [09:8.656](https://academa.ai/lectures/entropy-as-twenty-questions?t=548.6555625000001): average\_work (the "0.20(2)" part) is no longer emphasized. - [09:8.656](https://academa.ai/lectures/entropy-as-twenty-questions?t=548.6555625000001): average\_work (the "0.20(4)" part) is emphasized. - [09:10.525](https://academa.ai/lectures/entropy-as-twenty-questions?t=550.5245625): average\_work (the "0.20(4)" part) is no longer emphasized. - [09:10.525](https://academa.ai/lectures/entropy-as-twenty-questions?t=550.5245625): average\_work (the "0.20(5)" part) is emphasized. - [09:12.627](https://academa.ai/lectures/entropy-as-twenty-questions?t=552.6265625000001): average\_work (the "0.20(5)" part) is no longer emphasized. ##### [09:13.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=553.2265625) Narration: The Huffman code therefore uses two point six bits per symbol on average. The merging rule has recovered the likelihood-aware question plan, and it has guaranteed that no other binary prefix code has a smaller average length for these individual symbols. Board: Unchanged from the preceding beat in this scene. Actions: - [09:15.317](https://academa.ai/lectures/entropy-as-twenty-questions?t=555.3165625): average\_work is shown on the screen, written out. - [09:17.163](https://academa.ai/lectures/entropy-as-twenty-questions?t=557.1625625): A box is drawn around average\_work. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): average\_work is hidden from the screen — left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): codes is hidden from the screen — left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): heading\_code is hidden from the screen — left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): tree is hidden from the screen — left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_a is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_b is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_c is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_d is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_e is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_f is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_g is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): leaf\_h is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_ef is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_ef is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_ef\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_gh is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_gh is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_gh\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_cd is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_cd is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_cd\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_efgh is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_efgh is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_efgh\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_40 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_40 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_40\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_60 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_60 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_60\_2 is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): node\_root is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_root is hidden from the screen — tree left the board. - [09:28.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=568.0686666666667): edge\_root\_2 is hidden from the screen — tree left the board. ### Scene 5: [The Bound and the Files We Compress](https://academa.ai/lectures/entropy-as-twenty-questions?t=569.1103333333333) Span: 09:29.11–14:24.679 (569.1103333333333s–864.6787291666667s). #### Objects - block\_note: a Text \[text\] that says "Coding longer blocks makes the one-bit rounding allowance apply to an entire block, so its cost per source symbol can become arbitrarily small." - bound\_result: a Math \[text\] that says "$L \>= H$" - bound\_work: a Derivation \[text\] that says "$sum\_i 2^(-l\_i) \<= 1 \\ L-H &= sum\_i p\_i log\_2 frac(p\_i, 2^(-l\_i)) \\ &\>= -log\_2 (sum\_i 2^(-l\_i)) \\ &\>= 0$" - capacity\_note: a Text \[text\] that says "A codeword of length $l\_i$ occupies the fraction $2^(-l\_i)$ of a complete binary tree. Prefix-free leaves cannot overlap." - english: a Table \[text\] that says "Property Typical English text Distribution Uneven Context Strong dependencies Redundancy Letters and phrases predictable Entropy Below 8 bits per byte Compression Usually substantial" (rows=(('Property', 'Typical English text'), ('Distribution', 'Uneven…, header=True) - english\_label: a Tex \[text\] that says "Structured text" - entropy\_point: a Point \[red\] labelled "H = 2.522" drawn in scale (location=(2.522, 0.0)) - entropy\_value: a Math \[text\] that says "$H approx 2.522$" - gap\_value: a Math \[text\] that says "$L - H approx 0.078 thin upright("bit per symbol")$" - heading: a Heading that says "Why Huffman Gets So Close" - heading\_2: a Heading that says "Why Random Data Has No General Shortcut" - heading\_bound: a Heading that says "Why a Lossless Prefix Code Cannot Beat $H$" - heading\_compare: a Heading that says "Ideal Limit and Achievable Code" - heading\_files: a Heading that says "Why Some Files Shrink and Others Do Not" - heading\_recap: a Heading that says "The Compression Story" - huffman\_bound: a Math \[text\] that says "$H \<= L\_(upright("Huffman")) \< H + 1$" - huffman\_point: a Point \[green\] labelled "L = 2.600" drawn in scale (location=(2.6, 0.0)) - huffman\_value: a Math \[text\] that says "$L\_(upright("Huffman")) = 2.600$" - pigeonhole: a Math \[text\] that says "$2^(8n) thin upright("input files") \> sum\_(j=0)^(8n-1) 2^j thin upright("shorter strings")$" - random: a Table \[text\] that says "Property Independent random bytes Distribution Uniform over 256 values Context No predictive dependence Redundancy None on average Entropy 8 bits per byte Compression None on average" (rows=(('Property', 'Independent random bytes'), ('Distribution', 'Un…, header=True) - random\_count: a Math \[text\] that says "$256 = 2^8$" - random\_entropy: a Math \[text\] that says "$H = log\_2 256 = 8 thin upright("bits per byte")$" - random\_label: a Tex \[text\] that says "Uniform random bytes" - recap\_four: a Text \[text\] that says "4. Predictability creates the room that compression uses." - recap\_one: a Text \[text\] that says "1. A bit answers one binary question." - recap\_three: a Text \[text\] that says "3. Huffman coding gives likely symbols shorter paths." - recap\_two: a Text \[text\] that says "2. Entropy is the ideal average number of such questions." - scale: a NumberLine labelled "upright("bits per symbol")" (x\_range=(2.4, 3.0), include\_numbers=True, ticks\_every=0.1) #### Beats ##### [09:29.11](https://academa.ai/lectures/entropy-as-twenty-questions?t=569.1103333333333) Narration: Put the two numbers on one scale. Entropy for our source is about two point five two two bits per symbol. The Huffman code uses two point six. Board: Empty. Actions: - [09:29.11](https://academa.ai/lectures/entropy-as-twenty-questions?t=569.1103333333333): heading\_compare is shown on the screen, written out. - [09:30.41](https://academa.ai/lectures/entropy-as-twenty-questions?t=570.4103333333333): scale is shown on the screen, written out. - [09:31.711](https://academa.ai/lectures/entropy-as-twenty-questions?t=571.7113333333333): entropy\_point is shown on the screen, written out. - [09:33.232](https://academa.ai/lectures/entropy-as-twenty-questions?t=573.2323333333333): scale moves to a new place on the board. - [09:33.232](https://academa.ai/lectures/entropy-as-twenty-questions?t=573.2323333333333): entropy\_value is shown on the screen, written out. - [09:35.948](https://academa.ai/lectures/entropy-as-twenty-questions?t=575.9483333333333): huffman\_point is shown on the screen, written out. - [09:37.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=577.1093333333333): huffman\_value is shown on the screen, written out. ##### [09:38.998](https://academa.ai/lectures/entropy-as-twenty-questions?t=578.9983333333333) Narration: The gap is only point zero seven eight of a bit per symbol. Huffman coding is not merely better than the fixed three-bit code. It is very close to the information-theoretic target. Board: entropy\_value — a Math \[text\] that says "$H approx 2.522$"; huffman\_value — a Math \[text\] that says "$L\_(upright("Huffman")) = 2.600$"; scale — a NumberLine labelled "upright("bits per symbol")" (x\_range=(2.4, 3.0), include\_numbers=True, ticks\_every=0.1); heading\_compare — a Heading that says "Ideal Limit and Achievable Code"; entropy\_point — a Point \[red\] labelled "H = 2.522" drawn in scale (location=(2.522, 0.0)); huffman\_point — a Point \[green\] labelled "L = 2.600" drawn in scale (location=(2.6, 0.0)) Actions: - [09:39.416](https://academa.ai/lectures/entropy-as-twenty-questions?t=579.4163333333333): gap\_value is shown on the screen, written out. - [09:47.671](https://academa.ai/lectures/entropy-as-twenty-questions?t=587.6713333333333): The segment (2.522, 0.0) to (2.6, 0.0) in scale is lit up. - [09:50.132](https://academa.ai/lectures/entropy-as-twenty-questions?t=590.1323333333333): scale: retire a lit segment (unemphasize\_line). ##### [09:50.732](https://academa.ai/lectures/entropy-as-twenty-questions?t=590.7323333333333) Narration: Two questions remain. Why can no lossless prefix code move the green point to the left of entropy? And if the bound is unbeatable, why is Huffman allowed to sit slightly above it? Board: entropy\_value — a Math \[text\] that says "$H approx 2.522$"; huffman\_value — a Math \[text\] that says "$L\_(upright("Huffman")) = 2.600$"; gap\_value — a Math \[text\] that says "$L - H approx 0.078 thin upright("bit per symbol")$"; scale — a NumberLine labelled "upright("bits per symbol")" (x\_range=(2.4, 3.0), include\_numbers=True, ticks\_every=0.1); heading\_compare — a Heading that says "Ideal Limit and Achievable Code"; entropy\_point — a Point \[red\] labelled "H = 2.522" drawn in scale (location=(2.522, 0.0)); huffman\_point — a Point \[green\] labelled "L = 2.600" drawn in scale (location=(2.6, 0.0)) Actions: - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): entropy\_value is hidden from the screen — left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): gap\_value is hidden from the screen — left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): heading\_compare is hidden from the screen — left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): huffman\_value is hidden from the screen — left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): scale is hidden from the screen — left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): entropy\_point is hidden from the screen — scale left the board. - [10:3.109](https://academa.ai/lectures/entropy-as-twenty-questions?t=603.1088333333333): huffman\_point is hidden from the screen — scale left the board. ##### [10:4.309](https://academa.ai/lectures/entropy-as-twenty-questions?t=604.3088333333333) Narration: A binary prefix code is a set of nonoverlapping leaves in a binary tree. A codeword of length l occupies one part in two to the l of the tree's capacity. Board: Empty. Actions: - [10:4.309](https://academa.ai/lectures/entropy-as-twenty-questions?t=604.3088333333333): heading\_bound is shown on the screen, written out. - [10:14.351](https://academa.ai/lectures/entropy-as-twenty-questions?t=614.3513333333333): capacity\_note is shown on the screen, written out. ##### [10:16.008](https://academa.ai/lectures/entropy-as-twenty-questions?t=616.0078333333333) Narration: Add those occupied fractions over all symbols. They cannot exceed one. This is the tree-capacity inequality, often called Kraft's inequality. Board: capacity\_note — a Text \[text\] that says "A codeword of length $l\_i$ occupies the fraction $2^(-l\_i)$ of a complete binary tree. Prefix-free leaves cannot overlap."; heading\_bound — a Heading that says "Why a Lossless Prefix Code Cannot Beat $H$" Actions: - [10:16.356](https://academa.ai/lectures/entropy-as-twenty-questions?t=616.3563333333333): bound\_work is shown on the screen, written out. - [10:17.471](https://academa.ai/lectures/entropy-as-twenty-questions?t=617.4713333333333): bound\_work (the "2^(-l\_i)" part) is emphasized. - [10:26.527](https://academa.ai/lectures/entropy-as-twenty-questions?t=626.5268333333333): bound\_work (the "2^(-l\_i)" part) is no longer emphasized. ##### [10:27.127](https://academa.ai/lectures/entropy-as-twenty-questions?t=627.1268333333333) Narration: Now compare the actual average length L with entropy H. Their difference can be written as this weighted logarithmic ratio. Board: Unchanged from the preceding beat in this scene. Actions: - [10:32.026](https://academa.ai/lectures/entropy-as-twenty-questions?t=632.0263333333332): bound\_work is shown on the screen, written out. ##### [10:36.214](https://academa.ai/lectures/entropy-as-twenty-questions?t=636.2138333333332) Narration: The log-sum inequality says that weighted ratio is at least minus the log of the tree capacity. Since the capacity is at most one, that quantity is nonnegative. Board: Unchanged from the preceding beat in this scene. Actions: - [10:36.701](https://academa.ai/lectures/entropy-as-twenty-questions?t=636.7013333333333): bound\_work is shown on the screen, written out. - [10:46.523](https://academa.ai/lectures/entropy-as-twenty-questions?t=646.5233333333333): bound\_work is shown on the screen, written out. ##### [10:48.342](https://academa.ai/lectures/entropy-as-twenty-questions?t=648.3423333333333) Narration: Therefore every binary prefix code has average length at least H. Shorter paths for some outcomes consume more tree capacity and force compensating longer paths elsewhere. The average cannot cross the entropy bound. Board: Unchanged from the preceding beat in this scene. Actions: - [10:52.313](https://academa.ai/lectures/entropy-as-twenty-questions?t=652.3133333333333): bound\_result is shown on the screen, written out. - [11:2.448](https://academa.ai/lectures/entropy-as-twenty-questions?t=662.4483333333333): A box is drawn around bound\_result. - [11:3.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.2268333333333): bound\_result is hidden from the screen — left the board. - [11:3.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.2268333333333): bound\_work is hidden from the screen — left the board. - [11:3.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.2268333333333): capacity\_note is hidden from the screen — left the board. - [11:3.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.2268333333333): heading\_bound is hidden from the screen — left the board. ##### [11:3.827](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.8268333333333) Narration: Entropy supplies ideal lengths such as one point three two two bits. Real codewords have whole-number lengths. Huffman chooses those integers optimally, and its average is always less than one bit above entropy for a memoryless symbol source. Board: Empty. Actions: - [11:3.827](https://academa.ai/lectures/entropy-as-twenty-questions?t=663.8268333333333): huffman\_bound is shown on the screen, written out. - [11:12.069](https://academa.ai/lectures/entropy-as-twenty-questions?t=672.0693333333332): huffman\_bound (the "H" part) is indicated — a transient flash. - [11:15.947](https://academa.ai/lectures/entropy-as-twenty-questions?t=675.9473333333333): huffman\_bound (the "H + 1" part) is indicated — a transient flash. ##### [11:20.889](https://academa.ai/lectures/entropy-as-twenty-questions?t=680.8893333333333) Narration: When probabilities are exact powers of one half, the ideal lengths are integers and Huffman can meet entropy exactly. Otherwise it rounds through the tree, as our small point zero seven eight gap demonstrates. Board: huffman\_bound — a Math \[text\] that says "$H \<= L\_(upright("Huffman")) \< H + 1$" Actions: - [11:27.959](https://academa.ai/lectures/entropy-as-twenty-questions?t=687.9593333333332): huffman\_bound is indicated — a transient flash. ##### [11:35.421](https://academa.ai/lectures/entropy-as-twenty-questions?t=695.4208333333333) Narration: There is also a way to make the rounding cost per symbol smaller. Encode blocks of symbols together. One possible extra bit is then shared by the whole block rather than charged to every symbol. Board: Unchanged from the preceding beat in this scene. Actions: - [11:40.436](https://academa.ai/lectures/entropy-as-twenty-questions?t=700.4363333333333): block\_note is shown on the screen, written out. - [11:45.092](https://academa.ai/lectures/entropy-as-twenty-questions?t=705.0923333333333): block\_note (the "entire block" part) is emphasized. - [11:48.145](https://academa.ai/lectures/entropy-as-twenty-questions?t=708.1453333333333): block\_note is hidden from the screen — left the board. - [11:48.145](https://academa.ai/lectures/entropy-as-twenty-questions?t=708.1453333333333): huffman\_bound is hidden from the screen — left the board. - [11:48.145](https://academa.ai/lectures/entropy-as-twenty-questions?t=708.1453333333333): block\_note (the "entire block" part) is no longer emphasized. ##### [11:48.745](https://academa.ai/lectures/entropy-as-twenty-questions?t=708.7453333333333) Narration: Now return to files. Typical English text is structured. Spaces and common letters occur more often than rare punctuation, so even the one-byte distribution is uneven. Board: Empty. Actions: - [11:48.745](https://academa.ai/lectures/entropy-as-twenty-questions?t=708.7453333333333): heading\_files is shown on the screen, written out. - [11:51.705](https://academa.ai/lectures/entropy-as-twenty-questions?t=711.7053333333333): english\_label is shown on the screen, written out. - [11:52.599](https://academa.ai/lectures/entropy-as-twenty-questions?t=712.5993333333333): english is shown on the screen, written out. - [12:0.227](https://academa.ai/lectures/entropy-as-twenty-questions?t=720.2273333333333): english is shown on the screen, written out. ##### [12:1.675](https://academa.ai/lectures/entropy-as-twenty-questions?t=721.6748333333333) Narration: English also has dependencies across positions. After the letters q and u, some next letters are far more plausible than others. Words, phrases, indentation, and repeated substrings create further predictability. Board: english\_label — a Tex \[text\] that says "Structured text"; heading\_files — a Heading that says "Why Some Files Shrink and Others Do Not" Actions: - [12:2.94](https://academa.ai/lectures/entropy-as-twenty-questions?t=722.9403333333332): english is shown on the screen, written out. - [12:15.676](https://academa.ai/lectures/entropy-as-twenty-questions?t=735.6763333333333): english is shown on the screen, written out. ##### [12:17.472](https://academa.ai/lectures/entropy-as-twenty-questions?t=737.4718333333333) Narration: A compressor turns that predictability into short descriptions. Huffman coding exploits a probability distribution. More advanced compressors also exploit context, repeated strings, and predictions from earlier data. Board: Unchanged from the preceding beat in this scene. Actions: - [12:20.084](https://academa.ai/lectures/entropy-as-twenty-questions?t=740.0843333333332): english is shown on the screen, written out. - [12:26.237](https://academa.ai/lectures/entropy-as-twenty-questions?t=746.2373333333333): english is shown on the screen, written out. ##### [12:32.259](https://academa.ai/lectures/entropy-as-twenty-questions?t=752.2588333333333) Narration: Independent random bytes are different. Each of the two hundred fifty-six byte values has probability one over two hundred fifty-six, and the next byte is not predicted by the bytes before it. Board: Unchanged from the preceding beat in this scene. Actions: - [12:33.211](https://academa.ai/lectures/entropy-as-twenty-questions?t=753.2113333333333): random\_label is shown on the screen, written out. - [12:34.139](https://academa.ai/lectures/entropy-as-twenty-questions?t=754.1393333333333): random is shown on the screen, written out. - [12:38.098](https://academa.ai/lectures/entropy-as-twenty-questions?t=758.0983333333332): random is shown on the screen, written out. - [12:42.034](https://academa.ai/lectures/entropy-as-twenty-questions?t=762.0343333333333): random is shown on the screen, written out. ##### [12:44.667](https://academa.ai/lectures/entropy-as-twenty-questions?t=764.6668333333332) Narration: There is no statistical redundancy to exploit. The entropy is eight bits per byte, exactly the size already used by an ordinary byte. Board: english\_label — a Tex \[text\] that says "Structured text"; random\_label — a Tex \[text\] that says "Uniform random bytes"; heading\_files — a Heading that says "Why Some Files Shrink and Others Do Not" Actions: - [12:46.245](https://academa.ai/lectures/entropy-as-twenty-questions?t=766.2453333333333): random is shown on the screen, written out. - [12:49.276](https://academa.ai/lectures/entropy-as-twenty-questions?t=769.2763333333332): random is shown on the screen, written out. - [12:51.377](https://academa.ai/lectures/entropy-as-twenty-questions?t=771.3773333333332): random is shown on the screen, written out. - [12:53.99](https://academa.ai/lectures/entropy-as-twenty-questions?t=773.9898333333333): english is hidden from the screen — left the board. - [12:53.99](https://academa.ai/lectures/entropy-as-twenty-questions?t=773.9898333333333): english\_label is hidden from the screen — left the board. - [12:53.99](https://academa.ai/lectures/entropy-as-twenty-questions?t=773.9898333333333): heading\_files is hidden from the screen — left the board. - [12:53.99](https://academa.ai/lectures/entropy-as-twenty-questions?t=773.9898333333333): random is hidden from the screen — left the board. - [12:53.99](https://academa.ai/lectures/entropy-as-twenty-questions?t=773.9898333333333): random\_label is hidden from the screen — left the board. ##### [12:54.59](https://academa.ai/lectures/entropy-as-twenty-questions?t=774.5898333333332) Narration: There are two hundred fifty-six possible byte values, which is two to the eighth. If they are equally likely, identifying one requires eight bits. Board: Empty. Actions: - [12:55.425](https://academa.ai/lectures/entropy-as-twenty-questions?t=775.4253333333332): random\_count is shown on the screen, written out. - [13:3.204](https://academa.ai/lectures/entropy-as-twenty-questions?t=783.2043333333332): random\_entropy is shown on the screen, written out. ##### [13:4.861](https://academa.ai/lectures/entropy-as-twenty-questions?t=784.8608333333333) Narration: For an n-byte file there are two to the eight n possible inputs. There are not enough shorter binary strings to give every input a unique shorter lossless description. Board: random\_count — a Math \[text\] that says "$256 = 2^8$"; random\_entropy — a Math \[text\] that says "$H = log\_2 256 = 8 thin upright("bits per byte")$" Actions: - [13:10.05](https://academa.ai/lectures/entropy-as-twenty-questions?t=790.0503333333332): pigeonhole is shown on the screen, written out. ##### [13:16.316](https://academa.ai/lectures/entropy-as-twenty-questions?t=796.3163333333332) Narration: Some individual random-looking file may shrink by chance, but most will not, and compressor metadata can make them larger. Already compressed or encrypted files often behave similarly because their byte patterns have been deliberately made difficult to predict. Board: random\_count — a Math \[text\] that says "$256 = 2^8$"; random\_entropy — a Math \[text\] that says "$H = log\_2 256 = 8 thin upright("bits per byte")$"; pigeonhole — a Math \[text\] that says "$2^(8n) thin upright("input files") \> sum\_(j=0)^(8n-1) 2^j thin upright("shorter strings")$" Actions: - [13:32.57](https://academa.ai/lectures/entropy-as-twenty-questions?t=812.5703333333332): pigeonhole is hidden from the screen — left the board. - [13:32.57](https://academa.ai/lectures/entropy-as-twenty-questions?t=812.5703333333332): random\_count is hidden from the screen — left the board. - [13:32.57](https://academa.ai/lectures/entropy-as-twenty-questions?t=812.5703333333332): random\_entropy is hidden from the screen — left the board. ##### [13:33.17](https://academa.ai/lectures/entropy-as-twenty-questions?t=813.1703333333332) Narration: The whole story now fits into four steps. First, a bit is one resolved binary choice. Board: Empty. Actions: - [13:33.17](https://academa.ai/lectures/entropy-as-twenty-questions?t=813.1703333333332): heading\_recap is shown on the screen, written out. - [13:36.584](https://academa.ai/lectures/entropy-as-twenty-questions?t=816.5843333333332): recap\_one is shown on the screen, written out. ##### [13:40.829](https://academa.ai/lectures/entropy-as-twenty-questions?t=820.8293333333332) Narration: Second, repeated halving says an event of probability p carries about log base two of one over p bits. Averaging that surprise gives entropy. Board: recap\_one — a Text \[text\] that says "1. A bit answers one binary question."; heading\_recap — a Heading that says "The Compression Story" Actions: - [13:41.177](https://academa.ai/lectures/entropy-as-twenty-questions?t=821.1773333333333): recap\_two is shown on the screen, written out. ##### [13:52.691](https://academa.ai/lectures/entropy-as-twenty-questions?t=832.6913333333332) Narration: Third, Huffman coding repeatedly merges rare events so likely symbols end near the root. Its integer code lengths approach the entropy limit without ever beating that lower bound. Board: recap\_one — a Text \[text\] that says "1. A bit answers one binary question."; recap\_two — a Text \[text\] that says "2. Entropy is the ideal average number of such questions."; heading\_recap — a Heading that says "The Compression Story" Actions: - [13:53.167](https://academa.ai/lectures/entropy-as-twenty-questions?t=833.1673333333333): recap\_three is shown on the screen, written out. ##### [14:6.039](https://academa.ai/lectures/entropy-as-twenty-questions?t=846.0388333333333) Narration: Finally, compression is possible when data contains predictable structure. English supplies redundancy and context. Independent random bytes do not. Entropy measures that difference, and coding turns the available predictability into fewer stored bits. Board: recap\_one — a Text \[text\] that says "1. A bit answers one binary question."; recap\_two — a Text \[text\] that says "2. Entropy is the ideal average number of such questions."; recap\_three — a Text \[text\] that says "3. Huffman coding gives likely symbols shorter paths."; heading\_recap — a Heading that says "The Compression Story" Actions: - [14:6.387](https://academa.ai/lectures/entropy-as-twenty-questions?t=846.3873333333333): recap\_four is shown on the screen, written out. - [14:21.039](https://academa.ai/lectures/entropy-as-twenty-questions?t=861.0393333333334): A box is drawn around recap\_four. - [14:23.637](https://academa.ai/lectures/entropy-as-twenty-questions?t=863.6370625): heading\_recap is hidden from the screen — left the board. - [14:23.637](https://academa.ai/lectures/entropy-as-twenty-questions?t=863.6370625): recap\_four is hidden from the screen — left the board. - [14:23.637](https://academa.ai/lectures/entropy-as-twenty-questions?t=863.6370625): recap\_one is hidden from the screen — left the board. - [14:23.637](https://academa.ai/lectures/entropy-as-twenty-questions?t=863.6370625): recap\_three is hidden from the screen — left the board. - [14:23.637](https://academa.ai/lectures/entropy-as-twenty-questions?t=863.6370625): recap\_two is hidden from the screen — left the board.