8
$\begingroup$

I need some help on this one:

We have sets $X$ and $Y$ chosen independently and uniformly at random from among all subsets of $\{1,2,\ldots,100\}$. Determine the probability that $X$ is a subset of $Y$.

$\endgroup$
  • $\begingroup$ are they guaranteed to have the same number of elements? $\endgroup$ – JLee Jan 8 '15 at 17:53
  • 3
    $\begingroup$ @JLee : If they were, then it would seem silly to phrase the question in the way in which it was phrased here. $\endgroup$ – Michael Hardy Jan 8 '15 at 18:14
  • 2
    $\begingroup$ Welcome to Math.SE! To attract answers to your question, please add some context and background information. For example, where did you encounter this problem (e.g. a book, class, real-life)? Please also show your attempt; seeing your work helps us help you. If this is homework, please read this post. $\endgroup$ – apnorton Jan 9 '15 at 4:56
  • $\begingroup$ ...is this a title in the Joy of Sets???! $\endgroup$ – JP McCarthy Jan 9 '15 at 13:49
25
$\begingroup$

For every element $a$ of initial set one of four options is true:

  1. $\quad a \in X,\quad a \in Y$
  2. $\quad a \not\in X,\quad a \in Y$
  3. $\quad a \in X,\quad a \not\in Y$
  4. $\quad a \not\in X,\quad a \not\in Y$

The probability of each option is $1/4$ (due to independence and uniformity).
$X\subseteq Y$ if for all $a \in \{1,\ldots,100\}$ options number $1$, $2$ or $4$ are true. For every element probability is $\dfrac{3}{4}$ and for whole set it is $\left(\dfrac{3}{4}\right)^{100}$.

$\endgroup$
  • 1
    $\begingroup$ this is better. +1, I'll leave mine to see how this is better. $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 18:09
5
$\begingroup$

how many pairs $(X,Y)$ satisfy $X\subseteq Y$? classify according to the size of $Y$.

So we get $\sum\limits_{k=0}^n\binom{n}{k}2^k$.

Since there are $2^n\times 2^n$ possible pairs $(X,Y)$ you want $$\frac{\sum\limits_{k=0}^n\binom{n}{k}2^k}{2^{2n}}$$

Now notice that $\sum\limits_{k=0}^n\binom{n}{k}2^k$ is equal to $3^n$ because it is the number of ways to color the integers from $1$ to $n$ with colors white grey and black. To see this we could say we are indexing on the number of elements that are grey or black (So first pick the subset of numbers that are grey or black) And once that subset has been selected choose the subsets of that subset that is going to be black. Hence uniquely determining the coloring.

$\endgroup$
  • 4
    $\begingroup$ The numerator of this expression can be seen to be $(2+1)^n=3^n$. $\endgroup$ – paw88789 Jan 8 '15 at 18:12
  • $\begingroup$ oh yeah, I think I saw it in a book, I'll try to prove it combinatorially to keep with the counting theme in the answer $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 18:14
  • 1
    $\begingroup$ So $3^n/2^{2n}$, which is $(3/4)^n$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jan 8 '15 at 18:16
  • $\begingroup$ I think I found a non too shabby proof that the numerator is $3^n$ $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 18:18
0
$\begingroup$

Let $D_n = \{i| i \in \Bbb N \land i \le n\}$.

For an empty set $D_0$ all its subsets $X,Y \subseteq D_0$ are empty: $X = Y = \emptyset$, so $P_0(X\subseteq Y) = 1.$

Now let's consider $D_n$ for $n\in \Bbb N$. Then any subset $X\subseteq D_n$ either is a subset of $D_{n-1}$ or it contains the number $n$, both with probability equal $\tfrac 12$. For subsets $X,Y$ there are four equally possible cases of $n$ inclusion, which results in $$P_n=\tfrac 14P_{n-1} + 0 + \tfrac 14P_{n-1} + \tfrac 14P_{n-1} = \tfrac 34P_{n-1} $$ Since $P_0 = 1 = \left(\tfrac 34\right)^0$, the above makes a general answer $$P_n=\left(\tfrac 34\right)^n$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.