6
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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$? $\endgroup$
    – Gabe K
    Oct 25, 2020 at 20:04

1 Answer 1

9
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ So, Chebyshev's inequality. $\endgroup$ Oct 25, 2020 at 14:58
  • $\begingroup$ @NateEldredge : That's right, it's just Chebyshev's inequality. $\endgroup$ Oct 25, 2020 at 15:19
  • 1
    $\begingroup$ Thank you. I particularly like your proof that the lower bound is attained. I will ask a follow up question about $k$-wise independence. $\endgroup$
    – Simd
    Oct 26, 2020 at 10:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Simd
    Oct 26, 2020 at 11:49
  • 2
    $\begingroup$ @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)$. $\endgroup$ Oct 26, 2020 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.