3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ If $W$ can be arbitrary, I think we can set $\lambda=1$ without loss of generality. $\endgroup$ Jun 27, 2013 at 5:58
  • $\begingroup$ Yes, that's true. $\endgroup$ Jun 27, 2013 at 17:37

1 Answer 1

1
$\begingroup$

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}}$$

$\endgroup$
8
  • $\begingroup$ Can you explain the line that calculates $P(G_j, G_{j-1})$ ? Also, in that line, there is a typo as $G_{j-1}$ should correspond to $X_j + X_{j+1}$ $\endgroup$ Jun 27, 2013 at 17:40
  • $\begingroup$ Pankaj, I have added an extra line to the calculation in the above answer, showing how to express the joint probability as an integral over the probability densities of the exponential random variables $X_i$. The limits on the integrals are such that $x_j+x_{j+1}<W$ and $x_{j+1}+x_{j+2}<W$. $\endgroup$
    – Gustav
    Jun 27, 2013 at 20:12
  • $\begingroup$ Thanks. But I get a much more complicated result of that triple integral. Do you mind double-checking your results and/or adding a few intermediate steps in that calculation? $\endgroup$ Jun 27, 2013 at 23:43
  • 1
    $\begingroup$ Gustav, while this is trivially fixable, also note that the question asks not that all gaps are less than W, but that no gap is less than W (i.e., $1 - P(S_{k-2})$) $\endgroup$ Jun 28, 2013 at 6:18
  • $\begingroup$ Sorry, it is not $1 - P(S_{k-2})$ that we are after, but 1 - Prob(some gap is less than W). Seems fixable. $\endgroup$ Jun 28, 2013 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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