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
- Since the tickets were issued to the registered owner of the
vehicle, a lot of them claimed that it was someone else driving at the
time. They were reluctant to say just who was driving, but were
adamant that it wasn't them.
- Many motorists complained that the cadets were not fully
trained, and thus were not competent to issue tickets.
- Not surprisingly, perhaps, motorists were reluctant to complain
that the cadets were trying to enforce the written traffic laws
instead of enforcing the unwritten rules that seem to govern traffic in
Boston. (If you don't know these rules, I suggest taking the T.)
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.
Street intersections to be monitored
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 that satisfies . You can
do this in two ways.
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?
- Write the equation as a homogeneous system and solve, but
remember that the solution you want must be a probability
- Add the condition to your system of
equations and solve directly.
- 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.)
This document was generated using the
LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997,
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
William W. Farr