 # Advanced probability and Monte Carlo methods

## Presentation

• Conditional expectation, filtration, martingale, submartingale and supermartingale, Doob’s theorem, optional stopping theorem, convergence theorems, law of large numbers and central limit theorem for martingales.
• Background on deterministic gradient descent, Introduction to Robbins-Monro algorithms and links with classical results (Law of Large Numbers), Robbins-Siegmund Lemma, Robbins-Monro Convergence Theorems, Applications (Two-Armed Bandit, quantile, quantization, Linear Regression in high dimension).
• Generation of random numbers, simulation by inversion of the distribution function, by the reject method and by some specific methods, Monte-Carlo Methods (convergence, rate of convergence, variance reduction by using different methods).

## Objectives

At the end of this module, the student will have understood and be able to explain (main concepts):

• The notion of conditional expectation, the main properties of martingales and their classical use in modelling,
• Stochastic algorithms of Robbins-Monro type.
• The fundamental principles of simulating random variables and Monte-Carlo methods.

The student will be able to:

• To compute a conditional expectation, to show that a random process is a martingale, to use the various theorems (Doob, optional stopping and convergences), in particular for the maximum  likelihood estimation.
• Build and study the convergence of stochastic optimization algorithms, apply these methods to different problems (quantile, quantization,…)
• Simulate a random variable by different methods, use probabilistic,  choose appropriate techniques for variance reduction and error estimation.

## Needed prerequisite

Probability and statistics [I2MIMT31]

## Form of assessment

The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...