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

$\endgroup$
3
  • $\begingroup$ i don't see probability anywhere... Further, the problem could seem "very abstract", but the provided example should make it clear. $\endgroup$
    – leonbloy
    Commented Aug 1, 2012 at 18:58
  • $\begingroup$ You say you don't understand "$k$-sample", but there seems to be no mention of a $k$-sample in the question? $\endgroup$
    – joriki
    Commented Aug 1, 2012 at 20:09
  • $\begingroup$ @leonbloy: Perhaps "with probability" was a bad way of saying "using the probabilistic method" -- see my answer. $\endgroup$
    – joriki
    Commented Aug 1, 2012 at 20:53

1 Answer 1

Reset to default
6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ so Each string has probability 2−k of covering any given pattern of length k, does that mean from the n length, i only care k length structure? $\endgroup$
    – user1489975
    Commented Aug 2, 2012 at 14:03
  • $\begingroup$ I still got confused by this statement "the expected number of patterns not covered is (nk)2k(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." $\endgroup$
    – user1489975
    Commented Aug 2, 2012 at 14:05
  • $\begingroup$ @user1489975: Sorry, I don't understand the question in your first comment; please repharse it. Regarding the second comment, which part of that statement do you find confusing? By the way, note that you can use $\TeX$ on this site to make your mathematical notation more readable. Enclose it in single dollar signs for inline formulas or double dollar signs for displayed equations. If you don't know how to format something, you can get the code for any math you see on this site by right-clicking on it and selecting "Show Math As: TeX Commands". $\endgroup$
    – joriki
    Commented Aug 2, 2012 at 14:06
  • $\begingroup$ the first question i have figured it out, it's just like i choose k digits from n uniformly distributed digits. the expected number of patterns not covered is fine, i just confused by why if it's less than one, we would have the conclusion for the last phrase. $\endgroup$
    – user1489975
    Commented Aug 2, 2012 at 14:10
  • $\begingroup$ @user1489975: Did you check out the link to the Wikipedia article on the probabilistic method? That's explained there. $\endgroup$
    – joriki
    Commented Aug 2, 2012 at 14:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .