# Quick encoding of balanced vectors

It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$ efficiently ?

Thanks.

• I assume that by 'efficient' you mean O(n) or thereabouts, ruling out the "repeated random trials" argument ? – Suresh Venkat Sep 1 '10 at 8:12
• @Suresh, Would you be able to sketch the "repeated random trials" argument? – Emil Sep 1 '10 at 13:53
• one way of proving that the mapping exists is by the probabilistic method: pick F at random, and then the mapping works with some probability. that's what I meant. – Suresh Venkat Sep 1 '10 at 16:42
• The question is perfectly well-defined but, in my opinion, the title is misleading. I would not call a mapping F satisfying the stated condition an “encoding of balanced vectors” unless F is bijective. It is more like an encoding of an n-bit string by a balanced vector. – Tsuyoshi Ito Sep 1 '10 at 22:17
• “Perfectly well-defined” up to possibly different interpretations of “efficiently,” I mean. But this is not the point of my previous comment. – Tsuyoshi Ito Sep 2 '10 at 2:14

Let's consider $n$-bit strings $x$. Definitions:

• $f(x,i)$ = bit string $x$ with last $i$ bits complemented.
• $b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.

Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:

• $g(0) = b(x)$.
• $g(n) = -g(0)$.
• $|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.

Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.

Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.

Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.

• b(x) in the 3rd line should be b(y). – Emil Sep 1 '10 at 13:42
• I think that you need to possibly add another bit to the string x to ensure that it has even length (so that you can be sure that g(i) is zero for some i). – Emil Sep 1 '10 at 13:53
• @Emil: I don't claim that $g(i)$ is be zero for some $i$; it is sufficient that the absolute value of $g(i)$ is "fairly small" for some $i$ (at most logarithmic would be enough, but it's easy to show that it will be at most $1$ for some $i$). – Jukka Suomela Sep 1 '10 at 13:58
• @Jukka: Ah yes I see. – Emil Sep 1 '10 at 14:06
• But yes, you are right, there are many variants of the same basic approach. For example, as you suggested, you can first use a padding bit to ensure that $g(i)$ will be equal zero for some $i$; then you can encode $i$ by using bit pairs $01$ or $10$, that is $2\log(n)$ extra bits; then the result of the concatenation is strictly balanced and you don't need to add anything else. – Jukka Suomela Sep 1 '10 at 16:57

Use the mapping that preserves the lexicographical order. To find the $k$-th length-$n$ balanced vector with $n/2$ 1's, do it recursively: if $k\leq{n-1\choose n/2}$, then set the first bit 0 and then find the $k$-th length-$(n-1)$ vector with $n/2$ 1's to complete the remaining $n-1$ bits. Otherwise set the first bit 1 and find the $k-{n-1\choose n/2}$-th length-$(n-1)$ vector with $n/2-1$ 1's.

• And if you reuse the value of a binomial coefficient to compute the next required binomial coefficient, the whole algorithm runs in O(n) time. – Tsuyoshi Ito Sep 1 '10 at 14:29
• Thanks! This makes sense. I guess the running time will depend on the computational model. If you can perform operations on n-bit numbers in unit time, the implementation by Tsuyoshi Ito will run in O(n) time. On the other hand, if you count bit operations, the time will be O(n^2), I think. – Piotr Sep 2 '10 at 4:22