5
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
+50
$\begingroup$

Here is a solution for even $k\leq d$.

I. A lower bound for even $k$.

Simple lower bound (for $k$ even) follows from standard combinatorics of events and Bonferroni's inequalities. We need the following special case. (See e.g. Feller I (1968), p109/110.)

Let $(X_1,\ldots,X_d)$ be 0-1 variables, denote by $\sigma_j(X_1,\ldots,X_d)$ the $j$-th elementary symmetric function of $X_1,\ldots,X_d$, and let $S:=X_1+\ldots +X_d$. Further let $\mathbb{P}(S=1)$ the probability that exactly one $X_i=1$.

Then \begin{align*} \mathbb{P}(S=1)=\sum_{j=1}^d (-1)^{j-1} j\, \mathbb{E}\sigma_j(X_1,\ldots,X_d) \end{align*} and if in the sum for $\mathbb{P}(S=1)$ only the first $r$ terms are kept while the remaining terms are dropped, then the error (i.e. true value minus approximation) has the sign of the first omitted term, and is not larger in absolute value (``Bonferroni's inequalities'') .

Now let in your situation $A_i$ the event ``the $i$-th coin shows head'' and $X_i:=1_{A_i}$. Then by assumption $X_1,...,X_d$ are identically distributed with $P(X_1=1)=\frac{1}{d}$ and $k$-wise independent.. Thus for $j=0,\ldots,k$ $$\mathbb{E}\sigma_j(X_1,\ldots,X_d)={ d\choose j}\frac{1}{d^j}$$ and (by Bonferroni's inequalities above) for $k$ even $$\mathbb{P}(S=1)\geq \sum_{j=1}^k (-1)^{j-1} j\, { d\choose j}\frac{1}{d^j}=\sum_{j=0}^{k-1}(-1)^j { d-1\choose j}\frac{1}{d^j}$$

II. A matching construction

(Here we allow general success probability $p$.) The bound will be sharp when $\mathbb{E}\sigma_j(X_1,\ldots,X_d)=0$ for $j>k$. This will certainly be true $S=X_1+\ldots +X_d$ takes only values in $\{0,\ldots,k\}$.

We therefore try to find a distribution of the form $$\mathbb{P}(X_1=x_1,\ldots,X_d=x_d)=a(x_1+\ldots+x_d)$$
(the easiest case, the joint distribution depends only on the ``weight'' ) with $a(i)=0$ for $i > k$.

We want $X_1,\ldots,X_d$ to be $k$-wise independent and identically distributed with $\mathbb{P}(X_1=1)=p$.

This will be true if for $j=0,...,k$ $$\sum_{i=j}^d {d-j \choose i-j}a(i)=p^j\;\;.$$

Solving this (triangular) system of linear equations we find that for $j=0,\ldots,k$ we have to set
$$a(j)=p^j\sum_{i=0}^{k-j}(-1)^i {d-j \choose i} p^i\;\;.$$ These values will be a solution of the probabilistic problem if they are nonnegative. For $p=\frac{1}{d}$ this is easily shown to be the case. Thus in this case $\mathbb{P}(S=1)$ attains for even $k$ the lower bound given above.

Remarks:

(1) similarly, the construction achieves the corresponding ``Bonferroni upper bounds'' for odd $k$.

(2) for the case $k=d$ the probability $$\mathbb{P}(S=1)=(1-\frac{1}{d})^{d-1}=\sum_{j=0}^{d-1}(-1)^j { d-1\choose j}\frac{1}{d^j}\;\;,$$ and the lower and upper bounds for the $k$-wise independent cases are just the even resp. odd partial sums of the right hand side.

NOTE: for a given $k$ all $p\leq \frac{1}{d-k+1}$ give a probabilistic solution. The extreme cases $p=\frac{1}{d-k+1}$ of this construction appear in problems 6 and 7 of the "Mathematical Preliminaries Redux" section in fascicle 5 of volume 4 of "The Art of Computer Programming".

$\endgroup$
6
  • $\begingroup$ What are the asymptorics in $k$ and $d$ here? Is there a simple expression? $\endgroup$
    – Gabe K
    Commented Nov 4, 2020 at 15:01
  • $\begingroup$ For $k$ fixed and $d \longrightarrow \infty$ the bounds converge to $\sum_{i=0}^k \frac{(-1)^i}{i!}$ $\endgroup$
    – esg
    Commented Nov 4, 2020 at 17:27
  • 1
    $\begingroup$ So for pairwise independence ($k=2$) the other question showed that as $d$ gets large a strict lower bound is $1/d$ so it seems like these arguments are contradicting each other. $\endgroup$
    – Gabe K
    Commented Nov 4, 2020 at 18:08
  • 1
    $\begingroup$ For k=3, is it possible to say what the lower bound is? $\endgroup$
    – Simd
    Commented Nov 5, 2020 at 6:30
  • 1
    $\begingroup$ @Anush: Sorry, I have no idea what the lower bound should be for $k=3$ or any other odd $k$. (I have only found a construction which gives slightly lower (asymptotically equivalent) bounds than in the $k=4$ case.) $\endgroup$
    – esg
    Commented Nov 5, 2020 at 19:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .