Given $p>0$, I'm trying to find a collection of events that are pairwise independent and the probability of each event is $\le$ $p$ but the probability that none of them occur is zero.

For $p=\frac{1}{2}$, we can do the following. Let $X_1, X_2$ be independent random variables that take values in $\{0,1\}$ with equal probability and let $X_3 = X_1 +X_2 \mod 2$. Then the events $E_1:(X_1=X_2)$, $E_2:(X_2=X_3)$ and $E_3:(X_3=X_1)$ each have probability $\frac{1}{2}$ and are pairwise independent since $P(E_i \wedge E_j) = \frac{1}{4}$.

Also, $P(\bar{E_1}\wedge \bar{E_2}\wedge \bar{E_3}) = 0$.

How do we proceed for $p<\frac{1}{2}$? Any ideas are appreciated.

(I tried using independent $n$-binary strings $X, Y, Z$ such that $z_i = x_i+y_i \mod 2$ for $n$ large enough such that $\frac{1}{2^n} < p$ and then finding events that are pairwise independent and satisfy what I want. But the plan didn't work so far)


2 Answers 2


Roll a fair $n$-sided a total of $n+1$ times. Let $X_i$ be the outcome of the $i^{th}$ roll, and for each $i\neq j$, let $E_{i,j}$ be the event that $X_i=X_j$. Then $P(E_{i,j})=1/n$, the events $E_{i,j}$ are pairwise independent, and at least one of them always occurs by the pigeonhole principle.


Take $n$ large enough such that $\frac{1}{2^n} < p$. Let $X_i, i \in \{1,\ldots\ , 2^{n}+1\}$ be independent random variables that takes as values the binary strings of length $n$ where the digit in each position is determined by tossing a fair coin. Let $E_{ij}$ denote the event $(X_i = X_j)$ for $i < j$ and $i,j \in \{1, \ldots , 2^{n}+1 \}$.

$P(E_{ij}) = \prod_{k=1}^n P(a_k = b_k) = \frac{1}{2^n} < p$, where $a_k,b_k$ denote the digits at the $k$th position for $X_i,X_j$.

Now $P(E_{ij}\wedge E_{jl}) = \prod_{r=1}^n P(a_r=b_r=c_r) = \frac{1}{2^{2n}}$.

So, $E_{ij}, E_{jl}$ are independent. Also $E_{ij}, E_{lm}$ are independent.

Now, the events $(X_i \ne X_{j})$ for $i<j$ and $i,j \in \{1, \ldots, 2^n \}$ mean that $X_1, \ldots, X_{2^n}$ exhaust all possible $2^n$ binary strings of length $n$. So $X_{2^n + 1}$ must equal some $X_i$ for $i \le 2^n$.

That is, the event $\wedge_{i<j}\overline{E_{ij}} = \wedge_{i<j}(X_i \ne X_j)$ for $i,j \in \{ 1, \ldots, 2^n+1\}$is an impossible event. So, $P(\wedge_{i<j} \overline{E_{ij}}) = 0$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .