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?



Probability that no three events happen in a pre-defined window
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}}$$


