5

This is classic problem from most of the probability theory textbooks. What is the minimum number of points a sample space must contain in order that there exist $n$ independent events $A_1,\ldots,A_n$ none of which has probability zero or one? The answer I obtained by drawing Venn diagrams for cases $n=2,3$ was $2^n$. Cannot prove it for general case, meaning for any $n$.

Michael Hardy
  • 1
Don
  • 636

3 Answers3

7

If each of the events $A_1,\ldots,A_n$ has probability between zero and one, then by independence the same is true for all intersections $B_1\cap\cdots\cap B_n$ of events where $B_i$ is either $A_i$ or the complement of $A_i$. These intersections form a collection of $2^n$ disjoint sets, and each one in the collection is nonempty (since each one has positive probability), so each one contains at least one point not in any of the others. Conclude there are at least $2^n$ points in the sample space.

You can come up with an example where the value $2^n$ is achieved.

grand_chat
  • 38,951
  • You mean flipping a fair coin? – Don Nov 03 '15 at 01:13
  • @Don : The coin wouldn't be "fair" but it would have more than $0$ probability of "heads" and more than $0$ probability of "tails", and moreover it would generally be $n$ different coins each with its own probabilities of "heads" and "tails". ${}\qquad{}$ – Michael Hardy Nov 03 '15 at 01:27
  • @Don: Yep, flipping $n$ fair coins will do, but As Michael Hardy mentions, the coins involved don't need to be fair, or even have the same success probability, as long as the success probability is neither 0 or 1. – grand_chat Nov 03 '15 at 01:46
  • For example, I toss a fair coin. I am looking for Heads=$H$ (Tails=$T$), $A_1=H$, $A_2=TH$ ,$A_3=TTH$ and so on where $A_n$ is event. So I am looking for a toss which ends in heads. Would it be a good example? – Don Nov 03 '15 at 04:43
  • Does it have anything to do with the fact that the smallest sigma algebra is $2^n$? – Don Nov 03 '15 at 04:55
  • $P$($\bigcap_{i=1}^nB_i$)=$\prod\limits B_i$ – Don Nov 03 '15 at 05:06
  • Is there any way to prove it thru the equation written above? – Don Nov 03 '15 at 05:13
  • @Don: There is a simpler approach than what you are suggesting. Take the sample space to be all n-tuples of $H$ and $T$ (in other words, all the possible outcomes of tossing $n$ coins). This sample space has $2^n$ distinct elements. Consider events $A_1,\ldots, A_n$ where we define $A_i$ to be the set of all elements with an $H$ in slot $i$. Put a uniform probability distribution on the sample space, so $P({x})=1/2^n$ for each $x$. Now show (1) $P(A_i)=1/2$ for every $i$ and (2) the $A$'s are independent events. – grand_chat Nov 03 '15 at 19:10
1

Let's try proving it by induction on $n$. Suppose for $n$ events it's $2^n$. Then we add an $(n+1)$th event $A_{n+1}$.

Then each of the $2^n$ outcomes $\omega$ that we already had needs to be split into two separate outcomes $\omega_0$ and $\omega_1$. When the outcome is $\omega_0$, each of the $n$ events $A_1,\ldots,A_n$ either occurs or fails just as it did when the outcome was $\omega$, and the $(n+1)$th event fails. When the outcome is $\omega_1$, each of the $n$ events $A_1,\ldots,A_n$ either occurs or fails just as it did when the outcome was $\omega$, and the $(n+1)$th event occurs.

Splitting each outcome into two outcomes yields twice as many outcomes as before, thus $2^n\times 2 = 2^{n+1}$.

Michael Hardy
  • 1
0

Independence among $B_1$, $B_2$,...,$B_n$ means $\prod_{i\in I}P(B_n)=P(\bigcap_{i\in I}B_n)$ for all $I\in2^{[n]}$ and $\#(I)>=2$ there are $2^n-n-1$ equations (remove the 0 and 1 $B_n$'s)

Claim: under the assumption of problem, the $2^n$ possible intersection $\bigcap_{i\in I}B_n$ ($I\in 2^{[n]}$) are all distinct.
If not, $\bigcap_{i\in I_1}B_n=\bigcap_{i\in I_2}B_n$, then $\bigcap_{i\in I_1}B_n=(\bigcap_{i\in I_2}B_n)\cap (\bigcap_{i\in I_1}B_n)=(\bigcap_{i\in I_1 \cup I_2}B_n)$
then we have $\prod_{i\in I_1}P(B_n)=\prod_{i\in I_1 \cup I_2}P(B_n)$ => $\prod_{i\in I_2 - I_1}P(B_n)=1$, since $P(B_n)>0, \forall n$=> $P(B_n)=1, \forall n\in I_2-I_1$. it contradicts with the assumption that $P(B_n)\neq 1$. therefore, $I_2-I_1= \emptyset$. similarily, $I_1-I_2=\emptyset $, that is, $I_1=I_2$.

$B_1,..,B_n$ divides $\Omega$ into $2^n$ partitions (2 partitions ($A,A^c$) for only one event; 4 partitions ($A-B,AB,B-A,(A\cup B)^c$) for 2 events, etc), and to make all $2^n$ intersections distinct, at least one element in each partition (with positive probability).

Xinyu Liu
  • 1