# Lower bound for probability of getting exactly one head with pairwise independence

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

• From @Iosif Pinelis' answer, the sharp lower bound is $1/d$. Meanwhile, if they are i.i.d., the probability is $O(1)$, independent of $d$. If the coin-flips are three-wise independent (or $k$-wise independent), what happens to the lower bound as a function of $d$? – Gabe K Oct 25 at 20:04

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

• So, Chebyshev's inequality. – Nate Eldredge Oct 25 at 14:58
• @NateEldredge : That's right, it's just Chebyshev's inequality. – Iosif Pinelis Oct 25 at 15:19
• Thank you. I particularly like your proof that the lower bound is attained. I will ask a follow up question about $k$-wise independence. – fomin Oct 26 at 10:05
• If each coin has probability $1/(2d)$ of getting a head instead of $1/d$, can you still get a similar tight result? It seems from my calculations that you get a lower bound independent of $d$ which seems very surprising at first glance. But I may be mistaken. – fomin Oct 26 at 11:49
• @fomin : I have added the remark about other values of $p$. What you said about $p=1/(2d)$ is, of course, true (good observation!), and the similar conclusion is now shown to hold for $p=c/d$ with any constant $c\in(0,1)$. – Iosif Pinelis Oct 26 at 13:57