1

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$.

Chain Markov
  • 15,564
  • 6
  • 36
  • 116
  • https://math.stackexchange.com/questions/1510300/what-is-the-minimum-number-of-points-a-sample-space-must-contain-that-there-exis –  Nov 27 '19 at 18:26
  • You seem to be misusing the term "mutually independent". It means what you seem to be referring to as "independent altogether", not "pairwise independent" as you seem to be using it. See https://en.wikipedia.org/wiki/Independence_(probability_theory)#More_than_two_events. – joriki Nov 27 '19 at 18:32
  • @joriki, yes, I wanted to write "pairwise independent". I accidentally typed the wrong word... – Chain Markov Nov 27 '19 at 18:53

1 Answers1

2

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$

Community
  • 1
antkam
  • 15,363
  • hi. would getting a full solution to this question be interesting, in your opinion? – mathworker21 Dec 14 '19 at 03:39
  • @mathworker21 - oh yes! i already thought about this on and off for a few more days, but wasn't able to make further progress. any ideas? – antkam Dec 14 '19 at 06:39
  • I'm confused by your answer. Is the bound $m \ge n+1$ obvious? – mathworker21 Dec 31 '19 at 22:06
  • also, you can include the event $N(\emptyset) = 0$ to get $m = 2^k$ if $n = 2^k$. – mathworker21 Dec 31 '19 at 22:11
  • the "correct" question here is to find $n(m)$, the maximum size of a collection of pairwise independent sets for an $m$-sided die. this question is highly number-theoretic in nature. For example, I think $n(m) = 3$ if $m$ is prime. – mathworker21 Dec 31 '19 at 22:27
  • 1
    @mathworker21 - Hmm, you're right it is not obvious that in general $m \ge n+1$. All I am saying is that $m=2^k$ suffices for any $n < m-1$. The OP question asks for the min $m$ for a given $n$, so my $m=2^k>n$ is an upperbound, hence "partial" solution. ... OK re-reading my wording, maybe once again you object to my choice of "all we need" -- in fact what I mean is "it suffices". :D OK let me reword the main Claim, and see if that addresses your concern. – antkam Dec 31 '19 at 23:01
  • @mathworker21 - as to including $N(\emptyset) = 0$, I forgot that that is possible! :) I was obviously subconsciously adding the word "non-trivial". For that matter, we could also add $N(\emptyset)=1$, and thereby have $m=2^k$ sufficing for $n=m+1$. – antkam Dec 31 '19 at 23:07
  • @mathworker21 - re: $n(m) = 3$ for prime $m$, what you have in mind is probably the events $\emptyset, \Omega$ and any other non-trivial event, right? If so, I think I agree with you... but the OP is asking for $m(n)$. are you saying the correct approach is to find $n(m)$ and the "invert"? Very interesting idea... – antkam Dec 31 '19 at 23:09
  • Yes, concern addressed (nice partial answer btw). What you said achieves $n(m) = 3$; the proof that $3$ is an upper bound follows quite easily from $m$ being prime I believe. What I was saying is that finding $n(m)$ seems much more interesting to me. I think that finding $n(m)$ explicitly for each $m$ might be possible, in which case we can find $m(n)$ easily, but I don't really care too much about $m(n)$ (i.e. about the OPs actual question), though maybe my mind will change. Happy new years! – mathworker21 Dec 31 '19 at 23:40
  • also, can we be friends? I'd be willing to tell you (privately) my real identity and we can exchange contacts, only if you want of course. – mathworker21 Dec 31 '19 at 23:47
  • @mathworker21 - sure but how are we gonna exchange contacts in private? AFAICT there is no direct-message function in MSE (i've always been surprised about this). – antkam Jan 01 '20 at 01:24