2
$\begingroup$

Consider the following problem:

You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, ..., n \}}$ such that $\forall k \in \{ 1, ..., n \}:l'_k\le l_k$ and $\sum_{k=1}^n2^{-l'_k}=1$.

(For what it's worth, this is a problem arising from Information Theory, where the Kraft-McMillan Theorem gives that the result above yields a more efficient binary code than the one with codeword lengths $(l_k)$.)

Here are my initial thoughts. We can consider $\sum_{k=1}^n2^{-l_k}$ as a binary number e.g. $0.11010011$ and then we need to reduce the value of some $l_k$ values whose digit position is preceded by a $0$. So for instance, with the initial $0$ in the $\frac{1}{8}$ position of the example number I gave, we want to decrease the value of some $l_i=4$ to $l'_i=3$ to add $\frac{1}{8}$ and subtract $\frac{1}{16}$ to the sum. We then have $0.11100011$, so we've moved the problematic $0$ along a digit. When we get to the end we presumably have something like $0.11111110$, and then need to reduce the value of the longest codeword by 1 to get the overflow to $1.00000000$.

However, I encounter two problems: there may not be such an $l_i=4$, for instance, if the $1$ in the $\frac{1}{16}$ digit place arises as the sum of three $l_i=5$ numbers. Additionally, if we multiple have $0$ digits in a row then we presumably need to scan until the next $1$ and then decrement a corresponding $l_i$ multiple times, but it's conceivable that I would "run out" of large enough $l_i$ codewords that I can manipulate in this way.

Can anyone describe an algorithm with a simple proof of correctness?

A follow-up problem: how do we generalise this algorithm to bases other than $2$?

$\endgroup$
3
$\begingroup$

Here is a very simple algorithm. We will require the following lemma.

Lemma. Suppose that $1 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} \geq 1/2$. Then there exists $r \in \{1,\ldots,k\}$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$.

Proof. Let $r$ be the first index such that $\sum_{i=1}^r 2^{-\ell_i} \geq 1/2$. Since the $\ell_i$ are non-decreasing, there are integers $A,B$ such that $$ \begin{align} \sum_{i=1}^{r-1} 2^{-\ell_i} &= \frac{A}{2^{\ell_r}}, & \sum_{i=1}^r 2^{-\ell_i} &= \frac{B}{2^{\ell_r}}. \end{align} $$ Moreover, $A < 2^{\ell_r-1}$ and $B \geq 2^{\ell_r-1}$. Since $B-A=1$, we conclude that $B = 2^{\ell_r-1}$, and so $\sum_{i=1}^r 2^{-\ell_i} = 1/2$. $\quad\square$

This suggests the following algorithm. We can assume that your sequence is sorted, that is, we are given a sequence $\ell_1 \leq \cdots \leq \ell_k$ such that $\sum_{i=1}^k 2^{-\ell_i} \leq 1$. We now consider three cases:

  1. $\sum_{i=1}^k 2^{-\ell_i} = 1$. In this case, there is nothing to do.
  2. $\sum_{i=1}^k 2^{-\ell_i} \leq 1/2$. In this case, we can decrease each $\ell_i$ by $1$.
  3. $1/2 \leq \sum_{i=1}^k 2^{-\ell_i} \leq 1$. Applying the lemma, we find $r$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$, and so $\sum_{i=r+1}^k 2^{-\ell_i} \leq 1/2$. We thus have to solve the same kind of problem for the second half $\ell_{r+1},\ldots,\ell_k$, aiming at $1/2$ rather than $1$.

To implement this recursion more cleanly, we add a parameter $s$, and our goal is to correct a sequence satisfying $\sum_i 2^{-\ell_i} \leq 2^{-s}$ to one satisfying $\sum_i 2^{-\ell_i} = 2^{-s}$ by only decreasing elements.


Here is how the algorithm works in the case of the sequence $1,2,4,7,8$, which matches your example. The sum in your case is more than $1/2$, so we separate the sequence into two parts: $1$ and $2,4,7,8$. We only handle the second, aiming at a sum of $1/2$.

The sum in the case of $2,4,7,8$ is more than $1/4$, so we separate the sequence into two parts, $2$ and $4,7,8$, and only handle the second, aiming at a sum of $1/4$.

The sum in the case of $4,7,8$ is less than $1/8$, so we decrement each element, obtaining the sequence $3,6,7$, whose sum is more than $1/8$. We separate it into $3$ and $6,7$, and only handle the second, aiming at a sum of $1/8$.

We decrement $6,7$ twice, obtaining the sequence $4,5$ whose sum exceeds $1/16$. We separate it into $4$ and $5$, and decrement the latter once.

Putting everything together, we obtain the sequence $1,2,3,4,4$.


In the $q$-ary case, we have to change the problem somehow, since the result is not true in general. For example, take $q = 3$ and consider the sequence $1, 1$.


Here is another simple algorithm, based on the following lemma.

Lemma. Suppose that $0 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} < 1$. Then $\sum_{i=1}^{k-1} 2^{-\ell_i} + 2^{-(\ell_k-1)} \leq 1$.

Proof. Since the $\ell_i$ are nondecreasing, we can write $\sum_{i=1}^k 2^{-\ell_i} = A/2^{\ell_k}$, where $A < 2^{\ell_k}$. Replacing $\ell_k$ with $\ell_k-1$ increases the sum by $1/2^{\ell_k}$. Since $A+1 \leq 2^{\ell_k}$, the sum remains at most $1$. $\quad\square$

This suggests the following simple algorithm: repeatedly decrement the largest $\ell_i$. The algorithm necessarily terminates since at most $\sum_i \ell_i$ iterations can take place.

Let us apply this on our example above: $$ \begin{align} &1,2,4,7,8 \to 1,2,4,7,7 \to 1,2,4,6,7 \to 1,2,4,6,6 \to 1,2,4,5,6 \to \\ &1,2,4,5,5 \to 1,2,4,4,5 \to 1,2,4,4,4 \to 1,2,3,4,4 \end{align} $$ This algorithm can be implemented easily using a heap. However, it is slower (in general) than the preceding algorithm, if the latter is implemented correctly. For example, the sequence $\ell$ takes $\ell$ steps in this algorithm, but could be handled by a single iteration of the preceding algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.