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