Skip to main content
3 of 3
I corrected the formula for the lower bound from the previous answer.
Gabe K
  • 6k
  • 2
  • 31
  • 60

Probability of getting exactly one head and $k$-wise independence

Say we toss $d$ $k$-wise 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? In the first instance, let us consider $k=3$ or $4$ but a result for general $k\geq2$ would be wonderful. If $k=d$ then $1/e$ is a lower bound independent of $d$.

Background

It turns out that for $k=2$ the answer is $1/d$ which is tight. If the probability of getting a head is instead $c/d$ for $0 <c<1$ then @IosifPinelis points out there is a lower bound of $c(1-c)$, independent of $d$. In other words there is a transition at $c=1$. At least to me that makes pairwise independence seem very unintuitive as $1/d$ is the value which maximises the probability of getting exactly one head in the case where the coins are fully independent.

Simd
  • 3.4k
  • 26
  • 54