Fractional bits

It takes \(\log_2(8) = 3\) bits of data to carry one mes­sage from a set of 8 pos­si­ble mes­sages. Similarly, it takes \(\log_2(1024) = 10\) bits to carry one mes­sage from a set of 1024 pos­si­bil­ities. How many bits does it take to carry one mes­sage from a set of 3 pos­si­bil­ities? By the defi­ni­tion of “bit,” the an­swers is \(\log_2(3) \approx 1.58.\) What does this mean? That it takes about one and a half yes-or-no ques­tions to sin­gle out one thing from a set of three? What is “half of a yes-or-no ques­tion”?

Frac­tional bits can be in­ter­preted as tel­ling about the ex­pected cost of trans­mit­ting in­for­ma­tion: If you want to sin­gle out one thing from a set of 3 us­ing bits (in, e.g., the GalCom thought ex­per­i­ment) then you’ll have to pur­chase two bits, but some­times you’ll be able to sell one of them back, which means you can push your ex­pected cost lower than 2. How low can you push it? The lower bound is \(\log_2(3),\) which is the min­i­mum ex­pected cost of adding a 3-mes­sage to a long mes­sage when en­cod­ing your mes­sage as clev­erly as pos­si­ble. For more on this in­ter­pre­ta­tion, see Frac­tional bits: Ex­pected cost in­ter­pre­ta­tion.

Frac­tional bits can also be in­ter­preted as con­ver­sion rates be­tween types of in­for­ma­tion: “A 3-mes­sage car­ries about 1.58 bits” can be in­ter­preted as “one Trit is worth about 1.58 bits.” To un­der­stand this, see Ex­change rates be­tween digits, or How many bits is a trit?

Frac­tional units of data can also be in­ter­preted as a mea­sure of how much we’re us­ing the digits al­lo­cated to en­cod­ing a num­ber. For ex­am­ple, work­ing with frac­tional decits in­stead of frac­tional bits, it only takes about 2.7 decits carry a 500-mes­sage, de­spite the fact that the num­ber 500 clearly re­quires 3 dec­i­mal digits to write down. What’s go­ing on here? Well, we could de­clare that all num­bers that start with a num­ber \(n \ge 5\) will be in­ter­preted as if they start with the num­ber \(n - 5.\) Then we have two ways of rep­re­sent­ing each num­ber (for ex­am­ple, 132 can be rep­re­sented as both 132 and 632). Thus, if we have 3 decits but we only need to en­code a 500-mes­sage, we have one bit to spare: We can en­code one ex­tra bit in our mes­sage ac­cord­ing to whether we use the low rep­re­sen­ta­tion or the high rep­re­sen­ta­tion of the in­tended num­ber. Thus, the amount of data it takes to com­mu­ni­cate a 500-mes­sage is one bit lower than the amount of data it takes to en­code a 1000-mes­sage — for a to­tal cost of 3 decits minus one bit, which comes out to about 2.70 decits (or just short of 9 bits). For more on this in­ter­pre­ta­tion, see Frac­tional digits.