# Robot in a Maze

## Instructions:

This project is to be done in groups of two or three students, as assigned by
the instructor.. Groups

of size four or more are not permitted. Each group will turn in one solution to
the tasks described below, and each

member of the group will receive the same grade on the project. You should be
careful to understand each part of

the project – related questions may appear on exams.

## Submission Guidelines:

Please use the following guidelines when preparing your project for submission:

1. Include a cover page on which each member of the group signs their full
name. Also, in the top right hand

corner of each page submitted, write the names (first and last, written legibly)
of each group member. You

should not include student ID or social security numbers.

2. Only use one side of each sheet of paper and staple the pages together.

3. Presentation will be considered when grading this project. You should take
care to write legibly and hand in

full sheets of paper with no fringe, tears, etc. You should also clearly label
each problem and submit these in

order.

4. Give justification (in complete sentences!) for your answers

5. Be academically honest. This means, for example, providing a list of
sources other than the textbook (if any)

that you used to do the assignment; stating clearly that you’re copying or
mimicking an example from the book

in order to do the assignment (if appropriate).

6. The project is due at the beginning of class. Under certain circumstances,
late submissions may be accepted,

but they will be penalized.

**Setup: **A robot is placed in the maze below and is programmed to move
at random. Each minute, the robot either

stays in the room it is currently located or chooses a hallway at random and
moves into the adjoining room, and

each possibility is equally likely . For example, if the robot happens to be in
room 11, then there is a 1/3 chance

it will move next to room 10, a 1/3 chance it will move next to room 7, and a
1/3 chance it will stay in room 11.

## Project Tasks:

1. Find the appropriate transition matrix P for the Markov chain describing the movement of the robot.

2. Recall that a probability vector is a vector all of whose entries are
between 0 and 1 and such that the sum of

these entries is 1. Suppose v is probability vector in R^{12} whose i-th entry
gives the probability that the robot

is currently located in room i. What does the vector Pv tell you and why?

3. Carefully explain the real-world significance of the matrix P^{2}. Be sure to
justify, in your own words, the

meaning of the entries of the matrix P^{2}. It’s helpful to give explicit examples,
of the sort “The (3, 2) entry of

P^{2} tells me blah, blah, blah.” Do the same thing for P^{3}, P^{4}, etc.

4. An important concept in studying stochastic matrices is that of
“regularity”. A stochastic matrix is called

regular if some power of it has no zero entries. Show that P is regular. Also,
find the smallest integer k such

that P^{k} has no zero entries. What is the practical meaning (in terms of
properties of the maze) of this value

of k?

5. Calculate P^{k} for a very large value of k. (One fast way to do this is to
compute P^{2}, P^{4}, P^{8}, etc. by repeatedly

squaring .) What do you notice about the entries of P^{k} for k very large?

6. What is the approximate probability that the robot will wind up in each of
the twelve rooms after a very long

time has passed? To answer this, it might help to use the answer to the previous
part, and to remember that

P^{k}e_{j} is the j-th column of P^{k}. Does your answer depend on where the robot begins
his journey?

7. Find a probability vector that solves the equation Px = x. This is called
a steady state vector for the system.

What’s the connection between this vector and your answer to the previous part?

8. What connection is there between the entries of the steady-state vector
and the nature of the maze? Can you

explain heuristically why some of the entries of the steady-state vector are
equal to others?

9. Suppose the maze is now modified so that the hallway joining rooms 3 and 7
is permanently blocked off. This

leads to a new transition matrix — call it Q. Is Q regular? How can you be sure
of your answer?

## Computers:

You can conceivably do this project using just a fancy
calculator. I encourage you, however, to use the

software package Maple (or an equivalent one ). For one thing, it is far easier
to enter, manipulate, and view large

amounts of data in Maple than it is on a calculator, and this project will
require the use of rather large matrices.

Also, I believe it is a valuable experience to learn how to use a computer
algebra system such as Maple.

Maple is available on the Mathlab computer system and everyone in class should have access to Mathlab.

Here are some helpful tips concerning Maple. These are based on Version 10 of Maple

• You will need to “import” the linear algebra
package into Maple. Enter the command with (LinearAlgebra):

at the very start of your Maple session. (The trailing colon suppresses a long
list of commands that are imported

with the LinearAlgebra package — to see this list, replace the colon with a
semi-colon.)

• By default, Maple only displays in full matrices
of size at most 10 × 10. To increase this to 12, use

interface (rtablesize = 12);.

• To learn more about a Maple command or topic, type
in the command name or topic preceded by a question

mark. For example, try entering ?Matrix; into Maple. (You can also use the
menu-driven help documentation.)

• Here are a couple of useful commands:

– The command B := Matrix([[a,b,c],[d,e,f]]); sets
B to be the evident 2 × 3 matrix. Note that in

Maple, all commands should be ended with a “;” (or with a “:” if you don’t want
to see the output of the

command for some reason).

– You can use plus, minus, and exponents in the
usual manner for matrix operations. Instead of using an

asterisk for matrix multiplication , however, use the period key. For example,
enter A and B to be your

favorite 3 × 3 and 2 × 3 matrices, and try B.(A+3A^2);.

– The command ReducedRowEchelonForm(A); puts the matrix A in to reduced row echelon form.

– Suppose A is a matrix with rational numbers as
entries and you would rather have them as decimals.

Then you could use the command map(evalf,A);. Suppose you want to round off the
entries of A to 3

decimal places of accuracy. (This is useful for printing a large matrix so that
it fits on one page.) Then

use map(x -> evalf(x,3),A);.

Prev | Next |