number of random sets needed to generate subset

Question

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?

Answer 1

The sets $B_i$ can be independent but still have an intersection; just because they are generated independently doesn't prevent them having an element in common (in fact, it ensures that possibility exists). If you assume that the sets $B_i$ are generated independently, then they are independent, period. If you don't assume that, you have to define how you assume that they are generated before you can calculate any probabilities.

---

Regarding your updated question: "But doesn't ... ?" - Answer: No, it doesn't. If the r.v.s $B_1,B_2$ are independent, then the events $B_1 \not\subseteq A$, $B_2 \subseteq A$ are independent.

If you want a formal proof, here is one. If $B_1,B_2$ are independent random variables and $f$ is any function, then $f(B_1),f(B_2)$ are independent random variables. (You should try to prove it; it is not hard.) Then let $f(X)$ be true if $X \subseteq A$, or false otherwise, and the claimed result follows.