<p>This answer does not quite answer the question.  Rather, it describes a trivial solution and shows that it is close to optimal.  FWIW I <em>conjecture</em> that the solution is actually optimal.</p>
<hr />
<p>Let <span class="math-container">$n$</span> be the number of symbols given.
Consider the code where <span class="math-container">$s_n = 0^{n-1}$</span> and <span class="math-container">$s_i = 0^{i-1}1$</span> for <span class="math-container">$i&lt;n$</span>.
It has <span class="math-container">$N_1 = n-1$</span> and <span class="math-container">$N_0=n(n-1)/2$</span>.
By calculation its ratio is
<span class="math-container">$$\frac{N_0N_1}{N_0+N_1} = n - 3 + \frac{6}{n+2}.$$</span></p>
<hr />
<p>I conjecture this is optimal.  It is easy to show it is nearly optimal:</p>
<p><strong>Lemma 1.</strong> <em>For any code, the ratio <span class="math-container">$N_0N_1/N$</span> is at least <span class="math-container">$n - O(n/\log n)$</span>.</em></p>
<p><em>Proof.</em>  The ratio is <span class="math-container">$N_0(N-N_0)/N$</span>.  Any code has at most one all-0 codeword and at most one all-1 codeword, so <span class="math-container">$n-1 \le N_0 \le N-(n-1)$</span>.  Also, <span class="math-container">$N \ge n \log_2 n$</span> (as any binary tree with <span class="math-container">$n$</span> leaves has average leaf depth at least <span class="math-container">$\log_2 n$</span>).  So the ratio is at least
<span class="math-container">$$\frac{(n-1)(N - (n-1))}{N} = n - 1 - \frac{(n-1)^2}{N} = n - O(n/\log n).~~~~~~\Box$$</span></p>

CC BY-SA 4.0
2022-11-02T06:27:12.063Z
Thank you for the analysis. In fact I have thought of this solution, but the problem is that the code is too long. If we impose an upper-bound on the code length, I suppose the solution will be to make the codes the most unbalanced possible.
lchen
CC BY-SA 4.0
2022-11-02T15:10:49.287Z
Ah, well that would be a different question.  You could make another post, I guess.
Neal Young
CC BY-SA 4.0
2022-10-31T21:19:16.193Z
2022-10-31T21:19:16.193Z
Neal Young
<p>We have a long message <span class="math-container">$m$</span> to encode. The message is composed of a set of symbols <span class="math-container">$\{s_i\}$</span>. Let <span class="math-container">$p_i$</span> denote the number of appearance of <span class="math-container">$s_i$</span> in <span class="math-container">$m$</span>. We seek to find a prefix-free code for each <span class="math-container">$s_i$</span> so as to minimize <span class="math-container">$\frac{N_0N_1}{N}$</span>, where <span class="math-container">$N_0$</span> and <span class="math-container">$N_1$</span> denote the number of bits <span class="math-container">$0$</span> and <span class="math-container">$1$</span> in the coded message, respectively, <span class="math-container">$N=N_0+N_1$</span> denotes the length of the coded message. The prefix-free code system is a set of codes where any code is not a prefix of another. Our problem is to find such optimal coding system. Our problem resembles Huffman coding but with a more complex objective function.</p>

CC BY-SA 4.0
2022-10-30T21:36:07.813Z
I think this question, as stated at least, has a trivial (and practically useless) answer, so is not research-level.  BTW, OP, why do you title it "balancing", when minimizing $N_0 N_1/N$ does the opposite?  And if you meant "maximizing", I think the question would still have a trivial (and practically useless) answer.
Neal Young
CC BY-SA 4.0
2022-10-31T04:22:53.367Z
@NealYoung I am sorry for the typo, it is "unbalancing". I seek to minimize it. What is the trivial solution in this case (minimizing)?
lchen
CC BY-SA 4.0
2022-10-31T21:19:09.633Z
Sorry, my comment was overstated.   I conjecture that my "trivial" solution is optimal, but can only show that it is nearly so.   I'll explain what I had in mind as an answer below.
Neal Young
CC BY-SA 4.0
2022-11-01T16:51:39.820Z
Cross-posted from https://mathoverflow.net/questions/430201/optimal-prefix-free-code-design-with-a-complex-objective-function .
Emil Jeřábek
CC BY-SA 4.0
2022-11-02T15:18:42.723Z
Can you explain more about why you care about this objective function?  It seems quite strange.  It's almost the same as maximizing $\max(N_0, N_1)/\min(N_0, N_1)$, which would be a very strange thing to do.
Neal Young
<ds.algorithms><prefix-free-code>
Prefix free code unbalancing 0 and 1 bits
lchen
# Prefix free code unbalancing 0 and 1 bits

(Asked by: username_0 on 2022-10-30)

We have a long message $m$ to encode. The message is composed of a set of symbols $\{s\_i\}$. Let $p\_i$ denote the number of appearance of $s\_i$ in $m$. We seek to find a prefix-free code for each $s\_i$ so as to minimize $\frac{N\_0N\_1}{N}$, where $N\_0$ and $N\_1$ denote the number of bits $0$ and $1$ in the coded message, respectively, $N=N\_0+N\_1$ denotes the length of the coded message. The prefix-free code system is a set of codes where any code is not a prefix of another. Our problem is to find such optimal coding system. Our problem resembles Huffman coding but with a more complex objective function.

**Tags:** ds.algorithms, prefix-free-code
> **Comments:**
> **username_1**: I think this question, as stated at least, has a trivial (and practically useless) answer, so is not research-level.  BTW, OP, why do you title it "balancing", when minimizing $N_0 N_1/N$ does the opposite?  And if you meant "maximizing", I think the question would still have a trivial (and practically useless) answer.  
> **username_0**: @NealYoung I am sorry for the typo, it is "unbalancing". I seek to minimize it. What is the trivial solution in this case (minimizing)?  
> **username_1**: Sorry, my comment was overstated.   I conjecture that my "trivial" solution is optimal, but can only show that it is nearly so.   I'll explain what I had in mind as an answer below.  
> **username_2**: Cross-posted from https://mathoverflow.net/questions/430201/optimal-prefix-free-code-design-with-a-complex-objective-function .  
> **username_1**: Can you explain more about why you care about this objective function?  It seems quite strange.  It's almost the same as maximizing $\max(N_0, N_1)/\min(N_0, N_1)$, which would be a very strange thing to do.  

---

## 1 answers

### Answer by username_1 on 2022-10-31. Score: 3 | Accepted answer

This answer does not quite answer the question. Rather, it describes a trivial solution and shows that it is close to optimal. FWIW I *conjecture* that the solution is actually optimal.

---

Let $n$ be the number of symbols given.
Consider the code where $s\_n = 0^{n-1}$ and $s\_i = 0^{i-1}1$ for $i.
It has $N\_1 = n-1$ and $N\_0=n(n-1)/2$.
By calculation its ratio is
$$\frac{N\_0N\_1}{N\_0+N\_1} = n - 3 + \frac{6}{n+2}.$$

---

I conjecture this is optimal. It is easy to show it is nearly optimal:

**Lemma 1.** *For any code, the ratio $N\_0N\_1/N$ is at least $n - O(n/\log n)$.*

*Proof.* The ratio is $N\_0(N-N\_0)/N$. Any code has at most one all-0 codeword and at most one all-1 codeword, so $n-1 \le N\_0 \le N-(n-1)$. Also, $N \ge n \log\_2 n$ (as any binary tree with $n$ leaves has average leaf depth at least $\log\_2 n$). So the ratio is at least
$$\frac{(n-1)(N - (n-1))}{N} = n - 1 - \frac{(n-1)^2}{N} = n - O(n/\log n).~~~~~~\Box$$

> **Comments:**
> **username_0**: Thank you for the analysis. In fact I have thought of this solution, but the problem is that the code is too long. If we impose an upper-bound on the code length, I suppose the solution will be to make the codes the most unbalanced possible.  
> **username_1**: Ah, well that would be a different question.  You could make another post, I guess.  

---

