# Bypassing a series of stochastic stoplights

In order for me to drive home, I need to sequentially bypass $(S_1, S_2, ..., S_N)$ stoplights that behave stochastically. Each stoplight, $S_i$ has some individual probability $r_i$ of being red, and an associated probability, $g_i$, per minute of time of turning from red to green.

What is the probability density function for the number of minutes I spend waiting at the $N$ stoplights on my way home?

Update 2: The first update is incorrect since the $T$ variable $T$ is a mix of a discrete and continuous measures (as Sasha noted), to generate our distribution for $T$, and assuming all lights are the same, we need to compute the weighted sum:

Distribution for $x = T = \sum^N_{j=1} Pr[j$ lights are red upon approach$] * Erlang[j, g]$

Here, Pr[$j$ lights are red upon approach] is just the probability of $j$ successes in $N$ trials, where the probability of success is $r$.

In the case where all the lights are unique, we perform the same sort of weighted sum with the hypoexponential distribution, where we have to account for all possible subsets of the lights, with unique $g_i$, being red.

Update 1 (see update 2 first, this is incorrect!): from Raskolnikov and Sasha's comments, I'm supposing that the following is the case:

If we allow all the spotlights, $S_i$ to be the same, following from (http://en.wikipedia.org/wiki/Erlang_distribution), we have an Erlang (or Gamma) distribution where $k = N$ and the rate parameter is $\lambda = \frac{g}{r}$. This gives us a mean waiting time at all the red lights, $x = T$ minutes, of $\frac{k}{\lambda} = \frac{N}{(\frac{g}{r})}$ and the following PDF for $x = T$:

$\frac{\lambda^k x^{k-1} e^{-\lambda x}}{(k-1)!}$ = $\frac{(\frac{g}{r})^N T^{N-1} e^{-(\frac{g}{r}) T}}{(N-1)!}$

Now if all of the stoplights are not the same, following from (http://en.wikipedia.org/wiki/Hypoexponential_distribution), we have a hypoexponential distribution where $k = N$ and the rate parameters are $(\lambda_1, \lambda_2, ..., \lambda_N) = ((\frac{g_1}{r_1}), (\frac{g_2}{r_2}), ..., (\frac{g_N}{r_N}))$. This gives us a mean waiting time at all of the red lights, $x = T$ minutes, of $\sum^{k}_{i=1} \frac{1}{\lambda_i} = \sum^{N}_{i=1} \frac{1}{(\frac{g_i}{r_i})}$. I'm having trouble, however, understanding how to correctly calculate the PDF for the hypoexponential distribution.

Is the above correct? (answer: no, but the means are correct)

-
$T=\sum_i r_i T_i$ with $T_i$ exponential random variables with parameters $g_i$. If the $r_i=r$ and $g_i=g$ for all $i$, then this leads to an Erlang distribution. –  Raskolnikov Sep 14 '12 at 11:03
@Raskolnikov If we allow that all stoplights are the same, what would be the shape and rate parameters for the Erlang distribution? –  C.W. Sep 14 '12 at 11:35
Then, $T\sim \mbox{Erlang}(N,g/r)$ according to a quick glance here. –  Raskolnikov Sep 14 '12 at 11:38
On second thought, I think my formula for $T$ is not quite correct. It should really be $T=\sum_i B_i T_i$ with $B_i$ a Bernoulli random variable with success probability $r_i$. –  Raskolnikov Sep 14 '12 at 11:42
You forgot to take into account Sasha's comment. The variable $T$ has a probability measure that is a mix of a discrete and an absolutely continuous measure. There is a probability $\prod_i(1-r_i)$ that you have to wait exactly $0$ seconds in total. –  Raskolnikov Sep 14 '12 at 18:43

Let $T_i$ denote the time you wait on each stop-light. Because $\mathbb{P}(T_i = 0) = 1-r_i > 0$, $T_i$ is not a continuous random variable, and thus does not have a notion of density.
Likewise, the total wait-time $T = T_1+\cdots+T_N$ also has a non-zero probability of being equal to zero, and hence has no density.