3
$\begingroup$

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ string permutations (static, chosen beforehand) and then, the cost of an input string $B$ is the minimum cost of the $k$ permutations of $B$.

Given $k$, we want to choose $k$ string permutations in order to minimize the worst case over any input string of length $k$. I have been working on this problem for a couple of weeks and I have found that (almost symmetric) latin squares work quite well. For example, for $k$ = 8, the following set of permutations:

0 1 2 3 4 5 6 7 
1 4 5 6 0 2 7 3 
2 5 6 1 3 7 0 4 
3 6 1 4 7 0 2 5 
4 0 3 7 5 6 1 2 
5 2 7 0 1 3 4 6 
6 7 0 5 2 4 3 1 
7 3 4 2 6 1 5 0

has a worst case of 2 over every input (in my program, the permutations indicate the destination of the current symbol rather than the symbol that moves to the current destination). However, it already takes several minutes to compute and I will need to generalize this up to $k$ = 128.

I have been reading a bit about combinatorial designs but I am not mathematician, so I'm not sure what could work well. Any ideas?

$\endgroup$
  • $\begingroup$ Perhaps I am missing something: doesn't the identity along with swapping bit i with the last bit give cost zero for all inputs? $\endgroup$ – The Masked Avenger Apr 5 '14 at 18:26
  • $\begingroup$ @The Masked Avenger: Consider the images of $11111001$: itself and $11111010$ and $11111100$. These have costs of $5$, $6$, and $6$, for a minimum of $5$. To get a low cost, you need to move both $0$s close to the beginning. $\endgroup$ – Douglas Zare Apr 5 '14 at 18:31
  • $\begingroup$ @DouglasZare I think The-Masked-Avenger means swap bit i with the first bit? i.e. id, (2,1,3,4,...) (3,2,1,4,...), (4,2,3,1,...) etc. Therefore, whenever there is a 0, the cost is always 0. $\endgroup$ – Fei Gao Apr 6 '14 at 1:51
  • 1
    $\begingroup$ @Fei Gao: Perhaps people are mixing up first and last. That the first $0$ is in the first position does not mean the cost is $0$. The cost of $01111101$ is $5$, since there are $5$ $1$s before the last $0$, even though there are no $1$s before the first $0$. $\endgroup$ – Douglas Zare Apr 6 '14 at 2:41
  • 1
    $\begingroup$ Two quick comments: (1) The property you want seems vaguely like an approximation of a $t$-transitive permutation set. If you had access to more permutations, you could hope to map any small set of zeros to the front. (2) Every permutation in $\mathbb{F}_q$ is a polynomial. My gut feeling is you might find success choosing polynomials whose pairwise differences are of high degree (to "mix up placement of zeros"). I know high degree polynomials are useful in certain applications, such as cryptography. $\endgroup$ – Peter Dukes Apr 6 '14 at 20:28
1
$\begingroup$

In fact, you cannot do better than $k-2\sqrt{k\log k}$, i.e., for any $k$ permutations, there is a 0-1 sequence on which the cost of any permutation is at least this much. The prove is a simple application of known results about the Set Cover problem.

Consider the last $t=\sqrt{k\log k}$ positions in each permutation, these give $k$ sets of size $t$. We want to hit each of them with an element from our base set, this is called the Hitting Set problem and its dual is the Set Cover problem. You can read more details about them on Wikipedia, the important thing is that there is a fractional hitting set of size $k/t$ and since the integrality gap of the problem is at most $\log k$, there is a hitting set of size $(k\log k)/t$.

This means that we can select $(k\log k)/t$ positions such that any permutation contains at least one of them. If we set these positions to be 0's and the others to be 1's, then in any permutation there is a 0 somewhere towards the back and there are many 1's everywhere, a simple calculation gives a cost of at least $k-t-(k\log k)/t=k-2\sqrt{k\log k}$.

$\endgroup$
1
$\begingroup$

It seems that the worst case cost over all k-bit binary strings cannot be bounded by a constant. Let us try to argue that the worst case cost is lower bounded by $k/4$.

To keep the ceil and floor issues away, let us assume that $k$ is a multiple of $4$. Let $\pi_1, \ldots, \pi_k$ be the set of permutations that are chosen beforehand. Consider a $k$-bit binary string $B$ picked at random - by choosing each of the $k$ bits to be $0$ or $1$ independently and with equal probability. Consider the event $E$ that in at least one of the $k$ permutations of $B$, the final $k/4$ positions have no zeros. We can find an upper bound on the probability of $E$ as follows. The probability that there are no zeros in the final $k/4$ positions after $B$ is permuted according to $\pi_i$, $i \in [k]$, is $(1/2)^{k/4}$. The probability that there are no zeros in the final $k/4$ positions in at least one of the $k$ permutations of $B$ (which is the probability of $E$) is at most $k (1/2)^{k/4}$ (by union bound).

With probability $1/2$ the random string $B$ has at least $k/2$ ones. If $B$ has $k/2$ ones, then in any permutation the first $3k/4$ positions will contain at least $k/4$ ones.

The probability that either $B$ has less than $k/2$ ones or that event $E$ happens is at most $1/2 + k (1/2)^{k/4}$. For sufficiently large $k$, this will go below $1$. Which means, for such $k$, there is a non-zero probability that $B$ has more than $k/2$ ones (hence at least $k/4$ ones in the first $3k/4$ positions in every permutation) and that all the $k$ selected permutations of $B$ have a $0$ in at least one of the final $k/4$ positions. Which means with non-zero probability the cost of $B$ is at least $k/4$. Which then means that there exists some string $B$ with this property.

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