10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I assume that by 'efficient' you mean O(n) or thereabouts, ruling out the "repeated random trials" argument ? $\endgroup$ – Suresh Venkat Sep 1 '10 at 8:12
  • $\begingroup$ @Suresh, Would you be able to sketch the "repeated random trials" argument? $\endgroup$ – Emil Sep 1 '10 at 13:53
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 1 '10 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '10 at 22:17
  • $\begingroup$ “Perfectly well-defined” up to possibly different interpretations of “efficiently,” I mean. But this is not the point of my previous comment. $\endgroup$ – Tsuyoshi Ito Sep 2 '10 at 2:14
12
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ b(x) in the 3rd line should be b(y). $\endgroup$ – Emil Sep 1 '10 at 13:42
  • $\begingroup$ 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). $\endgroup$ – Emil Sep 1 '10 at 13:53
  • $\begingroup$ @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$). $\endgroup$ – Jukka Suomela Sep 1 '10 at 13:58
  • $\begingroup$ @Jukka: Ah yes I see. $\endgroup$ – Emil Sep 1 '10 at 14:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Sep 1 '10 at 16:57
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '10 at 14:29
  • $\begingroup$ 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. $\endgroup$ – Piotr Sep 2 '10 at 4:22

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.