Puzzle question finding Calvin

Question

How to solve this problem. I have reckoned that I need to take as optimization problem finding minimum value for waiting time. Any suggestions?

Calvin has to cross several signals when he walks from his home to school. Each of these signals operate independently. They alternate every 80 seconds between green light and red light.At each signal, there is a counter display that tells him how long it will be before the current signal light changes. Calvin has a magic wand which lets him turn a signal from red to green instantaneously. However, this wand comes with limited battery life, so he can use it only for a specified number of times.

a. If the total number of signals is 2 and Calvin can use his magic wand only once, then what is the expected waiting time at the signals when Calvin optimally walks from his home to school?

b. What if the number of signals is 3 and Calvin can use his magic wand only once?

Answer 1

Solution to (a) and (b) and the general case can be found in this paper, together with code and a simulation to verify the results. I think it is instructive for those new to statistical modeling.

a. Expected trip time is 8.75 sec. Optimally, wand should be used on red light if the counter is above 20 sec.

b. Expected trip time is 21.32 sec. Optimal wand usage at first light is if the counter is above 31.25 sec, and 20 at the second if there is a charge left.

c. Consult the paper for the recursive 10-line code that solves the general case. For example, if there are 4 lights and Calvin has 2 charges, then the expected trip time is 11.8 sec with the optimal wand usage.

Answer 2

Answer to part (a).

Calvin arrives at the first light. It is green with probability $\frac{1}{2}$. In this case Calvin uses the wand at the second light. So, half of the time Calvin doesn’t need to wait at any lights.

Half of the time Calvin arrives at the first light when it is red. He uses his wand when the timer at the first light exceeds a threshold $t$. This occurs with probability $\frac{80-t}{80}$ after which Calvin can be expected to wait at the second light on 50% of occasions (the expected wait will be $40$s). Calvin does not use his wand at the first light with probability $\frac{t}{80}$. In this case he waits an expected $\frac{t}{2}$s at the first light and never at the second (he's saved his wand).

In expectation Calvin's waiting time is: $\frac{1}{2}(0 + 0) + \frac{1}{2}( \frac{80-t}{80}\frac{1}{2}40 + \frac{t}{80}\frac{t}{2} )$

Taking derivatives with respect to $t$ one can see this expectation is minimized when $t = 20$ and that therefore that Calvin can be expected to wait 8.75 seconds at the lights.

Answer 3

I'll assume that the times at which the signals change are uniformly distributed and Calvin doesn't know anything about the remaining lights; his only information is from the display at the current light.

Then we need to find the expected waiting times $T_{ij}$ if Calvin has to pass $i$ lights and has $j$ uses of the magic wand left, where $1\le i\le 3$ and $0\le j\le1$. We have $T_{i0}=40i$, since each signal takes an expected $40$ seconds to change. Also $T_{11}=0$, since Calvin will use the magic wand in this case.

Now for $T_{21}$, if the time displayed on the penultimate light is $t$, his expected total waiting time will be $40$ if he uses the wand and $t$ otherwise, so he should use the wand if $t\gt40$, and then his expected total waiting time is $T_{21}=\frac12\cdot40+\frac12\cdot\frac{40}2=30$.

For $T_{31}$, if the time displayed on the first light is $t$, his expected total waiting time will be $80$ if he uses the wand and $t+30$ if he doesn't, so he should use the wand if $t\gt50$, and then his expected total waiting time is $T_{31}=\frac38\cdot80+\frac58\cdot\left(\frac{50}2+30\right)=\frac{515}8=64.375$.

Thus, with a single well-timed use of the wand, Calvin can reduce the expected waiting time of three lights down to just a bit more than one and a half times the expeced waiting time of one light.

More generally, if the total expected waiting time for $i-1$ lights with $1$ wand use is $T_{i-1,1}=40(i-1)-80+\theta$ and the first of $i$ lights displays time $t$, then Calvin should use the wand on the first light if $T_{i-1,1}+t\gt40(i-1)$, and thus if $t\gt80-\theta$, and then his expected total waiting time is

\begin{align} T_{i1} &= \frac{\theta}{80}\cdot40(i-1)+\frac{80-\theta}{80}\cdot\left(\frac{80-\theta}2+40(i-1)-80+\theta\right) \\ &=40(i-1)-\frac{(80-\theta)^2}{2\cdot80} \\ &=40i-80+\theta-\frac{\theta^2}{160}\;, \end{align}

so with each additional traffic light the difference $\theta$ between the optimal savings of $80$ and the expected savings is reduced by $\frac{\theta^2}{160}$. If we scale the times so that the maximal waiting time for one light is $1$, this becomes $\frac{\theta^2}2$, and the first few values of $\theta$ are $\frac12$, $\frac12-\frac{\left(\frac12\right)^2}2=\frac38$, $\frac38-\frac{\left(\frac38\right)^2}2=\frac{39}{128}$, in agreement with the above. In the limit of a large number of traffic lights, $\theta$ goes to $0$ and the one use of the wand effectively saves the average wait at two lights.

Answer 4

After further thought I think I have the right answer, at least for part a [2 signals; 1 wand]. The previous two answers above were on the right track of thinking but subtle nuances were missing.

So first you need to make some key assumptions:

1. Let's assume that Calvin can only see the signal that is coming up and not the next one. [Since the problem states that the signals are independent you want to structure the problem solving mechanism for that to hold true].

2. Calvin will be following some sort of optimal walking strategy.

3. When they say alternates between Red and Green every 80 seconds, I will assume 40 seconds on Red 40 seconds on green.

4. We have no idea about the synchronization or lag between the two signals.

**

I would suggest using an excel sheet to build a static simulation of all the possible signal combinations. You should have 4 columns. 1st column - counter for signal one, 2nd column colour of signal 1, 3rd and 4th columns, likewise, for signal 2.

i.e. 40R @ signal 1 and 1R @ signal ; 39R @ signal 1 and 1R @ signal 2; .... You should have 6400 combinations or rows in your sheet for each situation.

We will assume a uniform distribution, that is every situation has an equal likelihood of happening, due to our four assumptions. Thus the probability of Calvin being or starting his walk to land on any of those 6400 combinations is 1/6400 = 0.00015625

Note on assumptions: When modeling you always want to setup your model to make the least assumptions possible or the assumptions closest to reality.

Now we move on to the modeling part. Put yourself in Calvin's shoes. If you had to come up with the optimal walking strategy in 60 seconds without a computer, pen, paper or a calculator - how would you come up with a rough answer ? Let's call this first take at the walking strategy as a "Naive Optimal Approach".

As Calvin my thought process would be -

There are 4 combinations:

1. Red at the first signal; Red at the second signal
2. Red at the first signal; Green at the second signal
3. Green at the first signal; Red at the second signal
4. Green at the first signal; Green at the second signal

I need to make a decision to wave at the first signal [if i see Red], or if i should wait at the first signal and then wave at the second signal. Regardless of what is shown at the counter [this is important, because this is why we are calling this the naive approach. The counter is actually providing you with information that is relevant to come up with an approach. We will get to that in the later stage].

So let's do a very simple analysis of the two scenarios:

Scenario 1: I do not wait at signal 1, if i see Red [Wave wand at 1]

1. RR - Wait at R1 = 0; Wait at R2 = x --> Total Wait = x
2. RG - Wait at R1 = 0; Wait at G2 = 0 --> Total Wait = 0
3. GR - Wait at G1 = 0; Wait at R2 = 0 --> Total Wait = 0
4. GG - Wait at G1 = 0; Wait at G2 = 0 --> total Wait = 0

Scenario 2: I wait at signal 1, if I see Red [Wave wand at 2]

1. RR - Wait at R1 = x; Wait at R2 = 0 --> Total Wait = x
2. RG - Wait at R1 = x; Wait at G2 = 0 --> Total Wait = x
3. GR - Wait at G1 = 0; Wait at R2 = 0 --> Total Wait = 0
4. GG - Wait at G1 = 0; Wait at G2 = 0 --> total Wait = 0

So from our naive decision making technique we can see scenario 1 would be more effective since we don't add a wait at signal 1, for scenario "2", because we do not know what is ahead.

Now we stretch that thinking further, seems like the optimal strategy would be to wave at 1, if the counter for red is at, above, or below a number. This is where the ridiculous build of the 6400 combinations come in handy.

Code an if statement, first testing, if the signal at 1 is Red and counter at signal 1 displays 3 [Let's call 3 the 'thresh hold'. We picked an arbitrary start, you will see why]. I will wait. So you only add to your total wait time for if it is Red at signal 1 and the counter is 3, 2, or 1. The wait time at signal two won't be there because it will be green or you will wave your wand.

Now for the important part, nest another if statement where if Signal 1 is Red and the counter is 4, 5, 6,....,40. I will wave my wand at the first. Thus wait time at the first signal will be zero, but add the counter time if signal two is red, if it is green do not add the counter time. Make sure you code this logic right [sounds simple but it is trick; cross check manually 2 or 3 such combinations to see your formula/code is computing the final wait time right].

This is the most important part of the final logic for this. You need to go to the Red and signal 1 and green at signal 2 section. Here you will need to have a separate if statement which is as following. If Signal one is Red and counter is less than or equal to the 'threshold' [3] that you picked, then the wait time is whatever is displayed at the counter, if signal 1 is red and counter higher than the threshold then wait time is 0. Why is this important ?

**Because we are using the counter to make our decision. We are testing at each 'thresh hold' value, if we used that 'thresh hold' as our decision making/optimal walking approach, what would the total expected wait time be for the simulation of all 6400 possible combinations. To help you understand and see how the assumptions tie in. We don't know the synchronization of the signals. We decided if it's red on the first signal and 3 seconds or less on the counter, we would rather wait. To avoid say using the wand on the first and then landing on the second signal with a red and a counter that would most likely be higher than 3 seconds. Thus we actually increase our wait time.

However, that is a guess, because we don't know anything about the synchronization. It is also, just as likely, given it is a uniform distribution and all values have the same probability. That we wait when it's red at the first signal and displaying 3 on the counter, only to land on the second signal and find out it is green. Thus we never really got to use the wand. i.e. hypothetically if we knew the synchronization and we knew the next signal was green we would have used the wand at the first signal and the total wait time for those situations would be - 0 and not the 3, 1, or 1 second of wait as defined by the 'thresh hold'.

Once you are done doing this, multiple the total wait times by the 1/6400 probability and sum the entire array/column. This will be your E(x) when thresh hold is 3. Do this for all thresh holds 1, 2, 3, 4,...., 40. And plot the points. You should get a curve like this. The bottom of the curve is your optimal walking strategy. So from my graph it is 10 seconds. Even though I started with a hypothesis that 3 would be my optimal, turns out i should use 10 seconds as my thresh hold for my optimal walking strategy because when i use that, the E(x) for all 6400 situations is the lowest - 4.5312 seconds.