Probabilistic Algorithms MAT3512

Content of the course:

Part I. Discrete Time Parameter.

I.1. Finite-State Markov Chains.

Transition matrix. Trajectories (computations); the number
of steps of a trajectory,
Probability of realization of a trajectory.
The matrix of n-step transitions between two states.
Classification of states (absorbing, temporary, …).
Types of Markov chains: absorbing, regular, ergodic.
The asymptotic transition matrix of a Markov chain.
The average number of steps of trajectories of an absorbing
Markov chain.
Regular and ergodic Markov chains. The average number of
steps of the first return to a state, the average number
of steps of the first transition from a state to another
one.

I.2. Iterative Probabilistic Algorithms. Finite Interpretations.

The computation semantics of iterative probabilistic
algorithms.
Mutual interpretations of finite-state Markov chains
and iterative probabilistic algorithms interpreted in a finite
structure.
Algebraic semantics for iterative probabilistic algorithms.
The asymptotic transition matrix of an iterative probabilistic
algorithm.
The average number of steps of trajectories of an iterative
probabilistic algorithm.

I.3. Remarks on the quality of pseudo random generators.

Part II. Continuous Time Parameter.

II.1. Finite-State Markov Processes.

The Chapman-Kolmogorov semantics of finite-state Markov
processes. Transition matrix for a moment t.
Absorbing, regular and ergodic Markov processes.
The average number of steps of computations related to the
first transition from a state to another one.
The average time of computations related to the first return
to a state.
The average time of computations related to the first
transition from a state to another one.

II.2. Iterative Probabilistic Algorithms. Finite Interpretations.

The semantics of iterative probabilistic algorithms with the
continuous time parameter based on absorbing Markov
processes.

II.3 Examples of Real random processes modeled by means of
probabilistic algorithms with the continuous time parametr.