Kids are taught that when crossing the street, they should check for oncoming cars by looking left, then right, then left again.  Why left again?  Isn’t that redundant?  You already looked left.

You could imagine that the advice makes sense because during the time he was looking right, cars appeared coming from the left that he did not see when he first looked left.  But then wasn’t the first left-look a waste?  Maybe not because at the first step if he saw cars coming from the left then he knows that he doesn’t have to look right yet.  But then shouldn’t he insert a look-right at the beginning in hopes that he can pre-empt an unnecessary look-left?

I thought for a while and in the end I could not come up with a coherent explanation for the L-R-L again sequence.  When you can’t find an example, you prove the counter-theorem.  Here it is.

Take any stochastic process for arrival of cars.  Consider the L-R-L again strategy.  Consider the first instance when the strategy reveals that it is safe to cross.  Let t be the moment of that instance that the L-R-L again strategy looks to the left for the second time.

Now, consider the alternative strategy R-L.  This strategy begins by looking right, then when there is no car coming from the right it looks left and if there is no car coming from the left he crosses.  If he is using R-L there are two possibilites.

  1. The traffic from the right is not clear until time t.  In this case, by definition of t, he will next look left and see no traffic and cross.
  2. The traffic from the right clears before t.  Here, he looks left and either sees clear traffic and crosses or sees traffic.  In the latter case he is now in exactly the same situation as if he was following L-R-L from the beginning.  He waits until the traffic from the left clears and then re-initializes R-L.

In all cases, he crosses safely no later than he would with L-R-L again, and in one case strictly sooner.  That is, the strategy R-L dominates the strategy L-R-L.  Three further observations.

  1. This does not mean that R-L is the optimal strategy.  I would guess that the optimal strategy depends on the specific stochastic process for traffic.  But this does say definitively that L-R-L is not optimal and is bad advice.
  2. He might get run over by a car if after looking left for the last time he crosses without noticing that a car has just appeared coming from the right.  But this would also happen in all the same states when using L-R-L.  Crossing the street is dangerous business.
  3. I believe that the rationale for the L-R-L advice is based on the presumption that the child will not be able to resist looking left at the beginning.  Starting by looking right is very counterintuitive.  Under this theory, the longhand for the advice is “Go ahead and look left at the beginning, but when you see that the traffic is clear, make sure you look right as well before crossing.  And if you see traffic and have to wait for it to clear, don’t forget to look left again before starting out because a car may have appeared in the time you were looking right.”
About these ads