Frage

Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.

How many $B_i$ do we have to generate, so that there exists a $j: B_j\subseteq A$ with decent probability (constant or overwhelming in $n$).

It holds that $\Pr[B_i\subseteq A$ for a fixed $i$]=${\binom{\alpha n}{\beta n}}/\binom{n}{\beta n}$. If the probabilities for all $B_i$ would be independent we could make use of the geometric distribution to calculate (or at least bound) the probability that after generating $N$ random $B_i$ there is no $B_i: B_i\subseteq A$. But as soon as the $B_i$ start intersecting the probabilities seem not to be independent anymore. Any help would be appreciated.

Edit:

Ok, I guess my problem is, that I do not understand, if we are facing dependencies or not. So let me give some more details: The set $A$ is unknown, but we get access to an oracle $\mathcal{O}(B_i)$, that for input $B_i\subseteq \{1,...,n\}$ with $ |B_i|=\beta n$ outputs true, if $B_i \subseteq A$ holds and false otherwise. The $B_i$ are generated independently at random and tested sequentially for being a subset. So if the probabilities for all $B_i$ being a subset of $A$ are independent it must especially hold, that $$\Pr[B_2\subseteq A | B_1\not\subseteq A]=\Pr[B_2\subseteq A]$$

But doesn't the probability of $B_2$ being a subset of $A$ conditioned on $B_1$ being not a subset of $A$ depend on the size of the intersection of $B_1$ and $B_2$? So for example if $|B_1\cap B_2|=\beta n \Leftrightarrow B_1=B_2$ than $\Pr[B_2\subseteq A | B_1\not\subseteq A~\wedge~ B_1=B_2]=0$. Or does this just mean that all three events $(B_2\subseteq A, B_1\not\subseteq A, B_1=B_2)$ are not independent, but $B_2\subseteq A$ and $B_1\not\subseteq A$ can still be independent? If so, can we give a formal proof, that these events are indeed independent?

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top