Algortihmic Modelling of Random Phenomenons (elective) I24000j

Learning outcomes
Symbol Specify min. 4, max. 8 learning outcomes in the following order: knowledge – skills – competence. Each learning outcome must be verifiable Reference to the programme learning outcomes of education
LO1 provides an understanding of Markov chain/process and its application to modeling of random phenomena K_W01
K_U11
LO2 provides an oportunity to cooperation in programming experiments, related to simulation o Markov chains/processes by means o probabilistic algorithms K_U11
K_U18
LO3 provides an understanding of basic methods of probabilistic algorithms analysis K_W01
K_W08
LO4 provides an understanding of basic methods of Markov chain/processes analysis (determining parameters describing the behavior of Markov chain/process) K_W01
K_U07
LO5 provides ability to develop the model of real random phenomenon in the form of Markov chain/process or by using a probabilistic algorithm K_U07
K_U17
No. of learning outcome Methods of assessing the learning outcome Type of teaching activities (if more than one) during which the outcome is assessed
LO1 assesssment is via continuous performance monitoring during exersises and when discussing results of the project
LO2 assesssment is via continuous performance monitoring during exersises
LO3 assesssment is via continuous performance monitoring during exersises and when discussing results of the project
LO4 assesssment is via continuous performance monitoring during exersises and when discussing results of the project
LO5 assesssment is via continuous performance monitoring during exersises and when discussing results of the project
Student workload (in hours) 1 - attendance at lectures 15x2 30
2 - attendance at subject exercises 15x2 30
3 - make use of theoretical facts (presented at lectures) to realize programistic experiments of subject exercises 15x1 15
4 - preparing for the examination 10
5 - preparing for programistic experiments 15x2 30
6 - discussions concerning lectures and exercises (teacher consultations) 5
TOTAL: 120
Quantitative indicators Student's workload - activities that require direct teacher participation:
(6)+(1)+(2) 65 ECTS
2,5
Student's workload connected with practical classes
(3)+(2)+(5) 75 3.0

Assessment (Examination)

Assessment is based on final, individual projects, realized by students during 1.5 h
(an example of such a project is included).

The project consist in
a) the construction of a (small) program for simulation of a given three-state absorbing
Markov Chain/Process.
By means of the simulation the value of average number of steps/average time
of computations until absorption is determined,
b) determining, using Markov Chain/Process theory, the theoretical value of average
number of steps of computations/average time until absorption,
c) comparing the values determined in a) and b) and estimate the quality of the pseudo-
random generator used in simulation.

The project requires the following elements of knowledge and skills related to the theory
of Markov Chains and Processes (including prerequisites):

– students use basic facts of Linear Algebra, Mathematical Analysis and Probability
Theory,
– students determine transition matrices for small probabilistic programs
interpreted as Markov Chains and/or Processes,
– students determine (theoretical) values of parameters of obtained Markov models
using facts of Markov model theory; students could use professional tools like MatLab,
– students organize a programistic experiments for determining values of parameters
by simulation,
– students formulate opinions on the quality of pseudo-random generators used
In simulation,
– students prepare reports concerning the project.

-----------------------------------------------------------------------------------------------
(An example of) Project.
-----------------------------------------------------------------------------------------------
Task 1.

Given a probabilistic algorithm K:

while x <> 3
if x = 1 then x: = random1
else x: = random2;

interpreted with discrete time parameter
in the set {1, 2, 3} with the following the random assignment

random1: 1: 0.0, 2: 0.4, 3: 0.6,
random2: 1: 0.3, 2: 0.0, 3: 0.7.

Using the known methods, please determine
(A) transition matrices for the algorithm K and its subalgorithms;
(B) the vector of the average number of steps.

Task 2.

Consider the Markov process P (with continuous time parameter) on the set of states
{1, 2, 3}, and the intensity matrix
L = ....
Please designate
(C) the vector of average times to absorption.

Task 3.

Organizing a programming experiment, through the implementation of generators random1, random2, and the process P with continuous time, taking into account
matrix L, please designate (of the order of 1 000 repetitions of "simulation" of the process P):
(B ') the vector of the average number of steps to absorption,
(C ') the vector of average times to absorption.
also, please designate
(D) the percentage difference between the values of the parameters in
B and B',
C and C'.

Suggestion 1:
In Task 1 determine for a given algorithm K, the corresponding Markov chain M (with three states).

References:

a) basic:

Feller W.: Introduction to Probabilisty Theory, PWN,
Warszawa 1977, (in Polish),

Kubik L., Krupowicz A.: Introduction to Probabilisty Theory and its
Applications, PWN, Warszawa 1982,(in Polish),

Josifescu M.: Fnite Markov Processe and Their
Applications, John Wiley & Sons, New York,
London 1998,

Mirkowska G., Salwicki A.: Algorithmic logic for Programers,
WNT, Warszawa 1985, (in Polish),

b) additional:

Dańko W.: Algorithmic Models of Random Phenomena,
Wydawnictwa WSE w Białymstoku, Białystok 2006,
(in Polish)