Skip to main content
5 of 8
added 31 characters in body
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

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(B_j)+\sum_{l\in[d]\setminus\{j\}}P(C_{j,k})=\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_{j,k})=\frac1{d^2}=P(A_j)P(A_k)$$ for all distinct $j,k$ in $[d]$ -- so that the $A_j$'s are 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.

Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229