# Probablitity Proof: Let R=(1,2,...,n) be a set with n elements ....

• Jun 21st 2010, 06:00 AM
teramaries
Probablitity Proof: Let R=(1,2,...,n) be a set with n elements ....
Let R=(1,2,...,n) be a set with n elements. Let S be a set of all subsets. There are 2^n such subsets. Pick 2 at random call A and B. Show probability that A contained in B is (3/4)^n
• Jun 21st 2010, 06:42 AM
ANDS!
Something to help you get started: if S is the power set on R, then for any two randomly selected subsets A and B there are four possibilities: A is a subset of B, B is a subset of A, A is equal to B and A and B are disjoint sets (meaning they have no intersection - for example S= {1,2,3}, A could be {1} and B could be {2,3} - both subsets on S, neither containing the other).

Hopefully that is a step in the right direction.
• Jun 21st 2010, 10:58 AM
HallsofIvy
Quote:

Originally Posted by ANDS!
Something to help you get started: if S is the power set on R, then for any two randomly selected subsets A and B there are four possibilities: A is a subset of B, B is a subset of A, A is equal to B and A and B are disjoint sets (meaning they have no intersection - for example S= {1,2,3}, A could be {1} and B could be {2,3} - both subsets on S, neither containing the other).

Hopefully that is a step in the right direction.

No that's not right. A and B could be two NON-disjoint sets that are not equal and one is not a subset of the other. For example, with S= {1, 2, 3}, A= {1, 2} and B= {2, 3}.
• Jun 21st 2010, 11:37 AM
undefined
I think the question can be answered like this.

I assume A and B are not necessarily distinct sets.

Let $\displaystyle \mathcal{P}(X)$ mean powerset of a set $\displaystyle X$. So in the question statement, $\displaystyle S = \mathcal{P}(R)$. Not to be confused with $\displaystyle P(Y)$ which I'll use for probability of event $\displaystyle Y$.

$\displaystyle |\mathcal{P}(R)| = 2^n = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}$

So for randomly selected subset $\displaystyle A$ of $\displaystyle R$, there is a $\displaystyle \displaystyle\frac{\binom{n}{0}}{2^n}$ probability that $\displaystyle |A| = 0$, a $\displaystyle \displaystyle\frac{\binom{n}{1}}{2^n}$ probability that $\displaystyle |A| = 1$, etc.

Suppose $\displaystyle |A| = k$. How many (not necessarily proper) supersets does $\displaystyle A$ have that are in $\displaystyle S$? It is $\displaystyle 2^{n-k}$. (Each element in the complement of $\displaystyle A$ can be either in the superset, or not.) So the probability that $\displaystyle B$ is a superset of $\displaystyle A$ is $\displaystyle \displaystyle \frac{2^{n-k}}{2^n}$.

So we have $\displaystyle \displaystyle P(A \subseteq B)=\sum_{k=0}^n\left(\frac{\binom{n}{k}}{2^n}\cdot \frac{2^{n-k}}{2^n}\right) = \sum_{k=0}^n\frac{\binom{n}{k}}{2^{n+k}}=\displays tyle\frac{1}{2^n}\sum_{k=0}^n\frac{\binom{n}{k}}{2 ^k}$

Someone please help me with the last step: How to prove that $\displaystyle \displaystyle\sum_{k=0}^n\frac{\binom{n}{k}}{2^k}= \left(\frac{3}{2}\right)^n$? I'm guessing it's easy for people more used to working with sums of this nature..
• Jun 21st 2010, 12:38 PM
Plato
Quote:

Originally Posted by undefined
help me with the last step: How to prove that $\displaystyle \displaystyle\sum_{k=0}^n\frac{\binom{n}{k}}{2^k}= \left(\frac{3}{2}\right)^n$?

Notice that $\displaystyle 3^n=(1+2)^n=\sum\limits_{k = 0}^n {\binom{n}{k}}2^{n - k} }$

But $\displaystyle \sum\limits_{k = 0}^n {\binom{n}{k}}2^{n - k}=2^n\sum\limits_{k = 0}^n {\displaystyle\frac{\binom{n}{k}}{2^k} }$

BTW: That was nice work on your part.
• Jun 21st 2010, 02:31 PM
awkward
Nice indeed. Here is another approach: induction over n.

The case n=1 is easy to verify.

Suppose that when A and B are randomly chosen subsets of a set of size n that $\displaystyle P(A \subset B) = (3/4)^n$.

Now consider the case where there are n+1 elements $\displaystyle \{1, 2, 3, \dots n+1\}$, and suppose A and B are randomly chosen subsets. We know $\displaystyle P(n+1 \in A) = P(n+1 \in B) = 1/2$, and the events $\displaystyle n+1 \in A$ and $\displaystyle n+1 \in B$ are independent.

If $\displaystyle n+1 \notin A$ and $\displaystyle n+1 \notin B$, which happens with probability 1/4, then $\displaystyle P(A \subset B) = (3/4)^n$ by the inductive hypothesis.

If $\displaystyle n+1 \notin A$ and $\displaystyle n+1 \in B$, which happens with probability 1/4, then $\displaystyle P(A \subset B) = (3/4)^n$.

If $\displaystyle n+1 \in A$ and $\displaystyle n+1 \notin B$, which happens with probability 1/4, then $\displaystyle P(A \subset B) = 0$.

If $\displaystyle n+1 \in A$ and $\displaystyle n+1 \in B$, which happens with probability 1/4, then $\displaystyle P(A \subset B) = (3/4)^n$.

Putting all these cases together,

$\displaystyle P(A \subset B) = (1/4 + 1/4 + 1/4) (3/4)^n = (3/4)^{n+1}$,

which completes the proof.