1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Well, are the $B_i$ sampled independently or not? If not, then how are they sampled? I suspect you intend for them to be sampled independently; and are just confused by the distinction between independent vs disjoint. Those are not the same. $\endgroup$ – D.W. Aug 7 '18 at 15:28
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Does the independent sampling of the $B_i$ directly imply, that the probabilites that they are a subset of $A$ are independent? Even if we get the information that they are a subset or not sequentially? (I edited my answer for clarification) $\endgroup$ – Memphisd Aug 8 '18 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.