$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?$

I could not solve this question,i have no idea how to even start it.Please help me.

  • 1
    $\begingroup$ How are we supposed to reconstruct $A$ from $P$?? $\endgroup$ – Hagen von Eitzen Oct 8 '15 at 5:46
  • $\begingroup$ @HagenvonEitzen I think it is his way of saying "sampling with replacement." $\endgroup$ – angryavian Oct 8 '15 at 5:46
  • 2
    $\begingroup$ 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 :) $\endgroup$ – 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}.$$


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.