Robot warmup: skewed symbols and prefix codes

A robot on a distant moon sends movement instructions drawn from a small, skewed alphabet. Three students propose encoders: fixed width, variable length matched to frequency, and a theoretical "perfect" scheme .

Variable-length codes must be prefix-free: no codeword can be a prefix of another, or the receiver cannot parse the stream. A tree of codewords yields an average length equal to the weighted sum of depths; for the robot, a tuned tree reaches about 1.75 bits per instruction on average, beating fixed two-bit coding .

The third student asks what any optimal encoder must satisfy: after compression, each new bit should behave like a fair coin flip. Structured skew shows up as bias in the bitstream; true optimality leaves no pattern left to exploit .