Results 1 to 6 of 6

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

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    12

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jul 2009
    Posts
    593
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,769
    Thanks
    3027
    Quote Originally Posted by ANDS! View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,776
    Thanks
    2823
    Awards
    1
    Quote Originally Posted by undefined View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Dec 10th 2011, 06:40 PM
  2. Replies: 8
    Last Post: Nov 27th 2011, 10:18 PM
  3. Herstein: Simple proof with elements.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Oct 9th 2011, 12:29 PM
  4. Probablitity Help Please.....
    Posted in the Statistics Forum
    Replies: 5
    Last Post: May 9th 2009, 03:20 PM
  5. Proof of intersect between 2 elements of group G
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 21st 2008, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum