


Politecnico di Torino  
Academic Year 2016/17  
01RMING Stochastic processes/Dynamics over networks 

Master of sciencelevel of the Bologna process in Mathematical Engineering  Torino 





Subject fundamentals
The course is taught in Italian.
The purpose of this course is to provide basic and advanced concepts of graph theory and stochastic processes, with a focus on mathematical models describing deterministic and random dynamics over networks. The main stochastic processes in discrete and continuous time, with particular attention to their engineering applications, will be described during the lectures, together with the basic elements of combinatorial and algebraic graph theory, and the theory of stochastic matrices. Various applications will be discussed: algorithms for estimation problems over a network, mobile agents dynamical models, opinion and epidemics dynamics. 
Expected learning outcomes
The knowledge obtained through this course consists on:
Knowledge of basic theoretical elements of stochastic processes and their main characteristics and properties. Ability to recognize the stochastic processes suitable for modeling dynamical systems with nondeterministic evolutions. Ability to analyze dynamic stochastic models, and to describe related random quantities such as distributions of waiting times for achievement of absorbing states, or conditions for stationarity of the model. Knowledge of basic elements of graph theory with an emphasis on connectivity issues and periodicity. Knowledge of stochastic and substochastic matrix theory and their spectral theory. Ability to construct mathematical models describing dynamics over networks of possible use in robotics, inferential statistics, socioeconomic models. Ability to analyze the performance of a distributed algorithm over a network, its complexity and speed of convergence with special emphasis on the scalability properties with respect to the number of nodes in the graph. 
Prerequisites / Assumed knowledge
A basic knowledge of calculus, linear algebra, and probability theory are the prerequisites for this course.

Contents
General introduction to stochastic processes; filtration; stopping times.
Discrete time martingales and their properties. Decomposition of supermartingales and submartingales, Doobs theorem, convergence. Poisson processes: equivalent definitions, generalizations (nonhomogeneous, compound, mixed). Renewal processes: equilibrium distributions, limit theorems and stationary processes, expected number of renewals. Markov chains: transition matrices, classification of states, stationarity and ergodicity, reversibility. Examples (Branching processes). Continuoustime Markov processes, birth and death processes, Kolmogorov equations, stationary distributions. Brownian motions: definition, properties, applications. Directed graphs, paths, circuits, cycles. Connectivity and strong connectivity. Period of a node, aperiodic graphs. Connected components and condensation graph. Laplacian of a graph, Dirichlet form, harmonic functions. Stochastic matrices and their use in consensus dynamics. Convergence for the powers of a stochastic matrix. Spectral properties, Cheeger inequality. Graphs as electrical circuits and connection with timereversible stochastic matrices. Applications: algorithms for distributed estimation, opinion dynamical models. Models with interacting agents. Gossip dynamics. Epidemics diffusion models. Opinion dynamics models. Mean field approximation. Dynamics over trees. Threshold models. 
Delivery modes
Several exercises covering all the topics will be discussed and solved during classes. Technical discussions during class lectures will also help to assess the acquired level of knowledge and ability at the different stages of the course.

Texts, readings, handouts and other learning resources
The course will be fully covered by Lecture Notes and other material (including examples and exercises with solutions) written by the teachers and made available online to the students enrolled in the course.
Suggested books: Sheldon N. Ross "Stochastic processes" 2nd ed John Wiley Jacod J., Protter P, "Probability essentials", Springer 2000 D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (available online). 
Assessment and grading criteria
The exam consists of an oral examination on both parts of the course. During the course homeworks will be assigned concerning some parts of the program, that will consequently be removed from the final oral exam.

