0

Assume we repeatedly conduct $n$ Bernoulli trials in parallel, each with probability $p$ of success. We repeat this until we have at least $L$ successes. I am looking for the expected number of repetitions. For example, consider we throw $n$ coins in parallel, keeping a sum of all heads that showed up in total so far. Until this sum exceeds our threshold $L$, we repeat to throw $n$ coins in parallel, update our total and then stop once the total is higher than $L$. What is the expected number of repetitions?

The approach from this answer does not seem to be directly applicable here, since in the answer we stop after we reached $L$ successes and repeat the Bernoulli trials sequentially. While in the question posed here, we conduct $n$ parallel trials sequentially.

EDIT

Find below a python script that simulates the above experiment a 1000 times and returns the average number of repetitions needed. It also compares it to the formula mentioned in the comments, which seems to be close, but not exactly matching:

from scipy.stats import bernoulli
import numpy as np
import tqdm
n = 1024
p = 0.05
L = 6000

def run_experiment_once():
    count = 0
    tries = 0
    while count < L:
        r = bernoulli.rvs(p, size=n)
        count += np.sum(r)
        tries += 1
    return tries


def run_experiment():
    res = []
    for i in tqdm.tqdm(range(1000)):
        res.append(run_experiment_once())
    return np.mean(res)


sim = run_experiment()
q = 1-p
formula_res = L/(n*(p/q))
print("Simulation", sim)
print("formula_res", formula_res)
dieter.ml
  • 161
  • It looks to be the integer part of $\frac{L}{n \tfrac{p}{q}}$ where $q:=1-p$ – Jean Marie Oct 20 '21 at 20:54
  • Thank you! Could you sketch how you arrived at this answer? – dieter.ml Oct 20 '21 at 21:56
  • Have you simulated your "experiment" on a computer in order to see if this formula agrees with the result of the simulation ? – Jean Marie Oct 20 '21 at 22:32
  • When one of the coins comes up heads, do you stop flipping it, or do you keep flipping all of them every time and count multiple successes from a single coin towards trying to reach $L$? – Daniel Schepler Oct 20 '21 at 22:33
  • @DanielSchepler I flip all $n$ coins each round. Then count all successes from each of the $n$ coins towards reach $L$. If $L$ has not been reached, I go for another round, flip $n$ coins again and so forth. I want to figure out the expected number of rounds – dieter.ml Oct 20 '21 at 22:37
  • Very roughly, I would expect the generating function for the answer to satisfy something like $f(x) = \frac{1}{1-x} + ((1-p) + px)^n f(x)$. – Daniel Schepler Oct 20 '21 at 22:44
  • 1
    @JeanMarie I did -- the formula comes close, but does not exactly match the mean. I updated the question with the simulation code. For the parameters in the code ($n=1024,p=0.05,L=6000$), the simulation averages an $117$ or $118$ tries, while the formula would expect $111$ tries. – dieter.ml Oct 20 '21 at 22:51

1 Answers1

0

I'd say L/(np) is a better semi-answer. Gives the right value when L=n=1. But the more general answer seems a bit larger than L/(np), but not sure the discrete nature can be handled nicely or easily.

TickaJules
  • 170