MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.