Scribd
Upload
8 views

Introduction to Markov Chains

The document is a worksheet for Math 344 on Markov Chains, containing problems related to shark tanks, a rat on a grid, and a network of nodes. It involves setting up transition matrices, computing probabilities of movements, and analyzing the long-term distribution of states. The worksheet is divided into three parts, each focusing on different scenarios and requiring calculations and interpretations of Markov processes.

Uploaded by

pqpxbgz84z
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views

Introduction to Markov Chains

The document is a worksheet for Math 344 on Markov Chains, containing problems related to shark tanks, a rat on a grid, and a network of nodes. It involves setting up transition matrices, computing probabilities of movements, and analyzing the long-term distribution of states. The worksheet is divided into three parts, each focusing on different scenarios and requiring calculations and interpretations of Markov processes.

Uploaded by

pqpxbgz84z
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Math 344 Markov Chains Spring 2025

Markov Worksheet 1

Part A: Consider two shark tanks A and B that are


connected. Sharks are continuously swimming, and for our
problem they are always swimming clockwise in tank B and
counterclockwise in tank A. Sharks prefer a large tank so A B
we make the following observation: when sharks reach the
intersection of the tanks, sharks swimming in tank B will
remain in tank B 75% of the time while sharks swimming in
tank A will only remain in tank A 50% of the time.

The states (nodes) for this problem are tanks A and B, and the step for this problem includes one
pass through the intersection of tanks A and B.

1) What is the probability that a shark starting in tank B will be in tank A after 2 steps?
step 1 … B→A B→B
step 2 … A→A B→A
A→B B→B

2) Set up a transition matrix, 𝑷, with each “from” state aligned with a row and each “to” state
aligned with a column.

3) Compute 𝑷2 . How are the entries related to dot products between the “from” states and the “to”
states? What do the entries represent?
Math 344 Markov Chains Spring 2025

Part B: Another Rat


1 2
Consider the grid shown here. Imagine that a rat lives on this grid.
At the end of each minute, the rat moves or does not move to
3 4 5
another square based on the following rules:
✓ If the rat is in an odd-numbered square, then it moves to an
adjacent square. There are equal probabilities that it will move to any adjacent square.
✓ If the rat is in an even-numbered square, then it might stay in the square or move to an adjacent
square. All his possible choices have equal probability.

1. Using the rows to represent the “from” squares and the columns to represent the “to” squares,
write down the Markov matrix, 𝑷, that describes this situation.

2. Assume the rat is in square #1. Compute the probability that it moves to square #4 in exactly
two steps. Explain how this result is related to matrix multiplication.

3. Compute the Markov matrix, P, to the powers 3, 6, 10, and 100. Interpret the entries in terms of
probabilities for the rat’s movements within the grid. What do you observe about the high
powers of the Markov matrix? What does your observation imply about the long-term
distribution of the amount of time the rat spends in each square?
Math 344 Markov Chains Spring 2025

4. Assume 120 rats live on this grid of squares and all move according to the rules listed above.
Suppose all 120 rats are initially placed into square #5. What would be the expected
distribution of rats after one minute? Two minutes? Three minutes? What is the distribution
after many minutes?

5. Consider the steady state answer from question #4. What happens if this is the starting
distribution of rats? What does that imply about the steady state vector in terms of Eigenvalues
and Eigenvectors?

6. If the rat starts in square #4, what is the expected number of times that it will visit square #5
during the next 24 minutes? Reference the ideas in problem 3.
Math 344 Markov Chains Spring 2025

Part C: Consider the network to the right.

1 2
The states or nodes for this problem are depicted as
triangles and are numbered 1, 2, and 3. These nodes are
connected by arched paths and signals can travel in either
direction along an arched path. During each step the
signals within the network must change nodes.
3
1) What is the probability of a signal traveling from node 2
to node 1 in exactly 3 steps? (Hint: how many ways are
there to move from node 2 to node 1 in exactly 3 steps?)

2) Set up a transition matrix, 𝑷, with each “from” node aligned with a row and each “to” node
aligned with a column.

3) Given an initial signal distribution of 𝒔⃑0 = [100 100 100 ]T , what is the vector 𝑷T 𝒔⃑0 , and
what does it represent?

75
4) Given an initial signal distribution of 𝒔⃑0 = [100 100 100 ]T , what is the vector (𝑷T ) 𝒔⃑0 , and
what does it represent?

You might also like