5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @InterstellarProbe No I am not, though the term has been thrown around in a couple of classes. How can we evaluate the Lebesgue integral? Also, what is your take on my line of reasoning? $\endgroup$ Commented Dec 7, 2020 at 19:57
  • $\begingroup$ My take on your line of reasoning is that if $N(s)$ is the number of cars that have arrived at the intersection, then $N(60)$ is the total number of cars that arrived over the hour you are looking at. So, $N(60)\le 1$ is the event that at most, within an hour, only one car arrived in the intersection. That is not at all the same as no more than one car arrived during a five minute period. As I am thinking of it, I don't think it matters that the intervals overlap. I think your initial suggestion was correct. $\endgroup$ Commented Dec 7, 2020 at 20:54

2 Answers 2

4
$\begingroup$

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:

enter image description here


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} $$ enter image description here

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.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the amazing visuals! I have few questions. Firstly, could you either walk me trough (or direct me to appropriate resources regarding) how the generating function was derived in this case? Why is the expression such a fraction and what would be the general expression behind them (this would make it easier to reflect to it :). Secondly, should we take into consideration the different ways of choosing the arrangements of $o$ and $n$? Lastly, the generating function you derived is the pdf of a five minute span, or? What does the $[x^{60}]$ mean before the function? $\endgroup$ Commented Dec 8, 2020 at 8:05
  • 1
    $\begingroup$ I have added a description of how we derive the generating function. The $\left[x^{60}\right]$ operator extracts the coefficient of $x^{60}$. $\endgroup$
    – robjohn
    Commented Dec 8, 2020 at 13:20
  • $\begingroup$ If you have the time and/or will could you go over or direct me to some sources that explain why we can brake the 60 minute period to these particular atoms? I'm still a bit confused as why do we not have to consider all the possible starting moments of a five minute period. I guess this information is somehow encoded in the generating function? In addition, is it so that the information for the possible sequences (e.g. $nnonn$) is encoded in the optional terminal atoms? I've seen that these cases are handled with the number of combinations. What exactly does the same trick here? $\endgroup$ Commented Dec 8, 2020 at 19:43
  • $\begingroup$ The atoms are the way of breaking up the time so that no $5$ minute period contains more than one car entry. That is, any minute in which $1$ car enters, there must be at least $4$ minutes with no cars. I have amended my answer to handle $n$ atoms in a minute ($1/n$ minute resolution). The last plot compares the Poisson approximation with $1$ minute intervals to the case with infinite resolution. $\endgroup$
    – robjohn
    Commented Dec 9, 2020 at 13:18
2
$\begingroup$

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.

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .