8
$\begingroup$

The question seems like it should be known, but I was not able to find it anywhere.

How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur?

For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.

Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$.

I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.

$\endgroup$
  • 2
    $\begingroup$ The quantifiers are not clear to me. $\endgroup$ – Anthony Quas Aug 31 '15 at 21:01
  • 1
    $\begingroup$ consider m strings of length n of zeros and ones. Say we arrange them in m rows. Resulting in an $m\times n$ matrix. The question is what is the minimum m so that for every k columns all possible 2^k binary combinations appear in the rows. I am interested in results of the form $f(n,k)\le m \le c f(n,k)$ with c a fixed numerical constant independent of n and k. For example obviously m must be bigger than $2^k$ $\endgroup$ – Anahita Aug 31 '15 at 21:03
  • $\begingroup$ You are supposed to be able to pick any k columns; not just adjacent columns? $\endgroup$ – Anthony Quas Aug 31 '15 at 23:40
  • $\begingroup$ I also don't exactly understand what you want, but probably this might help. link $\endgroup$ – Dongryul Kim Aug 31 '15 at 23:54
  • 2
    $\begingroup$ Can you edit your question to clarify it? It should be understandable for readers who do not look at the comments. $\endgroup$ – Joonas Ilmavirta Sep 1 '15 at 12:01
7
$\begingroup$

Orthogonal arrays were mentioned in another answer, but you are not requiring that each $k$-tuple occurs exactly once in every set of $k$ columns, but rather that each $k$-tuple occurs at least once in every set of $k$ columns.

What you are looking for is called a covering array. In the usual notation for covering and orthogonal arrays, $v$ is the size of the alphabet ($2$ in this case), $k$ corresponds to your $n$, and $t$ corresponds to your $k$. Some known upper bounds for the number of rows for small values of $t,k,v$ are listed in http://www.public.asu.edu/~ccolbou/src/tabby/catable.html - you are interested in the numbers for $(t,k,2)$.

$\endgroup$
1
$\begingroup$

Definition: A $t-(v,k,\lambda)$ orthogonal array ($t \leq k$) (also called an orthogonal array of power/strength $t$) is a $λv^t × k$ array whose entries are chosen from a set $X$ with $v$ points such that in every subset of $t$ columns of the array, every $t-$tuple of points of $X$ appears in exactly $λ$ rows. I have used the standard notation for letters.

It seems to me the OP is looking for orthogonal arrays with minimal number of rows over the set $X=\{0,1\}$ with $k=n,\lambda=1,$ and $t=k$ because he wants every $k-$tuple to occur in every possible $k$ positions.

There are literally hundreds of papers and tens of constructions in this area. There are some lower bounds known for existence. I suggest he start with reading the Wikipedia entry and then moving on to tutorial papers of which there are plenty. Happy googling!

$\endgroup$
  • $\begingroup$ Also, orthogonal arrays for $\lambda=1$, $v=2$ exist only when $k=t$, $k=t+1$ or $t=1$. $\endgroup$ – Janne Kokkala Sep 1 '15 at 11:59
  • $\begingroup$ Sorry, fixed. You're right in OA notation his $n$ (length of sequence) is their $k.$ I wasn't aware of the existence restraint you stated. $\endgroup$ – kodlu Sep 1 '15 at 22:21
  • $\begingroup$ Thanks these are great refs. It seems though orthogonal array means every combination appears exactly once. Is there some thing more specific if we want at least once? $\endgroup$ – Anahita Sep 4 '15 at 18:16
  • $\begingroup$ @Anahita, you can choose $\lambda\geq 1$ and have everything appear at exactly $\lambda$ times. The other answer is more directly relevant to what you asked. On the other hand, I am unsure if any infinite families of covering arrays are known. $\endgroup$ – kodlu Sep 5 '15 at 2:02

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.