Say we toss $d$ pairwise independent coins, each with probability $1/d$ of getting a head. What is the highest lower bound one can give for the probability of getting exactly one head?


If they had been fully independent then I believe the answer is $1/e$.



Lower bound for probability of getting exactly one head with pairwise independence
The highest lower bound is $1/d$.


Indeed, for each $j\in[d]:=\{1,\dots,d\}$, let $A\_j$ denote the event of the head on the $j$th coin and let $X\_j:=1\_{A\_j}$. Let $S:=X\_1+\dots+X\_d$. Then the event of getting exactly one head is $\{S=1\}$.


Note that $EX\_j=p$ and (by the pairwise independence) $EX\_jX\_k=p^2+pq\,1(j=k)$ for all $j,k$ in $[d]$, where $p:=1/d$ and $q:=1-p$. So, by Chebyshev's inequality,
$$P(S\ne1)=P(|S-1|\ge1) \\ 
\le E(S-1)^2 \\ 
=ES^2-2ES+1\\ 
=\sum\_{j,k\in[d]}EX\_jX\_k-2\sum\_{j\in[d]}EX\_j+1 \\ 
=d^2p^2+dpq-2dp+1\\ 
=1-1/d,\tag{1}$$
whence
$$P(S=1)\ge1/d,\tag{2}$$
so that $1/d$ is indeed a lower bound on the probability of getting exactly one head.


It is also easy to see that this lower bound is attained. Indeed, consider the events
$$B\_j:=\{X\_j=1,S-X\_j=0\}=\{X\_j=1,S=1\},\\
C\_{j,k}:=\{X\_j=X\_k=1,S-X\_j-X\_k=0\}=\{X\_j=X\_k=1,S=2\}$$
for $j,k$ in $[d]$ such that $j<k$. These events are mutually exclusive, their union is the event $\{S\in\{1,2\}\}$, and the number of these events (that is, of the $B\_j$'s and the $C\_{j,k}$'s) is $n\_d:=d+d(d-1)/2\le d^2$. Therefore, we may assign probabilities to these events as follows:
$$P(B\_j):=1/d^2,\quad P(C\_{j,k}):=1/d^2,$$
so that $P(S=1)+P(S=2)=n\_d/d^2\le1$, with $P(S=0):=1-n\_d/d^2$. Then
$P(S\in\{0,1,2\})=1$, so that the inequality in (1) becomes the equality, and hence the inequality in (2) becomes the equality.
It also follows that
$$P(A\_j)=P(X\_j=1)=P(X\_j=1,S\le2)=P(X\_j=1,S=1)+P(X\_j=1,S=2)=P(B\_j)+\sum\_{l\in[d]\setminus\{j\}}P(C\_{1,2})=\frac1{d^2}+(d-1)\frac1{d^2}=\frac1d$$
for all $j\in[d]$ and
$$P(A\_j\cap A\_k)=P(X\_j=X\_k=1)=P(X\_j=X\_k=1,S\le2)=P(X\_j=X\_k=1,S=2)
=P(C\_{1,2})=\frac1{d^2}=P(A\_j)P(A\_k)$$
for all distinct $j,k$ in $[d]$ -- so that the $A\_j$'s are pairwise independent events of probability $1/d$ each, as desired.  

Thus, $1/d$ is indeed the best lower bound on the probability of getting exactly one head.




---


**Remark:** The above reasoning holds (with slight, straightforward modifications) for any natural $d\ge2$ and any $p\in[0,1/(d-1)]$ (in place of $1/d$). Indeed, for such $d$ and $p$, the best lower bound on the probability of getting exactly one head is (cf. (1)) $P:=2dp-d^2p^2-dpq=dp(2-dp-q)=dp(1-(d-1)p)$. In particular, if $p=c/d$ with $d$ varying and $c\in(0,1)$ remaining constant, then $P>dp(1-dp)=c(1-c)$, so that $P$ remains bounded away from $0$, just as in the case when the $A\_i$'s are assumed to be independent. Thus, there is a "phase transition" at $c=1-$. (The case $d=1$ is, of course, trivial.)


