4

The set A has $n$ elements, and so has $2^n$ subsets. The subsets are placed into an urn, and $m$ subsets $B_1, \dots, B_m$ are drawn in order at random with replacement from the urn. (Each subset has probability $\frac{1}{2^n}$.) What is the probability that $$B_1 \subseteq B_2 \subseteq \dots \subseteq B_m?$$

I'm not really sure how to approach this problem; the only thing I can think of is a counting argument of some sort, but it seems like that would involve a lot of casework about the sizes of the sets.

tostito
  • 305
  • 1
  • 5

2 Answers2

3

(The other answer appeared while I was typing this - the two are really the same argument, expressed differently.)

If you identify $B$ with its indicator function $\chi_B$ it's not hard to see that the probability that $B_1\subset\dots\subset B_m$ is exactly $(p_m)^n$, where $p_m$ is the probability that $X_1\le\dots\le X_m$ for iid random variables $X_1,\dots, X_m$, uniformly distributed on $\{0,1\}$.

Now there are $2^m$ possibilities for the sequence $(X_1,\dots,X_m)$, among which exactly $m+1$ are non-decreasing (the non-decreasing ones are just $(1,1,\dots,1), (0,1,1,\dots,1),(0,0,1,1,\dots,1),\dots,(0,0,\dots,0)$.)

So your probability is just $((m+1)/2^m)^n$.

David C. Ullrich
  • 89,985
0

First let us assume $m=2$. For each element you must have it in $B_2$ only, neither, or both, so the chance is $\frac 34$. The chance that $B_1 \subseteq B_2$ is therefore $\left(\frac 34\right)^n$

For more general $m$ each element must not stop appearing in the subsets once it has started. There are $2^m$ arrangements for the element among the $B$s of which $m+1$ are successful. The chance that a given element does not spoil the set of inclusions is then $\frac {m+1}{2^m}$ which agrees with $\frac 34$ when $m=2$. The chance no element spoils our inclusion is then $$\left(\frac {m+1}{2^m}\right)^n$$

Ross Millikan
  • 374,822
  • ah, I didn't think of considering the individual elements of the sets the way you did. thanks so much! – tostito Feb 18 '18 at 17:50