Number of successes when the successes are positively correlated

Question

In $n$ trials, each with success-probability $p$, what is the probability of at least $k$ successes, $P[n,k]$ ?

The answer depends on the dependence between the trials:

A. If the trials are independent, then the number of successes is a Binomial variable, so: $$ P^{\text{ind}}[n,k] = \sum_{i=k}^n {n\choose k} p^i (1-p)^{n-1} $$

B. If the trials can be arbitrarily dependent, then $P[n,k]$ might be 0. E.g, take $p=1/2$, $n=2,k=2$, and assume $X_2 = 1 - X_1$ (trial 2 fails iff 1 succeeds; from Henry's comment).

C. Now suppose that the variables are dependent "in the good direction": $$ \forall i_1,\ldots,i_j: \Pr[X_{i_1}=1\cap\cdots\cap X_{i_j}=1] \geq \Pr[X_{i_1}=1]\cdots\Pr[X_{i_j}=1] = p^j $$ that is, if we already had some successes, the probability of another success weakly increases.

Here, $P[n,k]$ cannot be zero. A trivial upper bound is $P[n,k] \geq p^k$ (as commented by muzzlator), since even if we consider only trials $1,\ldots,k$, the assumption implies that the probability all of them succeed is at least $p^k$

Is there a better lower bound for $P[n,k]$ in this case?

Initially I thought that $P[n,k]\geq P^{\text{ind}}[n,k]$, since intuitively, the dependence between the variables can only increase the number of successes. However, this is not true. As a simple example (from muzzlator's comment), take $k=1, n\to\infty$ and assume that all variables are the same: $X_i=X_1$ for all $i$. Then, $P^{\text{ind}}[n,1]\to 1$ while $P[n,1]=p$.

So, what is a correct lower bound on $P[n,k]$?

Answer 1

The answer to the question whether $p^k$ is the lower bound is: It depends. For some $p$,$n$,$k$ it is possible to achieve $P[n,k]=p^k$ for others it is not. The precise bound is given below. The following contains the sections:

1. An example where $p^k$ works and one where it fails
2. Discussion why there is no other solution to the failed example
3. The general equations which give the general lower bound
4. Some examples showing no constraints are redundant

Examples

I found those by writing the conditions as linear programming problem and solving it with R. The simplest example was $n=3$ and $k=2$. The tables below give the probability for each of the $2^n$ "states", i.e. unique combinations of zeros and ones of the variables. For $p=0.5$ the minimum $p^2=0.25$ is achieved by the solution:

| State| Probability| X_1=| X_2=| X_3=| #success|
|-----:|-----------:|----:|----:|----:|--------:|
|     0|        0.00|    0|    0|    0|        0|
|     1|        0.25|    1|    0|    0|        1|
|     2|        0.25|    0|    1|    0|        1|
|     3|        0.00|    1|    1|    0|        2|
|     4|        0.25|    0|    0|    1|        1|
|     5|        0.00|    1|    0|    1|        2|
|     6|        0.00|    0|    1|    1|        2|
|     7|        0.25|    1|    1|    1|        3|

For $p=0.9$ the optimum solution has $P[3,2]=0.85>0.81=0.9^2$:

| State| Probability| X_1=| X_2=| X_3=| #success|
|-----:|-----------:|----:|----:|----:|--------:|
|     0|        0.00|    0|    0|    0|        0|
|     1|        0.05|    1|    0|    0|        1|
|     2|        0.05|    0|    1|    0|        1|
|     3|        0.00|    1|    1|    0|        2|
|     4|        0.05|    0|    0|    1|        1|
|     5|        0.00|    1|    0|    1|        2|
|     6|        0.00|    0|    1|    1|        2|
|     7|        0.85|    1|    1|    1|        3|

No other solutions for $P[3,2]$ with $p=0.9$

Note that the dependency constraint C. as well as the objective function $P[n,k]$ are invariant under permutations. Hence if there is any solution at all there is also one invariant under permutations (exchangeable) and there is no loss of generality to discuss only those exchangeable solutions.

To generalise the failed example above let $x$ denote the total mass put on the states with 2 and 3 successes. The remaining mass can then be distributed on the states 1,2,4 with a single success and on state 0. Due to exchangeability each of the states 1,2,4 receives the same mass, call it $y$ and the rest which is allocated to state 0 $z$.

Using exchangeability again this leads to the equations $$ x+y=p \quad \text{ and }\quad x+3y+z=1\text{ for } z\geq 0.$$ The former expresses the constraint $\Pr[X_1=1]=p$ the latter the fact that all probabilities add up to one. Now set $x=p^k=p^2$, then $y=p-p^2$ and the remaining equation reads $$ z = 1- 3p - 2p^2.$$ A quick check reveals that $z(0.9)=-0.08 < 0$ fails while $z(0.5) = 0$. This corresponds to the probability of state 0 in the solution above and shows that the treshold for $p$ is indeed 0.5 in this case (the other root is 1).

General case

First one needs to convince oneself that the strategy minimising $P[n,k]$ puts all required mass $m$ (ideally $m=p^k$) into the single state with all ones and the $\binom{n}{k-1}$ states with $k-1$ successes. The reason is efficiency, you get best possible overlap when allocating to states with maximal number of ones. Note that if you are not on the threshold any mass remaining after condition C. is satisfied is allocated to the 0-state.

Case $k=1$: This case always achieves the minimum $p^k$. Just assign mass $p$ to state of all one and 1-p to the 0-state. So assume $k\geq 2$.

Due to exchangeability again all states with $k-1$ successes get assigned the same mass $y$. As in the example $y$ is determined by: $$(*) P[X_1=1]=p = m + \binom{n-1}{k-2} y$$ since $\binom{n-1}{k-2}$ is the number of states with $k-1$ successes and $X_1=1$.

The 0-state constraint reads: $$ z = 1 - m - \binom{n}{k-1}y\geq 0.$$

The j-dependency constraint for $2\leq j < k$ i.e. $\Pr[X_1=1, X_2=1, \ldots,X_j=1]\geq p^j$ is $$ m + \binom{n-j}{k-j- 1}y\geq p^j.$$

Since the strategy puts all mass in the all-one state, the remaining dependency constraints for $k\leq j \leq n$ are straightforward. We need $m\geq p^j$ and since $p^j\geq p^{j+1}$ this reduces to the single constraint $$ m\geq p^k.$$

To abbreviate write $b_j=\binom{n-j}{k-1-j}$ and use the equality constraint (*) to get rid of $y$ in the inequalities. The 0-constraint is then $$ m\geq \frac{b_1 - b_0 p}{b_1-b_0}$$ (note reversal of inequality since $b_1<b_0$) and the j-dependency constraints for $2\leq j \leq k-1$: $$ m \geq \frac{b_1p^j - b_j p}{b_1 - b_j}.$$

The smallest $m$ satisfying all constraints is the maximum of the constraints, i.e.:

\begin{align*} m &= \max \Big\{ p^k, \frac{b_1p^j - b_j p}{b_1 - b_j} | j=0,2,\ldots, k-1 \Big\} \\ &= \max \Big\{ p^k, \frac{(n-1)!(k-1-j)!p^j - (n-j)!(k-2)!p}{(n-1)!(k-1-j)! - (n-j)!(k-2)!} | j=0,2,\ldots, k-1 \Big\} \end{align*}

Necessity of all constraints

The constraints are not redundant as simple examples show. For $n=5$, $k=3$ and $p=\frac{2}{5}$ the maximum conditions in the sequence above are $$ \max \Big\{ \frac{8}{125}, 0, \frac{10}{125} \Big\} = \frac{10}{125}$$ which means that the 2-dependency bound is decisive and for $n=5$, $k=4$ and $p=\frac{3}{5}$ the 3-dependency bound bites $$ \max \Big\{ \frac{81}{5^4}, 0, \frac{75}{5^4}, \frac{87}{5^4} \Big\} = \frac{87}{5^4}$$ An example where a bound different from $j=k-1$ is active is provided by $n=8$, $k=4$ and $p=\frac{3}{8}$ with $$ \max \Big\{ 0.0198, 0, 0.0469, 0.0366\Big\} = 0.0469. $$

Answer 2

Trying a different approach here. Once again, I'm very sorry for how rough it is, and I'll try improve on it over time, but I'm stretched for time atm so I'll leave it here as something you might consider rather than as a full-fledged answer

Define the $i$-intersection as the region where exactly $i$ of the variables are true.

We want to get the most bang for buck by placing as much probability in the $(k-1)$-intersections as possible. That way, the probability budget here is spent in the most efficient way possible since the area is shared among $k-1$ things. There's no harm for our criteria putting our probability here since we're independent in the "good" direction.

The rest of our probability budget we want to spend in the $n$-intersection. This is because we use the least probability while knocking off all the variables here. That is to say, let's maximise our chance of exactly $k-1$ successes or otherwise, always have $n$ successes.

If the $n$-intersection were to have probability $p^k$, then we'd have to make sure every variable gets $p - p^k$ probability added to it. We can distribute these across the $(k-1)$-intersections. Each variable is associated with ${n-1} \choose {k-2}$ $(k-1)$-intersections so we need to make sure each $k-1$ intersection gets $(p - p^k)/{{n-1}\choose{k-2}}$. We then sum these up, there are total of $n \choose {k-1}$ of these so we are left with: $$ \frac{{n}\choose{k-1}}{{n-1}\choose {k-2}} (p - p^k) $$

Simplifying, this is:

$$ \frac{n}{k-1} (p - p^k)$$

The total area is therefore:

$$ \frac{n}{k-1} (p - p^k) + p^k $$

If this probability is less than or equal to $1$, we're good.

In general, we want to know when:

$$ \frac{n}{k-1} (p - A) + A \leq 1 $$ $$ \frac{k - 1 - n}{k-1} A \leq \frac{k - 1 - np}{k-1}$$ $$ A \geq \frac{np - k + 1}{n - k + 1} $$

So I'm going to say choice for lower bound maximum of $p^k$ and $\frac{np - k + 1}{n - k + 1}$.

Handwavey reasoning that the constraint is true: we have less area per variable in the ($k$ and above)-intersections (what I call the center) and therefore more in the lower intersections (the outside). Moreover, more of this is shared with all the other variables. Moreover, even if we use more than $p^k$ in the center, we're never going to add to it more than how much we'd have for $k$ or more successes with independent Bernoulli trials. <-- Edit: the flaw in this reasoning is that we count the ($k$ and above)-intersections area towards any intersection of fewer variables, and so having more area-per-variable on the outside doesn't mean much if the area in the center has decreased by too much.

Simple example of this:

In the case where $n=3, k=2, p=0.9$, $p^2 = 0.81$ and $\frac{np - k + 1}{n - k + 1} = 0.85$ and so the max is $0.85$. We can choose a distribution where probability of a single success is $0.05$ for each variable ($0.15$ total) and probability of all three succeeding is $0.85$

If $n=3, k=2, p=0.1$, then $p^2 = 0.01$ and $\frac{np - k + 1}{n - k + 1} = -0.35$ and so the maximum is $0.01$. We then share $0.01$ for all successes and have $0.09$ for each variable being the only success.

One more example:

If $n = 20, k = 10, p = 0.5$, then maximum is $\frac{np - k + 1}{n - k + 1} = \frac{1}{11}$. We now have $20 \choose 9$ places to put $(\frac{1}{2} - \frac{1}{11})/{19 \choose 8}$. That is, probability of exactly $9$ successes is $(\frac{1}{2} - \frac{1}{11})/{19 \choose 8}$ for each combination of $9$ things, and probability of all $20$ things succeeding is $\frac{1}{11}$. We'll see if the constraint is met here in the case of $P(X_1 \cap X_2) \geq 0.25$: We expect $X_1$ and $X_2$ to be in $18\choose 7$ of those $9$-intersections. That is a total probability of ${18\choose 7}(\frac{1}{2} - \frac{1}{11})/{19 \choose 8} = \frac{36}{209}$, add to that $\frac{1}{11}$ and we have $\frac{5}{19} > \frac{1}{4}$

To summarize: Consider the following distribution, where $A=\max\big(p^k, {np-k+1\over n-k+1}\big)$:

1. with probability $A$, all $n$ trials succeed.

2. with probability $(p-A) {{n \choose {k - 1}} \over {{n-1}\choose{k-2}}}$, a $k-1$-tuple of trials is selected at random, these $k-1$ trials succeed and the rest fail.

Then:

• The success probability of each single variable is (by construction):

$$ A + (p-A) {{{n-1}\choose{k-2}}\over{{n-1}\choose{k-2}}} = p $$

• The success probability of at least $k$ trials is exactly $A$.

It remains to prove that the success probability of each $j$-tuple of variables is at least $p^j$, i.e:

$$ A + (p-A){ {n-j \choose k-j-1} \over {n-1\choose k-2} } \geq p^j $$

This is obvious for $j\geq k$ since $A\geq p^k$. We proved it above for $j=1$. It remains to prove (or disprove) this for $1<j<k$.

Edit: See g g's examples below, he proves that the second condition is false. It's interesting that it always appears to be the $k-1$-intersection that causes the constraint, that is, can we use: $$A + (p-A){ 1 \over {n-1\choose k-2} } \geq p^{k-1} $$ as the only additional constraint?