What is the optimal strategy when driving to my university: Wait or take alternative route and (possibly) wait?

Question

When bicycling to my university, I'm faced with a difficult decision. The situation is shown here:

I have to get to point marked with the $\times$, but in order to do so, I must cross a big road with a traffic light at both places where crossing is possible. If the first traffic light (at the bottom) is green, then there's no debate; I simply cross and go up $A$ with no waiting time at all. The choice arises when it is red (as is always the case anyway), since I can choose to wait for the first light to change, or go up a smaller road $B$ and then try to cross at the second light.

Let's assume that the two traffic lights are identical w.r.t. the percent of the time they are red (let's call this quantity $\Theta$), but that the second is phase-shifted with $\tau$ w.r.t. the first, s.t. the second changes to e.g. green a time $\tau$ after the first. The length $L$ of the paths are identical and I bicycle with a constant speed $v$ (although I suspect these last two are irrelevant to the solution). I don't know anything about the light before I arrive at it. The question then becomes

If I arrive at a random time during which the first traffic light is red, given $\Theta$ and $\tau$ (and $L$ and $v$), should I

1. wait at the first light and go by path $A$, or should I
   
2. go by path $B$

in order to minimize waiting time?

The type of solution I'm looking for can better be formulated if we first look at two examples:

The $\mathbf{I}$'s represent the time during which the traffic light is red - the space in between them represent the green lights. The drawn lines represent my position if I chose to go by $B$. If I arrive at the first red light during the blue stretch, I should go by $B$; if I, on the other hand, arrive during the red stretch, I should go wait and go by $A$. As can be seen from the two scenarios $(a)$ and $(b)$ (where the lines represent my position should I choose path $B$, and where the slope is determined by $L$ and $v$), my choice depends on $\tau$, which is the only parameter that has been changed.

If we call the length of the blue strip $t_{\text{go}}$ and the length of the red strip $t_{\text{wait}}$, s.t. $t_{\text{go}}+t_{\text{wait}}=\Theta$, the solution should be of the form $$t_{\text{go}}(\tau)$$

I don't think $v$ and $L$ should play a role, since the effect of changing these can be incorporated into $\tau$, so we could probably set $v=L=1$. I'm guessing there should be a pretty simple geometric way of solving this, but for the time being it is eluding me.

Some random observations: If $v=\frac{L}{\tau}$ it doesn't matter what I choose. Also, if the second light was independent of the first, I should always go by $B$, since there I will at least have a $1-\Theta$ chance of getting a green light.

Any help is much appreciated!

Answer 1

Let's choose a unit of time so that each light cycle is exactly one unit long.

As you noticed, if $v = \frac L\tau$ it does not matter which choice you make. In fact, since you will arrive at the second light exactly $\frac Lv$ units of time later than you arrived at the first light (if you choose to try the second light), the expected waiting time at the second light will be exactly the same as the expected waiting time of a light at the location of the first light, but phase-shifted $\frac Lv$ units earlier than the second light, which itself is phase-shifted $\tau$ units later than the first light. So choosing to go to the second light is equivalent to making an irrevocable choice to phase-shift the first light $\tau - \frac Lv$ units later. Moreover, since phase-shifting by any whole number of units of time has no effect, we can say that choosing the second light is equivalent to phase-shifting the first light by $\delta$, where $0 \leq \delta < 1$ and there is an integer $N$ such that $N + \delta = \tau - \frac Lv$.

Let's suppose you arrive at the first light at time $t$, where $t=0$ if the light is just turning red and $t=\Theta$ if the light is just turning green again. Assuming the first light is red when you arrive, $0 \leq t < \Theta$. In addition to that constraint, there are three possible cases to consider: \begin{align} t &< \Theta + \delta - 1 \tag1 \\ \Theta + \delta - 1 \leq t &< \delta \tag2 \\ \delta \leq t & \tag3 \\ \end{align} Which cases are even possible depends on $\Theta$ and $\delta$. Essentially, by shifting the light cycle by $\delta$, you turn the light green for some portion of the time when it would have been red. Suppose the part of the cycle that was red and is now green starts at time $\alpha$ and ends at time $\beta$. If $\delta > 1 - \Theta$, then $\alpha = \Theta + \delta - 1$; otherwise $\alpha = 0$, ruling out case $(1)$. If $\delta < \Theta$, then $\beta = \delta$; otherwise $\beta = \Theta$, ruling out case $(3)$. If $\delta = 0$ then Case $(2)$ is ruled out (and it makes no difference which path you take); but Case $(2)$ is possible whenever $\delta \neq 0$.

In case $(1)$, you get a green light at time $\Theta + \delta - 1$, which is $1 - \delta$ units of time earlier than you would have gotten without the phase shift.

In case $(2)$, the phase shift turns the light green, and you can cross $\Theta - t$ units of time earlier than you would have without the phase shift.

In case $(3)$, you arrived at the first light after the portion of the light cycle that is turned green by the phase shift; you end up crossing $\delta$ units of time later than you would have without the phase shift.

Assuming that the distribution of your arrival time within the light cycle is uniform, the expected change in waiting time (positive for increased waiting, negative for decreased waiting), given that you arrive at the first light when it is red, is therefore \begin{align} E[\Delta T] &= \frac 1\Theta \int_0^\alpha (\delta - 1) \,dt + \frac 1\Theta \int_\alpha^\beta (t - \Theta) \,dt + \frac 1\Theta \int_\beta^\Theta \delta \,dt \\ &= \frac \alpha\Theta(\delta - 1) + \frac 1\Theta \left(\frac12 \beta^2 - \frac12 \alpha^2\right) - \frac{\beta - \alpha}{\Theta} \Theta + \frac{\Theta - \beta}{\Theta} \delta \\ &= \frac{1}{2\Theta}(\beta^2 - \alpha^2) + \frac \alpha\Theta(\delta - 1) + \alpha - \beta + \frac{\Theta - \beta}{\Theta} \delta \\ &= \frac{1}{2\Theta}(\beta^2 - \alpha^2) + \frac \alpha\Theta(\Theta + \delta - 1) + \frac{\Theta - \beta}{\Theta} (\Theta + \delta) - \Theta \end{align}

The reason for the seemingly peculiar rearrangement of terms on the last line of the equation above is that we know that either $\alpha = 0$ (in which case the term involving $\alpha$ disappears) or $\alpha = \Theta + \delta - 1$ (in which case the term becomes $\frac1\Theta (\Theta + \delta - 1)^2$); we also know that either $\beta = \Theta$ (in which case the term involving $\beta$ disappears) or $\beta = \delta$ (in which case that term becomes $\Theta - \frac1\Theta \delta^2$). We then have the following four possible answers, depending on whether $\delta \leq 1 - \Theta$ (that is, $\alpha = 0$) and on whether $\delta \geq \Theta$ (that is, $\beta = \Theta$):

Case $\Theta \leq \delta \leq 1 - \Theta$: $$E[\Delta T] = -\frac{\Theta}{2}.$$

Case $\delta \leq 1 - \Theta, \delta < \Theta$: $$E[\Delta T] = -\frac{\delta^2}{2\Theta}.$$

Case $\delta > 1 - \Theta, \delta \geq \Theta$: $$E[\Delta T] = \frac{(\Theta + \delta - 1)^2 - \Theta^2}{2\Theta}.$$

Case $1 - \Theta < \delta < \Theta$: $$E[\Delta T] = \frac{(\Theta + \delta - 1)^2 - \delta^2}{2\Theta}.$$

You should wait at the first light if $E[\Delta T]$ is positive, but go to the second light if $E[\Delta T]$ is negative. If $E[\Delta T] = 0$ either choice is equally good.

In the first two formulas for $E[\Delta T]$, where $\delta \leq 1 - \Theta$, clearly it is always advantageous to try the second light if the first is red, unless $\delta = 0$ (in which case it makes no difference). In the other formulas, where $\delta > 1 - \Theta$, we have $\Theta + \delta - 1 > 0$, so $(\Theta + \delta - 1)^2 - \Theta^2$ is negative if and only if $\Theta > \Theta + \delta - 1$, that is, if and only if $\delta < 1$, which is true. For similar reasons, $(\Theta + \delta - 1)^2 - \Theta^2$ is negative if and only if $\Theta < 1$, which presumably is also true.

So it seems that except for the case $\delta = 0$ (where it obviously makes no difference which path you take), it is always advantageous to go to the second light if the first is red.

Answer 2

Let's start by representing the phase of a light by the full circle, of which the first $\theta$ arc corresponds to a green light, and let $\tau$ represent the phase shift between the two lights. Let $\phi$ represent the phase shift induced by the time to go from the first light to the second light.

The picture shows in red the time when the first light is green, and in blue the time when the second light is green. If you take a point $s$ not in $[0,\theta]$, you'll be at the second light at $s+\phi$. So if you wait in front of the first light you would wait $2\pi -s$, and if you go for the second light you would wait $w(s)$ (see below).

The wait function when going to the other light is in three cases, either you arrive before the second light is green, after, or you arrive during this time. $$ w(s) = \begin{cases} t - (s+\phi) & \mathrm{ if }\; s+\phi <\tau\\ 2\pi + \tau - (s+\phi) & \mathrm{ if }\;s+\phi >\tau + \theta\\ 0 & \mathrm{ otherwise} \end{cases} $$

Now the strategy "let's go to the second light" is better than the "wait at the first light strategy" if and only if $\mathbb{E}[2\pi -s]$ is greater than $\mathbb{E}[w(s)]$ over $s \in ]\theta,2\pi[$ (assuming you have no additional information besides the color of the light when you arrive in front of the first light).

Edit: I forgot some factors in my initial calculations, so the result was completely wrong. It seems that David K did things right anyway.

By the way, there's a very simple argument to see that going to the second light is always at least as good as waiting. The transformation $s \to s + \phi$ is measure-preserving, so what matters is how much of the circle is covered by its codomain; and since this area is at most $2\pi-\theta$ (which is attained when both lights are synchronized and with a phase shift of $2\pi$), this means that it cannot do worse than waiting at the first light.

(However this assumes that all lights stay green for the same amount of time, so this may not apply to the real-life example).