Lectures from Yandex for those who want to spend the holidays with benefit. Discrete analysis and probability theory

For those who do not have one course for the holidays and who want more, we continue our series of courses from the Yandex Data Analysis School. Today was the turn of the course "Discrete Analysis and Probability Theory" - even more fundamental than the previous one. But without it, you can not imagine even a large part of modern data processing.

The course covers the basic concepts and methods of combinatorial, discrete and asymptotic analysis, probability theory, statistics, and their application is demonstrated using the example of solving classical problems.


')
Reads the course Andrey Raygorodsky. Doctor of Physical and Mathematical Sciences. Professor, Department of Mathematical Statistics and Random Processes, Faculty of Mechanics and Mathematics, Moscow State University M. V. Lomonosov. Head of the Department of Discrete Mathematics at the Moscow Institute of Physics and Technology. Professor and supervisor of the bachelor degree in the Department of Data Analysis of the Faculty of Innovations and High Technologies at MIPT. Head of the Department of Theoretical and Applied Research at Yandex. (You can find out more in the article about him on Wikipedia ).

Lecture 1. Basics of enumerated combinatorics

Combination numbers (with repetitions and without repetitions), placement numbers (with repetitions and without repetitions), permutations. Newton's binomial and binomial coefficients. Polynomial formula and polynomial coefficients. Formula for inclusions and exclusions.

Lecture 2. Generalized Möbius function and asymptotics

Simple combinatorial identities. Alternating identities. Using the formula of inclusions and exceptions to prove identities. Mobius function and Mobius inversion formula. Count the number of cyclic sequences. Elementary estimates of factorials, binomial coefficients, etc. The concept of entropy. Chernov's inequality. Stirling formula (b / d). Asymptotics for binomial coefficients, etc.

Lecture 3. Trees and unicyclic graphs

Basic concepts of graph theory. Enumeration of trees at n vertices (Cayley's formula): an approach with generating functions; approach using bections between multiple trees and multiple arrangements with repetitions (Prüfer codes). Isomorphisms and automorphisms of graphs. Summary of results on the enumeration of graphs.

Lecture 4. Splitting numbers into addends

Problems of splitting numbers into addends. Ordered and unordered partitions. Recurrence relations for partition functions. Hardy-Ramanujana (b / d).

Lecture 5. Generating functions and linear recurrence relations

Linear recurrence relations with constant coefficients. Power series and generating functions. Application of power series and generating functions to prove combinatorial identities. Application of power series and generating functions for solving recurrence relations. Numbers Catalan, Stirling, Bernoulli and others. Their applications.

Lecture 6. Chromatic numbers of graphs and Kneser graph

Chromatic numbers of graphs. Kneser hypothesis. Lovas theorem.

Lecture 7. Classical definition of probability, Bernoulli scheme and their application to Ramsey numbers

The classic definition of probability. Geometric probabilities. Bertrand's Paradox. Conditional probabilities Independence of events. Formulas of full probability and Bayes. Bernoulli scheme. Polynomial scheme. Scheme series. Random walks. The concept of a random graph. Percolation. Monte Carlo method.

Lectures 8-9. Local lemma of Lovas. Probability theory ( part 1 , part 2 )

Ramsey numbers. Coloring hypergraphs. Coverage graphs linear forests.

Lecture 10. Distributions of random variables.

Discrete and absolutely continuous distributions. The main types of distributions: binomial, geometric, Poisson, hypergeometric, uniform, normal, exponential, gamma distribution, chi-square, Student, Fisher, etc. Numerical characteristics of distributions: mathematical expectation, variance, moments, factorial moments. Joint distribution. Covariance and correlation. Independence and uncorrelated random variables. Concept of variation range. Distributions, expectations, variances and covariances of ordinal statistics.

Lectures 11-12. Limit theorems ( part 1 , part 2 )

Markov and Chebyshev inequalities. The law of large numbers for the Bernoulli scheme. The law of large numbers in the form of Chebyshev. The law of large numbers in the form of Khinchin. Kolmogorov inequality. The strong law of large numbers. Limit theorems of Moavre-Laplace for the Bernoulli scheme (local and integral). Poisson limit theorem for a scheme of series. Generating and characteristic functions. The central limit theorem (various formulations; proof only for the case of independent identically distributed random variables).

Lecture 13. The dimension of Vapnik-Chervonenkis

The concept of sampling and sample space. Point estimation parameters. Informability, consistency, etc. Methods of moments and maximum likelihood. Trust evaluation. Methods for constructing confidence intervals.

Update: all the lectures of the course “Discrete Analysis and Probability Theory” in the form of an open folder on Yandex.Disk .