Closed-form expression for the minimum redundancy of binary Huffman codes

Let $X$ be a source alphabet with $|X|=2$, consisting of symbols $x_1$ and $x_2$, with probabilities $\text{p}(x_1)$ and $\text{p}(x_2)$. Let $\beta_T$, $\beta_0$, $\mathcal{R}_{\mathrm{min}}^*$, $\mathcal{R}_{[x_1,x_2]}$, and $\mathcal{F}$ denote the quantities defined in the paper, and let $\Delta$ be the set of four codes parameterized by

$$a \in \{\lfloor-\log\text{p}(x_1)\rfloor,\lceil-\log\text{p}(x_1)\rceil\},\qquad b \in \{\lfloor-\log\text{p}(x_2)\rfloor,\lceil-\log\text{p}(x_2)\rceil\},$$

excluding the code $[x_1,x_2]$. The two-symbol minimum-redundancy formula. For $|X|=2$, $\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})$ is given by the following three cases:

1. If $\text{p}(x_1)+\text{p}(x_2)=1$, then

$$\mathcal{R}_{[x_1,x_2]}(\{x_1,x_2\}).$$

2. If $\text{p}(x_1)+\text{p}(x_2)<1$ and $\text{p}(x_1)\geq 0.5$ (or symmetrically $\text{p}(x_2)\geq 0.5$), then, with $\text{p}(x')=\frac{\text{p}(x_2)}{1-\text{p}(x_1)}$,

$$\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})=\mathcal{R}_{\mathrm{min}}^*(\{x_1\})+(1-\text{p}(x_1))\mathcal{R}_{\mathrm{min}}^*(\{x'\}).$$

3. Otherwise,

$$\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})=\min_{C\in\Delta}\mathcal{F}(\{x_1,x_2\},C)$$

and equivalently

$$\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})=\beta_T\log\beta_T+\min_{C_{(a,b)}\in\Delta}\left\{\beta_0-\beta_T\log\left(1-2^{-a}-2^{-b}\right)\right\}.$$

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.