For what minimal number of sides of a die one can select $n$ independent events

combinatoricsdiceelementary-set-theoryindependenceprobability

Suppose, we roll a die with $m$ sides. What is the minimal possible number $m$ if there are $n$ distinct pairwise independent events?

Note, that not all events here have to be independent all together. For example if $m = 4$, then the events $a_1 = \{1, 2\}$, $a_2 = \{1, 3\}$ and $a_3 = \{1, 4\}$ are pairwise independent ($P(a_1) = P(a_2) = P(a_3) = \frac{1}{2}$ and $P(a_1 \cap a_2) = P(a_2 \cap a_3) = P(a_3 \cap a_1) = \frac{1}{4}$) and thus satisfy our condition, but are not independent altogether ($P(a_1 \cap a_2 \cap a_3) = \frac{1}{4} \neq \frac{1}{8}$).

The only thing, that I managed to get, was this:

If there are pairwise independent events $a_1, … , a_n$, such that $\sum_{i = 1}^{n} P(a_i) \leq c$, then $m \geq \frac{n(n-1)}{c^2}$

Proof:

$$c \geq \sum_{i = 1}^{n} P(a_i)$$

thus

$$c^2 \geq (\sum_{i = 1}^{n} P(a_i))^2 \geq 2\sum_{i = 1}^{n} \sum_{j = i + 1}^n P(a_i)P(a_j) = 2\sum_{i = 1}^{n} \sum_{j = i + 1}^n P(a_i \cap a_j) \geq \frac{n(n-1)}{m}$$

Q.E.D.

And I do not know, what will happen, if we remove the supposition that $\sum_{i = 1}^{n} P(a_i) \leq c$.

Best Answer

Partial solution.

Claim: When $n$ is of the form $n = 2^k-1$, then $m=n+1 = 2^k$ suffices, i.e. such $m$ is an upperbound on the OP's required minimum.

Corollary: For any $n$, taking $m = 2^k > n$ for the smallest such power-of-$2$ suffices.

Fine-print: as @mathworker21 pointed out, in both claims above, I am including only non-trivial events, i.e. those with prob strictly $\in (0,1)$. We can always include two more events $\emptyset$ and $\Omega$ since with $P(\emptyset)=0, P(\Omega)=1$, each is independent of any event.

Consider flipping $k$ independent fair coins, which can obviously be simulated by rolling an $m=2^k$ sided die. Let $S$ be a non-empty subset of ($1$ to $k$) coin(s), and let $N(S)=$ the number of Heads among coins in $S$, modulo $2$. Note that there are $2^k-1$ distinct non-empty subsets of coins, and therefore $2^k-1$ distinct events of the form $N(S)=0$. The main claim now follows from:

Lemma: If $S,T$ are two different non-empty subsets, then event $N(S)=0$ and event $N(T)=0$ are pairwise independent.

Proof: Clearly $P(N(S)=0) = P(N(T)=0) = 1/2$. OTOH:

  • Event $(N(S)=0 \cap N(T)=0) =$ event $(N(S-T) = N(S\cap T) = N(T-S))$

  • The subsets $S-T, S \cap T, T-S$ are disjoint.

  • Since $S,T$ are different and non-empty, either $2$ or all $3$ of the subsets $S-T, S\cap T, T-S$ are non-empty.

  • If $1$ of them is empty, the other two must both have an even number of Heads, i.e. prob $1/4$.

  • If all of them are non-empty, all three must have the same parity of number of Heads, i.e. prob $2 \times 1/8 = 1/4. ~~~~~\square$

Related Question