next up previous

Boston Traffic Problem


This project deals with a simple model of traffic monitoring, using a regular Markov Chain. Before you begin working on this project, you should study the material in section 8.3 of the text. (This project is based on an example taken from Applications of Linear Algebra by Rorres and Anton.)


In the last year or two, there was a minor controversy in Boston caused by the Boston Police Department using cadets, who had not graduated from the police academy yet, to monitor traffic infractions at intersections in Boston. Each cadet would be given a certain number of intersections to watch. When he or she witnessed a violation of the traffic regulations, they were supposed to take note of the license number and write up a ticket, which was then mailed to the registered owner of the vehicle in question.

This program resulted in a considerable number of tickets being issued, and a lot of complaints from drivers, including the following points.

Anyway, your task is not to take sides in this controversy, but to model the following situation. Suppose a cadet is assigned to monitor the eight intersections, numbered 1 through 8, shown in figure below.

Figure 1: Street intersections to be monitored

\includegraphics [width=3in]{}

His instructions are to remain at each intersection for an hour and then to either remain there or move to a neighboring intersection. For example, if the cadet had just completed an hour at intersection 1 he could either stay at intersection 1 for the next hour, or go to either intersection 2 or intersection 4. To avoid establishing a pattern the cadet is told to choose the new intersection on a random basis, with each possible new choice to be equally likely. For example, suppose the cadet has just completed an hour at intersection 1. His next intersection can be either 1, 2, or 4, each with a probability of 1/3. Note that his probability of going to any other intersection except 1, 2, or 4 is zero. Every day the cadet starts at the location at which he stopped the day before and makes a new choice. You may assume that he ended the previous working day by finishing his hour at this same intersection.


Construct the transition matrix A where entry aij denotes the probability that the cadet's new intersection will be intersection i if his previous intersection was intersection j.
Suppose that the cadet starts his first day at intersection 3. Predict the probable location of the cadet after 3, 5, and 8 hours. That is, use your transition matrix and the initial state vector to predict the state after 3, 5, and 8 hours.
Continue your work in the previous exercise by predicting the state after 12, 24, 36, and 48 hours. What conclusion do you draw?
Start over, using a different intersection for the cadet to start at on the first day and repeat the two previous exercises. What conclusion do you draw now?
Experiment further with different initial state vectors and ``large'' numbers of hours. Does it make any difference what the initial state vector is?
Now explore the behavior of powers of the transition matrix for ``large'' values. (The same values as in the previous exercises should be sufficient.) What conclusion can you draw?
Find the fixed point or steady state distribution. That is, the vector $\mathbf{x}$ that satisfies $A\mathbf{x} = \mathbf{x}$. You can do this in two ways.
Write the equation as a homogeneous system and solve, but remember that the solution you want must be a probability distribution.
Add the condition $x_1+x_2+\ldots+x_8 = 1$ to your system of equations and solve directly.
Having done this, compare your result for the steady state distribution to the results you obtained in the first four exercises. What conclusions can you draw?
Can you suggest a strategy for a driver to follow to minimize the risk of getting a ticket? That is, are there certain intersections to be avoided? (Suggesting that the driver simply obey the rules is not appropriate - this is Boston, after all.)

About this document ...

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split +0 project_template.tex.

The translation was initiated by William W. Farr on 9/10/1998

next up previous

William W. Farr