1
$\begingroup$

Given $N$ initial draws, a constant probability of success $P$ (with replacement), and the fact that each success adds $D$ additional draws, find the probability that our draws will be exhausted with $S$ total successes (ie. $SD$ additional draws were added)

My thoughts are to start with the binomial distribution to get the probability of $S$ successful draws in $N+S*D$ attempts. This will overestimate the probability as it will count cases where $1$ of the final $D$ draws was a success, or $2$ of the final $2D$ draws were successes, or....

I can subtract the combinations for each of these overestimates, but they have intersections (having 1 draw in the final $D$ and another in the penultimate $D$ fits both the examples above), so I will go from an overestimate to an underestimate, and I will need to add those combinations back in, but if $S$ is $3$ or higher, I think that adding those back in gets us back to an overestimate, causing us to oscillate around the answer I am looking for.

If I continue this way $S$ times I should land on the correct answer, but I am hoping for a formula or method of doing so that would not scale up so much in complexity with increased $S$. Is there a better way of going about this?

$\endgroup$
  • $\begingroup$ I have fixed the error in the problem statement to show that $SD$ additional draws were added $\endgroup$ – Hoog Jan 9 at 15:45
  • 1
    $\begingroup$ I haven't been able to come up with anything on this. I tried using the reflection principle (see e.g. the accepted answer to this question), but I don't think it works because the unequal step sizes break the symmetry. I also tried using generating functions to divide out multiple returns to $0$, but $\sum_n\binom{Sn}nx^n$ doesn't seem to have a closed form for $S\gt3$. (The result for $S=3$ is fascinating, though.) $\endgroup$ – joriki Jan 9 at 19:32
  • 1
    $\begingroup$ Another approach would be to use inclusion–exclusion to systematically account for the over/underestimates that you describe, but that, too, doesn't really seem tractable, because if you have multiple zeros the number of paths depends in detail on their placement. $\endgroup$ – joriki Jan 9 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.