0
$\begingroup$

Here is the question, but I even don't understand what's $k$-sample...

It seems very abstract to me somehow...

Let $S$ be a set of binary strings $a_1 \cdots a_n$ of length $n$ (where juxtaposition means concatenation). We call $S$ $k$-complete if for any indices $1 < i_1 < \cdots < i_k < n$ and any binary string $b_1 \cdots b_k$ of length $k$, there is a string $s_1 \cdots s_n$ in $S$ such that $s_{i_1}s_{i_2} \cdots s_{i_k} = b_1 b_2 \cdots b_k$. For example, for $n = 3$, the set $S = \{001, 010, 011, 100, 101, 110\}$ is $2$-complete since all $4$ patterns of $0$’s and $1$’s of length $2$ can be found in any $2$ positions. Show that if $C(n, k) 2^k (1-2^{-k})^m <1,$ then there exists a $k$-complete set of size at most $m$.

  • 0
    @leonbloy: Perhaps "with probability" was a bad way of saying "using the probabilistic method" -- see my answer.2012-08-01

1 Answers 1

5

We can show this using the probabilistic method.

Choose $m$ binary strings of length $n$ randomly with independently uniformly distributed digits (i.e. throw a coin for each digit of each string). Each string has probability $2^{-k}$ of covering any given pattern of length $k$. There are $\binom nk2^k$ such patterns, so the expected number of patterns not covered is $\binom nk2^k(1-2^{-k})^m$. If this is less than $1$, that means that there must be at least one set of $m$ strings that leaves no patterns uncovered.

  • 0
    @user1489975: Did you check out the link to the Wikipedia article on the probabilistic method? That's explained there.2012-08-02