# A subset $P$(may be void also) is selected at random from set $A$ and the set $A$ is then reconstructed by replacing the elements of $P$.

$A$ is a set containing $n$ elements,a subset $P$(may be void also) is selected at random from set $A$ and the set $A$ is then reconstructed by replacing the elements of $P.$A subset $Q$(may be void also)of $A$ is again chosen at random.

$(A)$What is the probability that number of elements in $P$ is equal to the number of elements in $Q?$
$(B)$What is the probability that $P\cap Q=\emptyset?$

• How are we supposed to reconstruct $A$ from $P$?? – Hagen von Eitzen Oct 8 '15 at 5:46
• @HagenvonEitzen I think it is his way of saying "sampling with replacement." – angryavian Oct 8 '15 at 5:46
• Well, in contrast to balls in urns, I was never under the impression that selecting a subset of $A$ would deprive $A$ or its powerset of elements in the first place as mathematical objects don't tend to change over time :) – Hagen von Eitzen Oct 8 '15 at 5:48

First problem; It is convenient to imagine that the choices are made from two distinct $n$-element sets, $A$ and $B$, say boys and girls. There are $2^n$ equally likely ways to choose a subset of $A$, and $2^n$ equally likely ways to choose a subset of $B$, for a total of $2^{2n}$.

There are $\binom{n}{k}$ ways to choose a $k$-subset of $A$, and $\binom{n}{k}$ ways to choose a $k$-subset of $B$, for a total of $\binom{n}{k}^2$ ways. Thus the total number of "favourables" is $\sum_{k=0}^n \binom{n}{k}^2$.

Now we have our answer, but it can be greatly simplified. What follows has appeared a number of times on MSE. Replace one of the $\binom{n}{k}$ by $\binom{n}{n-k}$. So we are interested in the sum $\sum_0^n \binom{n}{k}\binom{n}{n-k}$.

But this sum is the number of ways to choose a total of $n$ people from the $n$ boys and $n$ girls, so the number of favourables is $\binom{2n}{n}$. Divide by $2^{2n}$ for the probability.

Second problem: Imagine that we are choosing the two sets $P$ and $Q$ by writing down the letter P if the point is to be in $P$, writing NP if the point is to be not in $P$, and doing something similar for $Q$. Then we are asking for the probability we do not write down simultaneously P and Q. The probability of this for any element of $A$ is $\frac{3}{4}$, so the probability this happens $n$ times in a row is $\left(\frac{3}{4}\right)^n$.

I assume we pick $P$ and $Q$ uniformly and independently from the power set of $A$. Since there are $n\choose k$ subsets of size $k$ the answer to the first question is $$\sum_{k=0}^nP(|P|=k)P(|Q|=k)=2^{-2n}\sum_{k=0}^n{n\choose k}^2$$ (the expression can still be simplified, cf. André's explanation)

For the second question, note that each element of $A$ is element of exactly half of the subsets and in fact drawing a subset from the power set uniformly is the same as deciding for each element of $A$ independently with a fair coin toss whether or not we want to incorporate it. Hence a specific element $x$ is in $P\cap Q$ with probability $\frac14$. And so $A\cap B$ is empty iff $n$ consecutive experiments of probability $\frac14$ fail, i.e., $$\frac{3^n}{4^n}.$$