2
$\begingroup$

Given a set $N$ I would like to calculate the probability that two arbitrarily chosen and equally likely subsets $K\subseteq N$ and $J\subseteq N$ both of fixed size intersect. Let's say $n=\#N$, $k=\#K$, and $j=\#J$ denote the number of elements of the respective sets. The probability should be called $\rho(p,j,k)$ and so far I think I have two formulas which do the job.

The first is recursively defined as:

$$ \rho(p,j,k)=\begin{cases}\frac{k}{n}+\frac{n-k}{n}\cdot\rho(j-1,k,n) & \text{if $j$>0},\\ 0 & \text{otherwise}.\end{cases} $$

The idea is that taking the first element of $J$ there is a chance of $\frac{k}{n}$ that it will be an element of $K$. If not, i.e. with a probability of $1-\frac{k}{n}=\frac{n-k}{n}$ there might be the probability that the next element will be in $K$ and so on.

I have an explicit formula as well:

$$ \rho(p,j,k)=\frac{k}{n}+\frac{k(k-1)}{n^2}+\cdots+\frac{k(k-1)\cdots(k-j+1)}{n^j}$$

The idea here is that either one element of $J$ is in $K$ (Probability: $\frac{k}{n}$) or two elements of $J$ are in $K$ (Probability: $\frac{k(k-1)}{n^2}$) and so on...

Now I have two questions:

  • First, I think I need to assume that $j\le k$ and I would like to not put any restrictions on the sizes of the sets.

  • Second, the problem seems very general so I wonder whether there is some known obvious result to it which I am overlooking.

$\endgroup$
2
$\begingroup$

I suppose that $k=\#K$ and $j=\#J$ are given. The number of all $J$'s is $\binom{n}{j}$, the number of those $J$'s that don't intersect $K$ is $\binom{n-k}{j}$, so the probability that $K$ and $J$ don't intersect is $\binom{n-k}{j}/\binom{n}{j}$.

edit: oops, you actually know the answer - but I'll leave it here anyway, just in case someone finds it useful

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think I did not know the answer. My formulas assume that $j\le k$ whereas your equation is symmetric with respect to $j$ and $k$. $\endgroup$ – Rupert Jones May 14 '13 at 9:29

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.