Skip to main content
1 of 3
Simd
  • 3.4k
  • 26
  • 54

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.

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 $1/(cd)$ for $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