# Probability of finding one sub-object vs a million disjoint ones

Let $W$ be a set of words of length $n$ on the three letters $a$, $b$ and $\ast$. Say that an element $w$ in $W$ matches" a word $w'$ of length $n$ on the letters $a$ and $b$ if each $\ast$ in $w$ can be replaced with an $a$ or a $b$ in such a way to give $w$'. Say that two words in $W$ are disjoint if, for all $i=1,\ldots,n$, the $i$-th letter of at least one of the two words is a $\ast$.

(So, for example, if $n=4$ then $\ast a\ast b$ matches $babb$ but not $bbab$. The word $\ast\ast ab$ is disjoint from $a\ast\ast\ast$ but not $\ast a b\ast$ or $\ast\ast ab$.)

Suppose that, given a word $w'$ of length $n$ on the letters $a$ and $b$ chosen uniformly at random, with probability at least $1/20$ there is a set of a million disjoint words $w$ in $W$ that match $w'$.

Is there some $\delta>0$ independent of $n$ and $W$ such that, given a word $w'$ of length $n$ on the letters $a$ and $b$ chosen uniformly at random, with probability at least $1/20+\delta$ there is at least one $w$ in $W$ that match $w'$?

My motivation for asking this question comes from various geometric settings (Erdős–Rényi random graphs, ...) where one might wish to know that finding one sub-object of interest is definitively more likely than finding a million disjoint sub-objects of interest, even when the class of sub-object of interest is so poorly understood that you can't use anything about this class to analyze the question.

If all the words in W are disjoint from each other, then there is a positive answer (and moreover you can take $1/20+\delta$ to be very close to $1$).

• What does it mean for a million words to be disjoint? Do they need to be pairwise disjoint, or you need a more general notion than is present at the moment? Dec 1 '16 at 21:30
• Pairwise disjoint.
– Alex
Dec 1 '16 at 21:33
• The only tiny bit of progress that I've made on this problem is the following: For any 1>m>0 and any sufficiently small delta>0, and any k>1, there exists an n and Bernoilli RVs X_1, X_2, ..., X_n such that: (A) With probability at least m there is exists subset A of {1, ..., n} of size k such that X_i=1 for i in A, and the X_i, i in A are independent. (B) The probability that at least one X_i=1 is at most m+delta. I still hope that the question I asked has a positive solution, but this fact means that it has to use more than that finding disjoint words are independent events.
– Alex
Dec 3 '16 at 16:50