ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let XX be a source alphabet with ∣X∣=2|X|=2, consisting of symbols x1x_1 and x2x_2, with probabilities p(x1)\text{p}(x_1) and p(x2)\text{p}(x_2). Let βT\beta_T, β0\beta_0, Rmin∗\mathcal{R}_{\mathrm{min}}^*, R[x1,x2]\mathcal{R}_{[x_1,x_2]}, and F\mathcal{F} denote the quantities defined in the paper, and let Δ\Delta be the set of four codes parameterized by

a∈{⌊−log⁡p(x1)⌋,⌈−log⁡p(x1)⌉},b∈{⌊−log⁡p(x2)⌋,⌈−log⁡p(x2)⌉},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 [x1,x2][x_1,x_2]. The two-symbol minimum-redundancy formula. For ∣X∣=2|X|=2, Rmin∗({x1,x2})\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\}) is given by the following three cases:

  1. If p(x1)+p(x2)=1\text{p}(x_1)+\text{p}(x_2)=1, then
R[x1,x2]({x1,x2}).\mathcal{R}_{[x_1,x_2]}(\{x_1,x_2\}).
  1. If p(x1)+p(x2)<1\text{p}(x_1)+\text{p}(x_2)<1 and p(x1)≥0.5\text{p}(x_1)\geq 0.5 (or symmetrically p(x2)≥0.5\text{p}(x_2)\geq 0.5), then, with p(x′)=p(x2)1−p(x1)\text{p}(x')=\frac{\text{p}(x_2)}{1-\text{p}(x_1)},
Rmin∗({x1,x2})=Rmin∗({x1})+(1−p(x1))Rmin∗({x′}).\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})=\mathcal{R}_{\mathrm{min}}^*(\{x_1\})+(1-\text{p}(x_1))\mathcal{R}_{\mathrm{min}}^*(\{x'\}).
  1. Otherwise,
Rmin∗({x1,x2})=min⁡C∈ΔF({x1,x2},C)\mathcal{R}_{\mathrm{min}}^*(\{x_1,x_2\})=\min_{C\in\Delta}\mathcal{F}(\{x_1,x_2\},C)

and equivalently

Rmin∗({x1,x2})=βTlog⁡βT+min⁡C(a,b)∈Δ{β0−βTlog⁡(1−2−a−2−b)}.\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.