6 CFU
II YEAR - I TERM
Wed. 12.00-13.30, Room A3, via Ariosto, Dipartimento di Ingegneria Informatica, Automatica e Gestionale
Thu 15.45-19.00, Room A4, via Ariosto, Dipartimento di Ingegneria Informatica, Automatica e Gestionale
The purpose of the course is to present a comprehensive treatment of advanced probabilistic techniques for applications to stochastic modelling and data analysis. Preliminary background material will be quickly reviewed and some basic tools in the thoery of stochastic processes (i.e., conditional expectation, filtrations, stopping times) will be introduced. This will allow to cover discrete and continuous time model, with particular reference to the theory of martingales, random walks and Markov chains.
EXAMINATION DATES:
13-9-2017 ORE 9,30 room V (4th floor), Dip. Statistica
TEXTBOOKS:
Probability and Random Processes
G. Grimmett, D.Stirzaker
Oxford Univ. Press, 2001 (3rd ed.)
Probability and Computing : Randomized Algorithms and Probabilistic Analysis
M. Mitzenmacher, E.Upfal
Cambridge Univ. Press, 2005
Notes on Elementary Martingale Theory
J.B. Walsh
British Columbia Univ. CA
https://www.math.ubc.ca/~walsh/marts.pdf
Stochastic Processes: Theory and Applications
R.G.Gallager
Cambridge University Press 2013
http://www.rle.mit.edu/rgallager/documents/6.262-5vaw.pdf
Randomness and Computation
A. Sinclair
Lecture notes
UC Berkeley 2010
28-9-2016: Probability space, random variables (discrete), probability distribution with properties (GS 1.1-1.2-1.3; 2.1-2.3; MU 1.2-2.1-2.2-2.4)
29-9-2016: Continuous random variables, density function, expected value and moments, variance, covariance. Independence of r.v.'s. Markov and Chebyshev inequalities. Moment generating function. Tail probabilities and Chernoff bounds. (GS 2.3-2.5-3.3-3.6; 4.1-4.2-4.3-4.7; 5.1; 7-3; MU 2.1; 3.1-3.2-3.3; 8.1-8.2-8.3; 4.1-4.2-4.3)
5-10-2016: Probability generating function with properties and examples. Sum of a random number of r.v.'s. Wald formula. Convolution formula for p.g.f. (GS 5.1)
6-10-2016: Random walks. Properties of time and space homogeneity, Markov property, Reflection principle. Ballot problem, distribution of the maximum of a r.w. Gambler's ruin problem. (GS 3.9-3.10)
12-10-2016: Random walks: probability distribution of first and last visit to the origin (the latter in the symmetric case only). Reversed r.w. . (GS 3.10)
13-10-2016: Random walks: arcsine law, distribution of subsequent returns to the origin, persistent and transient r.w.'s; Spitzer's identity. Conditional expectations: review of basic definitions. (GS 5.1-5.3; 3.7; 4.6; MU 2.3)
19-10-2016: Conditional expectation of a r.v. given a sigma-field (for finite-partitions of the space omega and for general sub-sigma fields). Properties. (W 1.1-1.2)
20-10-2016: Properties of conditional expectations of a r.v. given a sigma-field. Conditional monotone and dominated convergence theorems, Fatou's lemma. Iterated conditional expectations, Jensen's inequality. Filtrations. Martingale, sub-martingale and super-martingale. Examples: random walks, Doob martingale. (W 1.2-1.3-1.4-1.5; 2; GS 12.1; MU 12.1)
26-10-2016: Properties of martingales and sub-martingales. Examples: Polya mart., branching process, Previsible process. Doob-Meyer decomposition. Compensator. (GS 12.1; W 2.3)
27-10-2016: Properties of the compensator. Applications: De Moivre's martingale and ruin problem; bet strategies. Tail bonds for martingale differences. Azuma-Hoeffding inequality. Markov generalized inequality. Applications: large deviations of random walks. Upcrossing inequality for numerical sequences. Upcrossing inequality for submartingales. (GS 12.2-12.3; MU 12.4; W 2.9)
2-11-2016: Convergence results on submartingales. Filtration in continuous time. Stopping times: properties and examples. Sigma-field stopped at a random time. (GS 12.3; W 2.4-2.10)
3-11-2016: Theorems on sigma-fields stopped at a stopping time. Optional stopping theorems for martingales, submartingales and supermartingales (for finite stopping times and without finiteness restrctions). (GS 12.4-12.5; MU 12.2; W 2.6)
9-11-2016: Brownian motion as limiit of a simple symmetric random walk. Definition, transition function and distributional properties. Kolmogorov theorem. Almost sure continuity and non-differentiability of the trajectories. (GS 13.1-13.3)
16-11-2016: Distribution of the maximum and first-passage time of a Brownian motion. Inverse Gaussian. Arcsine law of the last visit of the origin (analogies with random walks). Brownian motion with absorbing barrier. (GS 13.4-13.5-13.6)
17-11-2016: Brownian motion with reflecting barrier. Analytical approach to the Brownian motion theory: heat equation and backward equation. Additional conditions in the case of absorbing and reflecting barriers. Brownian motion with drift. Distribution of the minimum between two first-exit times from a given interval (also by means of martingale's arguments and the optional stopping theorem) (GS 13.5)
23-11-2016: Expected first-exit time from a given interval (also by means of the optional stopping theorem). Other diffusion processes and related pde: Brownian bridge with properties; Ornstein-Uhlenbeck processe (GS 13.3-13.6)
24-11-2016: Fokker-Plank equation and transition density of the Ornstein-Uhlenbeck processe. Poisson process: assumptions of the model, properties, equation and distribution; interarrival times and theri distribution. Renewal processes: strong law of large numbers and central limit theorem for the counting process; renewal function; renewal equation. (GS 10.1-10.2)
30-11-2016: Solution of the renewal equation through Laplace transform; Elementary renewal theorem. Renewal-reward processes: residual life time. (GS 10.2-10.3; G 3.1-3.2-3.3)
1-12-2016: Renewal-reward processes: age and duration processes. Convergence of the general renewal-reward time-average. Continuous-time random walks: definitions and Montroll-Weiss equation in interal and integro-differential forms. Compound Poisson process. Hints of semi-Markov processes with interarrival power law decay. (GS 10.3; G 3.4)
15-12-2016: Applications of Doob martingale and Azuma inequality: pattern matching and chromatic number. The probabilistic method: the basic counting argument. (MU 12.5; 6.1)
21-12-2016: The probabilistic method: the expectation argument with application to "finding a large cut". Dependency graphs: the Lovasz local lemma. (MU 6.1-6.2-6.7; S. 22.1)