6
$\begingroup$

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]$?

$\endgroup$
7
  • $\begingroup$ What is $p$ here? I would have thought $P^{\text{ind}}[20,10] \approx 0.588$ when $p=\frac12$, while $P^{\text{ind}}[2,1] =0.75$ $\endgroup$
    – Henry
    Jul 21, 2017 at 8:12
  • $\begingroup$ To reproduce your results it seems $p=\frac34$ is necessary. You would get $P^{\text{ind}}[20,10] < P^{\text{ind}}[2,1] $ for $p \le \frac{1}{2}$ (in fact $p \lt 0.5761537\ldots$) and I find that less counterintuitive $\endgroup$
    – Henry
    Jul 21, 2017 at 8:22
  • $\begingroup$ Let them all be the same variable, then P[n,k] = p, but P_ind[n, 1] = 1 - (1 - p)^n. As n gets larger, P_ind[n,1] tends to 1 > p. $\endgroup$
    – muzzlator
    Jul 21, 2017 at 8:29
  • $\begingroup$ @muzzlator: thanks! I replaced my example with your simpler one. $\endgroup$ Jul 23, 2017 at 5:48
  • 1
    $\begingroup$ "since intuitively, the dependence between the variables can only increase the number of successes" By the same reasoning, a positive correlation should also increase the number of failures. Hence, the reasoning should be wrong. $\endgroup$
    – leonbloy
    Jul 30, 2017 at 20:01

2 Answers 2

3
+50
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ This direction looks promising! I added a summary, is that what you meant? I see two remaining issues: First, the success probability of each single variable should be exactly $p$, not at least $p$. Second, the success probability of each $j$-tuple of variables should be at least $p^j$. I do not know how to prove this. $\endgroup$ Jul 31, 2017 at 6:02
  • $\begingroup$ The success probability for each variable in the formulation I gave above is exactly $p$. The thing is we don't necessarily use $1-A$ probability for the $(k-1)$-tuples when $A = p^k$ as in the case for $n = 3, k = 2, p = 0.1$. The second proof you mention is a little tougher, it's intuitively true (these words are the sure sign of a statement being false? :)) but it's a little trickier to prove formally $\endgroup$
    – muzzlator
    Jul 31, 2017 at 13:25
  • $\begingroup$ I re-edited some of the things you added to what I think is a more accurate summary of where we are so far. LMK what you think $\endgroup$
    – muzzlator
    Jul 31, 2017 at 13:35
  • 1
    $\begingroup$ The j-dependency constraints do not seem to be redundant. See the examples at the end of my answer. $\endgroup$
    – g g
    Aug 1, 2017 at 14:43
  • 1
    $\begingroup$ Ha. Nice examples. Guess I should have realized it was false the moment I said it was intuitive. I did have a go at trying to prove it and noticed it started to seem false the moment I tried to show quantity unrelated to p was supposed to scale something by p. $\endgroup$
    – muzzlator
    Aug 1, 2017 at 16:55
2
+100
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much. But what bound do you suggest for the case where $p^k$ does not work? $\endgroup$ Jul 31, 2017 at 14:20
  • $\begingroup$ included now the $p^k$ constraint which I forgot before, solution should be complete now. $\endgroup$
    – g g
    Aug 1, 2017 at 7:31
  • $\begingroup$ Great answer. I'll give you a bounty tomorrow. $\endgroup$ Aug 3, 2017 at 17:47

You must log in to answer this question.

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