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

Printable View

June 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
June 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.
June 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}.
June 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 $\mathcal{P}(X)$ mean powerset of a set $X$ . So in the question statement, $S = \mathcal{P}(R)$ . Not to be confused with $P(Y)$ which I'll use for probability of event $Y$ .

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

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

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

So we have $\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\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..
June 21st 2010, 12:38 PM
Plato

Quote:

Originally Posted by undefined

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

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

But $\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.
June 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 $P(A \subset B) = (3/4)^n$ .

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

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

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

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

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

Putting all these cases together,

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

which completes the proof.