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

pairwisedisjoint, or you need a more general notion than is present at the moment? $\endgroup$