Skip to main content
added 620 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 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(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.)

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.

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

added 9 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 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(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.

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

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.

added 31 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 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$$$$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_{j,k})=\frac1{d^2}=P(A_j)P(A_k)$$$$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 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.

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.

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

added 31 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 31 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 1 character in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
added 683 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading