Encoding trits with GalCom bits

There are \(\log_2(3) \approx 1.585\) bits to a Trit. Why is it that par­tic­u­lar value? Con­sider the GalCom thought ex­per­i­ment, in which you make money by send­ing in­for­ma­tion about the stock mar­ket across the ce­les­tial reaches. Let’s say that Com­pany X is about to pub­lish a big earn­ings re­port, and that you want to send a mes­sage to your stock trader in the Vega star sys­tem that says one of three things: “Perfor­mance was in the top 13 of what I ex­pected,” “Perfor­mance was in the mid­dle 13 of what I ex­pected,” or “Perfor­mance was in the bot­tom 13 of what I ex­pected.” You ob­vi­ously don’t want to send whole sen­tences; it suffices to trans­mit a sin­gle Trit of in­for­ma­tion.

That is, if you had con­trol of a com­mu­ni­ca­tion chan­nel that could hold one of three sig­nals (say, a wire that could be pos­i­tively charged, nega­tively charged, or un­charged) which was con­nected to your com­puter on Vega, then you could pro­gram the com­puter to rec­og­nize a pos­i­tive charge as “top 13 perfor­mance”, a neu­tral charge as “mid­dle 13 perfor­mance”, and a nega­tive charge as “bot­tom 13 perfor­mance.” You could then pro­gram it to buy, hold, or sell re­spec­tively, and make your money.

Un­for­tu­nately, you don’t con­trol a wire con­nected to your com­puter on Vega. The com­puter on Vega is in a differ­ent star sys­tem, and the only way to com­mu­ni­cate with it is through GalCom, the galac­tic com­mu­ni­ca­tions net­work. And GalCom doesn’t sell trits (which let you trans­mit one of three mes­sages) it sells bits (which let you trans­mit one of two mes­sages).

So, how many bits on GalCom will it cost you to send your trit?

(You’re in­vited to pause and find some method for en­cod­ing a trit us­ing bits.)

You can eas­ily trans­mit a trit via two bits. If you re­serve two bits on GalCom, you get to con­trol two of the pulses of light on the sender, by choos­ing wether they are pre­sent or ab­sent. This af­fects whether the re­ceiver writes down 0 or 1, and those two bi­nary digits will be sent to your ma­chine on Vega. Thus, if you pur­chase two bits on GalCom, you can send one of four mes­sages to your ma­chine on Vega: 00, 01, 10, or 11. This is more than enough to en­code a trit: You can pro­gram the ma­chine such that 00 causes it to sell, 01 causes it to hold, and 10 causes it to buy. Then you have one code left over, namely 11, that you’ll never send.

One trit encoded, inefficiently, using 2 bits

To en­code a bit us­ing trits, you could pur­chase two bits and then make use of only 3 of the 4 available codes.

How­ever, this is in­effi­cient: You pur­chased one code (11) that you are never us­ing. Is there any way to re­pur­pose this code to make some of your money back?

(You are in­vited to pause and find some method of en­cod­ing a trit us­ing two bits such that, some­times, you’re able to sell one bit back to GalCom and re­cover some of your losses.)

Here’s one thing you could do: Pro­gram your ma­chine on Vega such that it rec­og­nizes both 10 and 11 as “top 13 perfor­mance.”

Encoding a trit using two bits, such that 1/3 of the time you can sell one bit back to GalCom.

Then, by the time you’ve trans­mit­ted a 1, the ma­chine on Vega already knows to start pur­chas­ing stock: It doesn’t need the next bit. This means that it doesn’t mat­ter (to you) whether you send 10 or 11; these are two differ­ent ways of rep­re­sent­ing the same mes­sage. Thus, if Com­pany X has perfor­mance in the top 13 of your ex­pec­ta­tions, you can sell one bit back to GalCom: Send 10 if the next bit they were go­ing to send was a 0, and 11 if the next bit they were go­ing to send was a 1. You’ve just shaved one bit off of the next mes­sage that was go­ing to come through GalCom!

(The above ex­po­si­tion im­plies that you need to know the first bit of the next mes­sage, and that your com­puter on Vega needs to be set up to for­ward the sec­ond bit to where it needs to go. In prac­tice, this sort of thing would be stan­dard op­er­at­ing pro­ce­dure on GalCom, which could use pre­fix free codes to avoid the need for see­ing/​for­ward­ing bits of fol­low­ing mes­sages.)

If you en­code your trit this way, then you re­serve 2 bits in ad­vance, and 13 of the time you get to sell one back. Thus, if you send lots and lots of trits us­ing this en­cod­ing, you only pay \(2 - \frac{1}{3} \approx 1.67\) gal­coins per trit on av­er­age (as­sum­ing, as we should, that each mes­sage oc­curs with equal fre­quency).

Can we do bet­ter? Yes. (TODO)