Enseignement

Revision of basic set theory and combinatorics.

Elementary probability: random experiment; probability space; conditional probability; independence.

Random variables: basic notions; density and mass functions; examples including Bernoulli, binomial, geometric, Poisson, uniform, normal; mean, variance,  correlation and covariance; moment-generating function; joint distributions, conditional and marginal distributions; transformations.

Many random variables: notions of convergence; laws of large numbers; central limit theorem; delta method; applications.

Statistical inference: different types of estimator and their properties and comparison; confidence intervals; hypothesis testing; likelihood inference and statistical modelling; Bayesian inference and prediction; examples.

The class will cover statistical models and statistical learning problems involving discrete structures. It starts with an overview of basic random graphs and discrete probability results. It then covers topics such as reconstruction on trees, stochastic block models, and spectral graph theory.

Content

• thresholds
• random graphs basics
• random trees
• broadcasting on trees
• stochastic block models and community detection
• spectral graph theory

The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees, stochastic block models and perceptron models. Requirement: basics of probability and statistics.

The class overviews some of the main concepts and developments concerning reasoning in AI, such as Transformers, LLMs, Step-by-Step Reasoning, Tool Use, Planning, Logical Reasoning, Self-Improvement, Generalization on the Unseen or Theorem Proving.