Let X be a source alphabet with ∣X∣=2, consisting of symbols x1 and x2, with probabilities p(x1) and p(x2). Let βT, β0, Rmin∗, R[x1,x2], and F denote the quantities defined in the paper, and let Δ be the set of four codes parameterized by
a∈{⌊−logp(x1)⌋,⌈−logp(x1)⌉},b∈{⌊−logp(x2)⌋,⌈−logp(x2)⌉},
excluding the code [x1,x2]. The two-symbol minimum-redundancy formula. For ∣X∣=2, Rmin∗({x1,x2}) is given by the following three cases:
- If p(x1)+p(x2)=1, then
R[x1,x2]({x1,x2}).
- If p(x1)+p(x2)<1 and p(x1)≥0.5 (or symmetrically p(x2)≥0.5), then, with p(x′)=1−p(x1)p(x2),
Rmin∗({x1,x2})=Rmin∗({x1})+(1−p(x1))Rmin∗({x′}).
- Otherwise,
Rmin∗({x1,x2})=C∈ΔminF({x1,x2},C)
and equivalently
Rmin∗({x1,x2})=βTlogβT+C(a,b)∈Δmin{β0−βTlog(1−2−a−2−b)}.
This gives a purported closed-form characterization of the minimum redundancy for binary Huffman coding. The surrounding discussion presents the formula as a conjectural pattern suggested by numerical contour plots and local minima; the high-probability case is supported by Lemma 1 of MPK06, while the general case remains to be established.