Waiting for Stoplights

A walker in a city is at the green point in the upper-right corner of the plot. Her goal is the red point at the origin. Thus, at each intersection of streets, she goes either to the west or to the south. She has to go intersections to the west and intersections to the south. Suppose that at each intersection, there is always a green light in one of the two possible directions and a red light in the other direction; the walker always chooses the direction where she sees the green light. Also suppose that the walker faces the lights randomly, that is, there is a probability of 1/2 that the green light is to the west and also a probability of 1/2 that the green light is to the south.
As long as she does not come to the axes, she does not need to wait at any intersection. As soon as she comes to an axis, she will stay on it and may well come to an intersection at which there is a red light in the direction she has to go; this happens with probability 1/2. We are interested in the number of stops during her walk, that is, in the number of intersections where she has to wait because of a red light.
The Demonstration shows sample paths of the walker for up to 1000 intersections of streets, the number of encountered red lights, and the expected number of red lights.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


Snapshots 1, 2, 3: these plots show the results when the starting point is , , or
When the starting point is for , the expected number of red lights is 1.76, 2.51, 3.98, 5.63, 7.97, 12.6, and 17.84, respectively. Thus, the expected number of red lights grows slowly, approximately as .
The expected number of red lights is easy to calculate with Mathematica by using recurrence relations. Let be the expected number of red lights when starting from . The recurrence relations are:
for and ,
for ,
for ,
The Demonstration is based on problem 18 in [1]. See also [2].
[1] P. J. Nahin, Digital Dice: Computational Solutions to Practical Probability Problems, Princeton: Princeton University Press, 2008.
[2] H. Sagan, "On Pedestrians, City Blocks, and Traffic Lights," Journal of Recreational Mathematics, 21(2), 1989 pp. 116–119.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.