Combinatoric problem with the development of intersection of union of events

Question

Hello,

Let say you have events $A_1, A_2, ..., A_r$. Each event has a probability $p$ to occur and the events are independent. Let $b$ be an integer with $b\leq r$.

Compute the probability of the event :

$$ \cap_{i=1}^{r-b+1} \cup_{j=0}^{b-1} A_{i+j} = (A_1\cup A_2\cup ...\cup A_b) \cap (A_2\cup A_3\cup ... \cup A_{b+1}) \cap ... \cap (A_{r-b+1}\cup ... \cup A_r)$$

If you develop this expression, we find many reductions and simplifications but it seems hard, at least to me, to find the exact probability for big values of $r$ even though events are independent and with the same probability.

Answer 1

This event means that in the sequence of outcomes $ A_1, ..., A_r $ you don't have $ b $ adjacent falses. Suppose $ b \le t $. Let $ r-t $ be the index of the last true event in that sequence. Then $ 0 \le t < b $ you get this sequence from an $ r-t-1 $ long sequence with this property by appending t falses and a true. Thus, if you name the probability of this event a(r), you have the recurrence $$ a(r) = \sum_{0 \le t < b} p(1-p)^ta(r-t-1), $$ and the starting conditions $ a(r) = 1 $ if $ r < b $.

Fix any errors in the above argument, then try to solve the recurrence. For any fixed $ b $, this is a linear recurrence, so it has an explicit solution. With $ b $ as a parameter, it might be hard, though you could still ask for an approximation. The Concrete Mathematics book may help.