Results 1 to 6 of 6

Math Help - 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
    15,361
    Thanks
    1311
    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 \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..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

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

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 10th 2011, 06:40 PM
  2. Replies: 8
    Last Post: November 27th 2011, 10:18 PM
  3. Herstein: Simple proof with elements.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 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