Finding the probability that at most n events take place on any interval during a given time period

Question

I am interested in the general case, but let us start with a smaller example. Suppose that cars arrive to a street with intensity $\lambda$ per minute. We would like to know the probability that at least two cars have arrived on the street during any five minute interval in the next hour. How can we find this?

My initial thought was to use complementary event: 1 - the probability that at most one car is on the street in any five minute period during the next hour. Hence my reasoning was something like $1 - \int_0^{55}\mathbb{P}(N(s + 5) - N(s) \leq 1)ds - \int_{55}^{60}\mathbb{P}(N(60) - N(55 + s) \leq 1)ds$.

But I quickly realized that finding this probability might not be that easy, since the intervals we are considering overlap, namely $N(5)$ and $N(5 + s)$ overlap except for the infinitesimal point $s$. So then, is the correct way to integrate just $\mathbb{P}(N(s) \leq 1$ over the region? Moreover, I think that my line of reasoning is missing something critical, since I do not see a reason, why the summation would not end up being negative.

Answer 1

Generating Function Approach

Let's compute the probability that no $5$ minute span has more than $1$ car entry.

---

Poisson with $\bf{1}$ Minute Resolution

Poisson says the probability that $0$ cars enter the street in a given minute is $e^{-\lambda}$, and the probability that $1$ car enters the street in a given minute is $\lambda e^{-\lambda}$.

Let a minute with one car be represented by '${+}$', which has a probability of $\lambda e^{-\lambda}$. Let a minute with no cars be represented by '${-}$', which has a probability of $e^{-\lambda}$.

The $60$ minute span can be uniquely built from atoms of '${-}$' and '${+}{-}{-}{-}{-}$' followed by an optional terminal atom of '$\text{+}$', '$\text{+}{-}$', '$\text{+}{-}{-}$', '$\text{+}{-}{-}{-}$'

This gives a generating function of $$ f_\lambda(x)=\frac{1+\overbrace{\ \ \lambda e^{-\lambda}x\ \ }^{+}+\overbrace{\lambda e^{-2\lambda}x^2}^{+-}+\overbrace{\lambda e^{-3\lambda}x^3}^{+--}+\overbrace{\lambda e^{-4\lambda}x^4}^{+---}}{1-\underbrace{\ \ \ e^{-\lambda}x\ \ \ }_{-}-\underbrace{\lambda e^{-5\lambda}x^5}_{+----}}\tag1 $$ The probability that in no $5$ minute span of the hour there is more than $1$ car is $$ \begin{align} \left[x^{60}\right]f_\lambda(x) &=e^{-60\lambda}\left(1+60\lambda+1540\lambda^2+22100\lambda^3+194580\lambda^4\right.\\ &\left.+1086008\lambda^5+3838380\lambda^6+8347680\lambda^7+10518300\lambda^8\right.\\[2pt] &\left.+6906900\lambda^9+1961256\lambda^{10}+167960\lambda^{11}+1820\lambda^{12}\right) \end{align}\tag2 $$ Computing the complementary probability, we get the probability that two or more cars will enter in a single $5$ minute period during an hour:

---

The Generating Function

In order to prevent any $5$ minute span from having more than $1$ car entry, above, we break down the $60$ minutes into $1$ minute atoms:

The $60$ minute span can be uniquely built from atoms of '${-}$' and '${+}{-}{-}{-}{-}$' followed by an optional terminal atom of '$\text{+}$', '$\text{+}{-}$', '$\text{+}{-}{-}$', '$\text{+}{-}{-}{-}$'

and we compute the probabilities for each of these atoms using the Poisson Distribution:

Poisson says the probability that $0$ cars enter the street in a given minute is $e^{-\lambda}$, and the probability that $1$ car enters the street in a given minute is $\lambda e^{-\lambda}$.

In the generating function, we represent an '${+}$' by $\lambda e^{-\lambda}x$ and an '${-}$' by $e^{-\lambda}x$. Thus, the power of $x$ counts the minutes and the coefficients accumulate the probabilities. Thus, for each of these atoms, we include a factor of $$ \overbrace{\phantom{i^5}e^{-\lambda}x\phantom{i^5}}^{-}+\overbrace{\lambda e^{-5\lambda}x^5}^{+----}\tag3 $$

To account for any number of the standard atoms ('${+}$' and '${+}{-}{-}{-}{-}$'), we total the product of all powers of the standard atom: $$ \sum_{k=0}^\infty\left(e^{-\lambda}x+\lambda e^{-5\lambda}x^5\right)^k=\frac1{1-e^{-\lambda}x-\lambda e^{-5\lambda}x^5}\tag4 $$ Since products of the standard atoms of length $4$ or more will end in at least $4$ '${-}$'s, we add optional atoms of '${+}$', '${+}{-}$', '${+}{-}{-}$', or '${+}{-}{-}{-}$'. This is included in the generating function as a factor of $$ \overbrace{\phantom{iw^2}1\phantom{iw^2}}^\text{none}+\overbrace{\phantom{i^2}\lambda e^{-\lambda}x\phantom{i^2}}^{+}+\overbrace{\lambda e^{-2\lambda}x^2}^{+-}+\overbrace{\lambda e^{-3\lambda}x^3}^{+--}+\overbrace{\lambda e^{-4\lambda}x^4}^{+---}\tag5 $$ Thus, we arrive at the generating function, $f_\lambda(x)$, given in $(1)$. To get the probability for a span of $60$ minutes, we look at the coefficient of $x^{60}$: $\left[x^{60}\right]f_\lambda(x)$.

---

Poisson with $\boldsymbol{\frac1n}$ Minute Resolution

We can handle finer resolutions using atoms of '${-}$' and '${+}\overbrace{{-}{-}\cdots{-}}^{5n-1}$'. To simplify notation, we will write $e^{-\lambda/n}x=u$. $$ \begin{align} g_{\lambda,n}(x) &=\frac{1+\frac\lambda{n}e^{-\lambda/n}x+\frac\lambda{n}e^{-2\lambda/n}x^2+\cdots+\frac\lambda{n}e^{-(5n-1)\lambda/n}x^{5n-1}}{1-e^{-\lambda/n}x-\frac\lambda{n}e^{-5\lambda}x^{5n}}\tag{6a}\\ &=\frac{1+\frac\lambda{n}u\,\frac{1-u^{5n-1}}{1-u}}{1-u-\frac\lambda{n}u^{5n}}\tag{6b}\\ &=\frac{\left(1-u-\frac\lambda{n}u^{5n}\right)+\frac\lambda{n}u}{\left(1-u-\frac\lambda{n}u^{5n}\right)\left(1-u\right)}\tag{6c}\\ &=\frac1{1-u}+\frac{\frac\lambda{n}u}{\left(1-u-\frac\lambda{n}u^{5n}\right)(1-u)}\tag{6d}\\ &=\frac1{1-u}+\left(\frac1{1-u-\frac\lambda{n}u^{5n}}-\frac1{1-u}\right)\frac1{u^{5n-1}}\tag{6e} \end{align} $$ Since all coefficients of $\frac1{1-u}$ are $1$, we get $$ \begin{align} \left[x^{60n}\right]g_{\lambda,n}(x) &=e^{-60\lambda}\!\left[u^{60n}\right]g_{\lambda,n}(x)\tag{7a}\\[9pt] &=e^{-60\lambda}\!\left[u^{65n-1}\right]\frac1{1-u-\frac\lambda{n}u^{5n}}\tag{7b}\\ &=e^{-60\lambda}\!\left[u^{65n-1}\right]\sum_{k=0}^\infty\left(u+\frac\lambda{n}u^{5n}\right)^k\tag{7c}\\ &=e^{-60\lambda}\!\left[u^{65n-1}\right]\sum_{k=0}^\infty\sum_{j=0}^k\binom{k}{j}u^{k-j}\left(\frac\lambda{n}\right)^ju^{5nj}\tag{7d}\\ &=e^{-60\lambda}\sum_{j=0}^{12}\binom{65n-1-(5n-1)j}{j}\left(\frac\lambda{n}\right)^j\tag{7e} \end{align} $$ For $n=1$, $\text{(7e)}$ agrees with $(2)$.

---

Infinite Resolution

The limit as $n\to\infty$ of $\text{(7e)}$ is $$ \begin{align} p(\lambda) &=e^{-60\lambda}\sum_{j=0}^{12}\frac{(65-5j)^j}{j!}\lambda^j\tag{8a}\\ &=e^{-60\lambda}\left(\vphantom{\frac11}\right. 1+60\lambda+\frac{3025}2\lambda^2+\frac{62500}3\lambda^3+\frac{1366875}8\lambda^4\\ &+\frac{2560000}3\lambda^5+\frac{367653125}{144}\lambda^6+\frac{30375000}7\lambda^7+\frac{30517578125}{8064}\lambda^8\\ &+\frac{800000000}{567}\lambda^9+\frac{284765625}{1792}\lambda^{10}+\frac{15625000}{6237}\lambda^{11}+\frac{9765625}{19160064}\lambda^{12} \left.\vphantom{\frac11}\right)\tag{8b} \end{align} $$

At $\frac14$ car per minute, the probability is $99.91\%$ that two or more cars will enter in a single $5$ minute period during an hour.

Answer 2

Conditional Probability Approach

Poisson says that in an hour, the probability that $n$ cars have entered is $$ e^{-60\lambda}\frac{(60\lambda)^n}{n!}\tag1 $$ Given that $n$ cars have entered in the hour, the probability that none is within $5$ minutes of another is the ratio of the volumes of the simplices $$ \frac{\left|\left\{x_k\ge0:\sum\limits_{k=1}^nx_k\le60-5(n-1)\right\}\right|}{\left|\left\{x_k\ge0:\sum\limits_{k=1}^nx_k\le60\right\}\right|}=\left(\frac{13-n}{12}\right)^n\tag2 $$ Each $x_k$ is the time from car $k-1$, or the beginning of the hour, to car $k$. With $n-1$ buffers of $5$ minutes removed, we get the numerator; without the buffers removed, we get the denominator.

Thus, Bayes' Theorem gives $$ \begin{align} p(\lambda) &=\sum_{n=0}^{12}e^{-60\lambda}\frac{(60\lambda)^n}{n!}\left(\frac{13-n}{12}\right)^n\tag{3a}\\ &=e^{-60\lambda}\sum_{n=0}^{12}\frac{(65-5n)^n}{n!}\lambda^n\tag{3b}\\ &=e^{-60\lambda}\left(\vphantom{\frac11}\right. 1+60\lambda+\frac{3025}2\lambda^2+\frac{62500}3\lambda^3+\frac{1366875}8\lambda^4\\[3pt] &+\frac{2560000}3\lambda^5+\frac{367653125}{144}\lambda^6+\frac{30375000}7\lambda^7+\frac{30517578125}{8064}\lambda^8\\[3pt] &+\frac{800000000}{567}\lambda^9+\frac{284765625}{1792}\lambda^{10}+\frac{15625000}{6237}\lambda^{11}+\frac{9765625}{19160064}\lambda^{12} \left.\vphantom{\frac11}\right)\tag{3c} \end{align} $$ This matches the result from $(8)$ of my previous answer.