4

What is the minimum number of points a sample space must contain in order that there exist $n$ independent events none of which has probability zero or one?

I'm thinking the answer is $2^n$, but this is just from checking by hand for the values $n=2$ and $n=3$. I thought maybe a proof by induction would be appropriate, but didn't make it terribly far with it.

I'm merely studying probability because I want to be better at it, and this seems to be a pretty classic problem. So it seemed like a good problem to understand.

Avraham
  • 3,237
Pierre
  • 41
  • 2
  • Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – Matthew Conroy Jun 11 '14 at 20:46
  • How exactly did you "check by hand" the case n=3? – Did Jun 11 '14 at 21:14
  • I created a sample space with 8 points and what should have been three independent sets. But since you just asked I double checked myself and it seems I was sloppy and made a mistake. – Pierre Jun 11 '14 at 21:25
  • Nevermind, I was right in the first place.

    If you take three sets, A, B, and C, each with four sample points such that the intersection of any two has two sample points, the intersection of all three has one sample point, and the complement of the union of all three has one sample point. The picture is a venn diagram with three intersecting circles such that each region has one point (including the complement of all of them).

     – Pierre Jun 11 '14 at 21:34
  • Perhaps there is more to the problem than you are sharing, but it is possible to have three independent events in a discrete probability space with fewer "points". Consider a uniform probability space on four points, say ${a,b,c,d}$. Let the three events be ${a,b}$, ${a,c}$, and ${a,d}$. These are independent according to the definition: the probability of the intersection of any two of them is product of their probabilities. – hardmath Jun 11 '14 at 23:57
  • @hardmath I think in your example the probability of the intersection of all three sets is 1/4, whereas the product of the probabilities of the three sets is 1/8. I don't think there is anything more to the problem than what I included here. But I thought that I was looking for sets A_1,A_2,...,A_n s.t. P(\bigcap_{i=1}^n A_i)=\Pi_{i=1}^n P(A_i). – Pierre Jun 12 '14 at 02:15
  • Two events are independent if the probability of their intersection is the product of their probabilities. For more than two events, we might ask them to be pairwise independent, or a stronger condition, mutually independent. This asks more than you have, looking only at the intersection of all events. – hardmath Jun 12 '14 at 02:33
  • I see what you mean. I assume the problem is meant to ask for mutually independent events. But perhaps the best conclusion at the moment is that the problem could be worded a little better (I took it essentially word for word from the book). Thanks for your help though. – Pierre Jun 12 '14 at 03:09
  • That one can construct K independent events on a sample space of size 2^K with some specific probability (for example the uniform one) is clear. But you are asking for the minimal size of the sample space, so my question was: did you check that no sample space of size 7, 6, 5, ..., can work? – Did Jun 12 '14 at 09:16

2 Answers2

2

Taking into account the independence of events stated by the question and considering that by definition two subsets/events that are mutually exclusive (disjoint) cannot be independent, we can note that any pair of events $X_i$ and $X_j$ must not be disjoint. This means that the intersection between $X_i$ and $X_j$ has to contain at least one point.

We can generalize this by noting that any intersection between the events $Y_1$, $Y_2$, $Y_3$, ... $Y_N$ has to contain at least one point, regardless of whether $Y_j$ corresponds to $X_j$ or to a "multiple" event $X_j^z$. As a result, all intersections of any combination of $Y_j$, with j = 1 to N, must include at least one point. Because the number of these combinations is $2^N$, we get that the sample space must have a minimal size of $2^N$ as well.

Also note that this results only represents a lower bound for the size of the sample space, as stated in the question. A simple example of space with size $2^N$ over which $N$ independent events can be identified so that none has probability equal to zero or 1 is given by a sequence of $N$ coin flips. Here the sample space is characterized by $2^N$ points, and under the uniform distribution each space point has probability equal to $1/2^N$. Considering the $N$ events $Y_1$, $Y_2$... $Y_N$, where $Y_j $ indicates the event that on the j-th flip we get (for example) head, these are $N$ clearly independent events, each with $1/2$ probability.

Anatoly
  • 17,079
  • This seems offtopic. Do you know the definition of independence of events? – Did Jun 12 '14 at 09:13
  • Thank you for your note. I have edited my answer taking into account the issue of independence of events. – Anatoly Jun 12 '14 at 15:47
  • Actually, you can have $n+1$ sample space points such that all $n$ events share the same point. So, all intersections won't be empty. However, these events are not independent. –  Sep 29 '14 at 08:55
1

Consider non-trivial independent events $\{A_i\}_{i=1}^n$. Now, use the fact that for any $\alpha\in\{0,1\}^n$, the family $\{B_i^{\alpha_i}\}$ is independent (see, for example, Theorem 2.5. in Klenke, Prob. Theory), where $B_i^{\alpha_i}=A_i$, if $\alpha_i=0$ and $A_i^c$, if $\alpha_i=1$.

Namely, for any $\alpha\in\{0,1\}^n$, $\bigcap_{i=1}^nB_i^{\alpha_i}$ must be non-empty (otherwise independence fails). By construction, these sets are disjoint and must contain at least one element. Hence, $|\Omega|\ge|\{0,1\}^n|=2^n$.