Thursday, October 8, 2009

Random subsets

Two random subsets A and B are selected from an n-element set. What is the probability that A is a subset of B?
Posted by at
Labels: ,

1 comment:

  1. DavidOctober 9, 2009 at 1:24 PM

    The answer is (3/4)^n.

    The only way that A can fail to be a subset of B is if there exists an element x that belongs to A but does not belong to B.

    For each x, the probability is 1/2 that x belongs to A, and 1/2 that x does not belong to B. Since the events are independent, the probability is 1/4 that x belongs to A but not B.

    The probability that this event does not occur for a given x is 1 - 1/4 = 3/4, and the probability that it never occurs for any x is (3/4)^n.

    ReplyDelete

Subscribe to: Post Comments (Atom)