Re: Expected Value of the number of elements in an intersection of two random subsets of a set

Hassan Jameel wrote:
This is my first post to this group. My question is as follows:
Consider a universal set Z. let N=|Z| be the number of elements in this
set. Let A and B be two subsets which are selected uniformly at random
from all subsets of Z (excluding the empty set).

Why exclude the empty set?

Let |A intersection B|
be the number of elements in the intersection of these two random
subsets. How can we calculate the following expected value:

E{|A intersection B|}

Suppose we allow the empty set, then each element is in A with
probability 1/2, and independently the same for B. So, each element is
in the intersection with probability 1/4. So, the expected number of
elements in the intersection is N/4.

The probability that neither A or B is the empty set is (1 - 2^{-N})^2.
So, if we don't allow empty sets, the expected number of elements is

N / ( 4 * (1 - 2^{-N})^2 ).

Further more, how can we calculate this expected value when A and B are
sampled according to any given distribution e.g. normal distribution
(not necessarily uniform).

There are only a finite number of subsets, so what do you mean by a
normal distribution?

--
David Marcus
.

Relevant Pages