I needed to compute an upper bound for a probability that I think is small but can't quite prove it.
Let's say I have a sequence of events of lenght M, all independent, and with probabilities:
$A : p$
$B : p$
$C : (1-2p)$
I want to get an upper bound for the probability that somewhere in my sequence of M events there is a subsequence of consecutive events such that B occurs N times in that subsequence and A never occurs in that subsequence. If you can think of this as a game: if A occurs, I get N credits, every time B occurs I lose 1 credit. If C occurs nothing happens. I loose the game if I run out of credits. I want to know the probability of loosing the game. In my case $N$ is something like $100$ and $p$ is something like $1/N = 1/100$. $M$ is quite large, like $10^{10}$ or something like that.
I have tried to compute the exact expression to then aproximate but I was not very sucessfull.
One of my ideas was that if I just ignore the C's, my proability should be smaller than $M/2^N$.
When I tried to write the exact formula I got:
$$ \sum_{m=0}^{M-N}\sum_{t=N}^{M-m}\binom{t}{N}p^N(1-2p)^{t-N}. $$
The idea was: I have $M-N$ places to start the sequence, then I know the sequence can be of lenght $t$ minimum N and maximum $M-m$. For a sequence of length $t$ I have N places to put event B with joint probability $p^N$. Then in the other $t-N$ places I must have C with joint probability $(1-2p)^{t-N}$.
But I failed to get a useful upper bound. Doing it in a computer is obviously impossible as well.