Homework answers / question archive / Discrete — Time Markov Chains We have only been going through this stuff in class, so it shouldn’t be more advanced than using these types: 1

Discrete — Time Markov Chains We have only been going through this stuff in class, so it shouldn’t be more advanced than using these types: 1

Computer Science

Share With

---

Discrete — Time Markov Chains
We have only been going through this stuff in class, so it shouldn’t be more advanced than using
these types:
1. Introduction
Part 1. Managing Engineering Data
2. Basic Structures
3. Containers
4. Files and Regular expressions
5. Modules and Packages
1 Introduction
1.1 Presentation of the Problem
Markov chains are pervasive in science and engineering.
The objective of this assignment is to design a program that manages discrete-time Markov
chains, DTMC for short. Namely, the program should:
— Read a DTMC from a text file and write a DTMC into a text file.
— Assess the DTMC at given steps and print out the results into files.
— Build a DTMC from a time series and vice-versa.
1.2 Mathematical Background
Recall that a discrete-time Markov chain can be described as a directed graph, i.e. as a pair
(S,T), where
~ § is a finite set of states.
0.4 0.1
5 ¢ —_ me
0.6 0.9
Figure 1: A possible DTMC for the sea condition measured on a simplified Douglas sea scale
Table 1: Matrix encoding of the DTMC pictured in Figure 1
CALM MODERATE ROUGH
CALM 0.6 0.4 0.0
MODERATE 0.6 0.3 0.1
ROUGH 0.0 0.9 0.1
— T is a finite set of transitions, i.e. of triples (s,p,t), where s and t are states called
respectively the source and the target states of the transition and p is a probability, i.e. a
real number between 0 and 1.
We shall assume moreover that:
i) There is no loop, i.e. no transition from a state to itself.
ii) For any pair of states s and t, there is at most one transition from s to t.
Finally, the DTMC must verify the following property.
iii) For all state s, the sum of the probabilities labeling the transitions going out of s must be
less or equal to 1.
Figure 1 shows the graphical representation of a possible DTMC for the sea condition mea-
sured on a simplified Douglas sea scale.
A DTMC (S,T) can be encoded as a square matrix M of dimension n = |S|, where |5S|
denotes the number of elements in the set S:
— The cell M(i,j), 1 <1#4 J <n, contains the probability p if there is a transition labeled
with p from the state of index 7 to the state of index j and 0 otherwise.
— The cell M(z,7), 1 <7 <n, contains the remaining probability, i.e. 1—) 75-1 n ja; M(4 3).
The matrix corresponding to the DTMC pictured in Figure 1 is given in Table 1.
A distribution of probabilities over the states can thus be represented by means of line vector
n of size n, such that )>,_,_,, 7(i) = 1.
If the distribution of probabilities over the states at a given step is 7, then the distribution
at the next step is p=a x M.
More generally, if the initial distribution of probabilities is 79, the distribution of probabilities
at step k is p= 7 x M*.

In practice, DTMC representing engineering problems tend to be very large and sparse, i.e.
they contain 0.0’s but for a tiny fraction of their cells. To put it differently, the average number
of transitions going out of states is much lower than the number of states.

Encoding such Markov chain with square matrices would be much too much memory and
time consuming. Consequently, Markov chains are encoded as sparse matrices, i.e. as list of

transitions. Moreover, the product 7 x M* is calculated by means of successive vector by matrix
products:
ax M* = (.--((1x M)xM)---)xM (1)

Consequently, the key operation we need to implement is the product of a vector by a sparse
matrix.

To conclude this remainder on DTMC, recall that it is possible to estimate the sojourn time
in each state by averaging, over a sufficiently large number of steps, the probability to be in
each state.

1.3 Requirements
The objective of this assignment is to show your Pythonic skills.

Here follows a number of requirements.

1. You must provide your program together with a small document explaining how it is orga-
nized, what it is doing (which functionalities are implemented) and reporting experiments
you have performed with it.

The quality of a program is judged along three criteria: its completeness, its correctness
and its maintainability:
— A program is complete if it provides all functionalities demanded by the client. Some
functionalities are however more important than other. You must first concentrate
on the main functionalities, then develop the “nice-to-have” ones.
— A program is correct if it is bug free. To ensure that your program is correct, you
must test it extensively. Design tests before writing the first line of code. There is no
such a thing than a program or a functionality that works “most of the time”. Either
it works, or not. If you are not able to make a functionality work, do not deliver it.
— A program is maintainable if it is well presented, if the identifiers are significant, and
so on. But before all, a program is maintainable if it well organized and as modular
as possible. Separate the concerns.
2 Tasks
For this assignment you are asked to design several data structures and to implement quite a
few functions. Each of these functions must be thoroughly tested.

The assignment consists in the following tasks.

MarkovChain SeaCondition
CALM —> MODFRATE: 0.4;
MODERATE —> CALM: 0.6;
MODERATE —> ROUGH: 0.1;
ROUGH —> MODERATE: 0.9;
end
ProbabilityDistribution pO of SeaCondition
CALM: 1.0;
MODERATE: 0.0;
ROUGH: 0.0;
end
Figure 2: Example of text file content encoding a DTMC and a probability distribution
2.1 Data structure to encode DTMC and probability distributions
The information regarding a DTMC consists (at least) of the following data.
— Its name;
— Its set of states;
— Its set of transitions.
The information regarding a probability distribution consists (at least) of the following data.
— Its name;
— A reference to the DTMC;
— For each state of the DTMC, a probability.

Task 1. Design a data structure to encode DTMC and implement associated management
functions. Your data structure must be essentially a sparse matrix. It is advised to
create specific data structure to implement states and transitions.

Task 2. Design a data structure to encode probability distributions over the states of a DTMC
and implement associated management functions.

Task 3. Design a data structure to manage sets of DTMC and probability distributions and
implement associated management functions.

2.2 Reading and Writing DTMC and probability distributions
We shall record DTMC into text files. The format of these text files is exemplified in Figure 2
for the DTMC pictured in Figure 1.

Sequences of white space, tabulation and end of lines are separators. Identifiers for DTMC,
probability distributions and states are sequences of letters, digits and underscores starting
with a letter or an underscore. MarkovChain, ProbabilityDistribution, of and end must be
reserved words (they cannot be used as identifiers).

Task 4. Prepare a benchmark of DTMC and probability distributions written according to
the specified format. This benchmark will be used to test your program.
 

Task 5. Implement functions to print a list of DTMC and a list of probability distributions
into a file.
To read DTMC and probability distributions from text files, you shall first read files and
extract a list of tokens from these files.
The information regarding a token consists (at least) of the following data.
— A code telling which type of token it is (identifier, number.,. .. );
— The string of the token;
— The line and the column number it has been read.
Task 6. Design a data structure to encode tokens and implement the associated management
functions.
Task 7. Implement functions to read a text file and returns the list of tokens this file consists
in.
Task 8. Implement functions to parse DTMC and probability distributions from a list of
tokens.

2.3 Checking DTMC and probability distributions

A DTMC or a probability distribution can be syntactically correct, but still incorrect or awkward

from a mathematical standpoint. For instance, the sum of the probabilities labeling transitions

leaving a state may be greater than 1 or a state may be without in or out transitions.
Task 9. Implement functions to check DTMC and probability distributions.

2.4 Calculations

We can now implement calculations.

Task 10. Implement a function that calculates the product of a probability distribution by the
sparse matrix.

Task 11. Implement functions that, given a DTMC and an initial probability distribution,
calculate the probability distribution and the sojourn times in each state after a
mission of n steps.

2.5 Time Series

DTMC can be used to generate times series and reciprocally, they can be built from time series.

Task 12. Implement a function that, given a DTMC and an initial state, generates a time series
(a sequence of states). The next state must be chosen at random from the current
one, according to the probabilities of out transitions.

Task 13. Implement a function that, given a time series, creates a DIMC using the frequency
of transitions from one state to the next one observed in the time series.

You can now generate a time series from a DT MC, create a DTMC from this time series and
compare the two DTMC.

Task 14. Perform an experimental study to determine what should be the length of the time
series to make the original and the created DTMC close one another.

Hint: Use sojourn times to compare the two DTMC.