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.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+