Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
If $W$ can be arbitrary, I think we can set $\lambda=1$ without loss of generality. –  Johan Wästlund Jun 27 '13 at 5:58
    
Yes, that's true. –  Pankaj Gupta Jun 27 '13 at 17:37
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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}$ –  Pankaj Gupta Jun 27 '13 at 17:40
    
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$. –  Gustav Jun 27 '13 at 20:12
    
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? –  Pankaj Gupta Jun 27 '13 at 23:43
1  
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})$) –  Pankaj Gupta Jun 28 '13 at 6:18
    
Sorry, it is not $1 - P(S_{k-2})$ that we are after, but 1 - Prob(some gap is less than W). Seems fixable. –  Pankaj Gupta Jun 28 '13 at 6:25
show 3 more comments

Your Answer

 
discard

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.