Probability that no three events happen in a pre-defined window

Question

Consider a Poisson process with arrival rate $\lambda$ arrivals per unit time. Given a window of time $W$ and a total of $k$ events, what is the upper bound of the probability that no three events happen in that window? Said another way, if events are numbered $1,2,\ldots,k$, what is the upper bound of $$P(\operatorname{gap}(j,j+2) \geq W \text{ for all } 1 \leq j \leq k-2)?$$

The problem in estimating this for me has been that while each successive gap is distributed exponentially, $\operatorname{gap}(1,3)$ and $\operatorname{gap}(2,4)$ are dependent. So, my best upper bound so far is obtained by just completely ignoring half the gaps: $$ P\bigl(\operatorname{gap}(j,j+2) \geq W\ \text{ for }\ 1 \leq j \leq k-2\bigr) < P\bigl(\operatorname{gap}(j,j+2) \geq W\ \text{ for }\ 1 \leq j \leq k-2,\ j \text{ odd}\bigr). $$ The right hand side is approximately $P(\operatorname{gap}(1,3) \geq W)^{(k-1)/2} = (\exp(-\lambda W)(1+\lambda W))^{(k-1)/2}$

because $exp(-\lambda W)(1+\lambda W)$ is the probability that 0 or 1 arrivals happened in duration W, and there are $(k-1)/2$ such odd gaps.

Is there a better upper bound?

Answer 1

Let $G_j$ be the event that $\operatorname{gap}(j,j+2)>W$. In terms of the interarrival times $X_i$ we can write this as the event that $X_{j+1}+X_{j+2}>W$. The independence of the interarrival times implies that $G_j$ is independent of $G_{k}$ for $j-k>1$. This will make the calculation very simple. All we need is $$ P(G_j)=P(X_{j+1}+X_{j+2}>W)=(1+\lambda W)e^{-\lambda W} $$ and $$ P(G_j,G_{j-1})=P(X_{j+1}+X_{j+2}>W,X_j+X_{j+1}>W) =\int_0^\infty dx_{j+1}\int_{\operatorname{max}(0,W-x_{j+1})}^\infty dx_{j}\int_{\operatorname{max}(0,W-x_{j+1})}^\infty dx_{j+2} \lambda^3e^{-\lambda(x_j+x_{j+1}+x_{j+2})} =\left(\int_0^Wdx_{j+1}\int_{W-x_{j+1}}^\infty dx_{j}\int_{W-x_{j+1}}^\infty dx_{j+2}+\int_W^\infty dx_{j+1}\int_0^\infty dx_{j}\int_0^\infty dx_{j+2}\right) \lambda^3e^{-\lambda(x_j+x_{j+1}+x_{j+2})} =2e^{-\lambda W}-e^{-2\lambda W} $$ for $j>1$. Let $S_l$ be the event that all gaps up to and including gap $l$ have length greater than $W$. Then $S_1=G_1$ and for $l>1$ $$P(S_l)=P(G_l|S_{l-1})P(S_{l-1})=P(G_l|S_{l-1})P(G_{l-1}|S_{l-2})\cdots P(G_{2}|S_1)P(G_1).$$ The independence of the interarrival times simplifies the conditional probability: $$ P(G_l|S_{l-1})=P(G_l|G_{l-1},G_{l-2},\dots,G_1)=P(G_l|G_{l-1})=P(G_l,G_{l-1})/P(G_{l-1}) =\frac{2-e^{-\lambda W}}{1+\lambda W}. $$ So $$P(S_l)=\frac{(2-e^{-\lambda W})^{l-1}}{(1+\lambda W)^{l-2}}e^{-\lambda W}$$ for any $l>1$. You are interested in $P(S_{k-2})$.

What follows was my initial answer to the wrong question, namely asking about the probability of all windows having a length less than W. This can be ignored, I just leave it in case someone is interested in this alternative question. Let $G_j$ be the event that $\operatorname{gap}(j,j+2)<W$. In terms of the interarrival times $X_i$ we can write this as the event that $X_{j+1}+X_{j+2}<W$. The independence of the interarrival times implies that $G_j$ is independent of $G_{k}$ for $j-k>1$. This will make the calculation very simple. All we need is $$ P(G_j)=P(X_{j+1}+X_{j+2}<W)=1-(1+\lambda W)e^{-\lambda W} $$ and $$ P(G_j,G_{j-1})=P(X_{j+1}+X_{j+2}<W,X_j+X_{j+1}<W) =\int_0^Wdx_j\int_0^{W-x_j}dx_{j+1}\int_0^{W-x_{j+1}}dx_{j+2}\lambda^3e^{-\lambda(x_j+x_{j+1}+x_{j+2})} =1-2\lambda We^{-\lambda W}-e^{-2\lambda W} $$ for $j>1$. Let $S_l$ be the event that all gaps up to gap $l$ have length less than $W$. Then $$P(S_l)=P(G_l|S_{l-1})P(S_{l-1}).$$ The independence of the interarrival times simplifies the conditional probability: $$ P(G_l|S_{l-1})=P(G_l|G_{l-1},G_{l-2},\dots,G_1)=P(G_l|G_{l-1})=P(G_l,G_{l-1})/P(G_{l-1}) =\frac{1-2\lambda We^{-\lambda W}-e^{-2\lambda W}}{1-(1+\lambda W)e^{-\lambda W}}. $$ So $$P(S_l)=\frac{\left(1-2\lambda We^{-\lambda W}-e^{-2\lambda W}\right)^{l-1}}{\left(1-(1+\lambda W)e^{-\lambda W}\right)^{l-2}}$$