Sampling analysis and probability theory

Lecture 1.

Basic combinatorial quantities and basic combinatorial formulas. Number of combinations (with or without repetitions), number of arrangements, permutations. Newton binomial and binomial coefficients. Polynomial formula and polynomial coefficients. Inclusion-exclusion principle.
Literature: [1], [2], [3], [4].

Lecture 2.

Combinatorial identities and Moebius formula. Basic combinatorial identities. Alternating identities. Application of inclusion-exclusion principle to combinatorial identities. Moebius function and Moebius inversion formula. Counting the number of cyclic sequences.
Literature: [1], [2], [3], [5], [6], [7].

Lecture 3.

Estimates and asymptotic for combinatorial quantities. Simple estimates for the factorials, binomial coefficients etc. Entropy. Chernoff inequality. Stirling formula (without proof). Asymptotic for the binomial coefficients etc.
Literature: [3], [8].

Lecture 4.

Elements of asymptotic analysis. Abel transformation. Riemann zeta-function. Application of Abel transformation and Moebius inversion formula to analysis of zeta-function properties. Replacing the sums by integrals in asymptotic estimates. Examples: harmonic numbers, Euler's constant, summation over the prime numbers, etc.
Literature: [6], [8], [9].

Lecture 5.

Integer partitions. The problem of the partition of numbers into summands. Ordered and unordered partitions. Recurrence relations for the partition functions. A few words on the diagram technique. Hardy-Ramanujan theorems (without proof).
Literature: [1], [3], [5], [10].

Lectures 6 and 7.

Recurrence relations and generating functions. Linear recurrence relations with constant coefficients. Power series and generating functions. Application of power series and generating functions to combinatorial identities. Application of power series and generating functions for solving recurrence relations. Catalan, Stirling, Bernoulli numbers etc. Their applications.
LIterature: [1], [2], [3], [7], [11].

Lecture 8.

Basics of graph theory and enumeration problems on graphs. Basic concepts of graph theory. Enumeration of trees on n vertices (Cayley formula): approach with generating functions and approach using the bijection between the set of trees and the set of arrangements with repetitions (Prüfer codes). Isomorphisms and automorphisms of graphs. Summary of the results on the enumeration of graphs.
Literature: [3], [7], [12], [13], [14], [15].

Lecture 9 and 10.

Discrete and geometric probability. Classical definition of probability. Geometric probability. Bertrand paradox. Conditional probability. Independence of events. Law of total probability and Bayes formula. Bernoulli scheme. Polynomial scheme. The scheme of the series. Random walks. The notion of a random graph. Percolation. Monte Carlo method.
Literature: [15], [16], [17], [18], [19].

Lecture 11.

Random variables and cumulative distribution functions. Discrete and absolutely continuous cumulative distribution functions (CDF). The main types of CDF: binomial, geometric, Poisson, hypergeometric, uniform, normal, exponential, gamma distribution, chi-square, Student's, Fisher, etc. Numeric characteristics of the CDF: expectation, variance, moments, factorial moments. The joint CDF. Covariance and correlation. Independent and uncorrelated random variables. The concept of a variation sequence. Distribution, mathematical expectation, variance and covariance of order statistics.
Literature: [16], [17], [18], [20].

Lecture 12 and 13.

Limit theorems. Markov and Chebyshev inequalities. The law of large numbers for Bernoulli scheme. The law of large numbers in the form of Chebyshev. The law of large numbers in the form of Khinchin. Kolmogorov's inequality. Strong law of large numbers. Moivre-Laplace limit theorems for the Bernoulli scheme (local and integral). Poisson limit theorem for a scheme of series. Generating and characteristic functions. The central limit theorem (different formulations, the proof only for the case of independent and identically distributed random variables).
Literature: [16], [17], [18].

Lectures 14 and 15.

Fundamentals of Statistics. The concept of the sample and the sample space. Point estimation of parameters. Unbiasedness, consistency, etc. Methods of moments and maximum likelihood. Confidence estimation. Methods of construction of confidence intervals.
Literature: [20], [21], [22], [23].


[1] N. Y. Vilenkin, Combinatorics, Moscow, Nauka, 1969.
[2] N.B. Alfutova, A.V. Ustinov, Algebra and number theory (book of tasks), Moscow, MCCME, 2002.
[3] A.M. Raigorodskii, A.V. Savvateev, I.D. Shkredov, Combinatorics (handbook for department of bioengineering and bioinformatics, MSU), Moscow, MAX-PRESS, 2005.
[4] J. Riordan, Introduction to combinatorial analysis, Moscow, IL, 1963.
[5] M. Hall, Combinatorics, Moscow, Mir, 1970.
[6] K. Chandrasekharan, Arithmetic functions, Moscow, Fizmatlit, 1975.
[7] R. Stenly, Enumerative combinatorics. Trees, generating functions and symmetric functions. Moscow, Mir, 2005.
[8] G.M. Fichtengoltz, Lectures on differential and integral calculus, Moscow-Izhevsk, Fizmatlit, 2003.
[9] A.A. Karatsuba, Introduction to analytical number theory, Moscow, Editorial URSS, 2004.
[10] G. Andrews, The theory of partitions, Moscow, Nauka, 1982.
[11] A.O. Gelfond, Calculus of finite differences, Moscow, Nauka, 1967.
[12] F. Harary, Graph theory, Moscow, Mir, 1973.
[13] O. Ore, Graphs and their applications, Moscow, Nauka, 1965.
[14] F. Harary, E. Palmer, Graph enumeration, Moscow, Mir, 1977.
[15] B. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.
[16] V. Feller, Introduction to probability theory and applications, Moscow, Mir, 1967.
[17] B. V. Gnedenko, Lectures on probability theory, Moscow, Fizmatlit, 1961.
[18] A.N. Shiryaev, Probability, Moscow, Nauka, 1989.
[19] N. Alon, J. Spencer, Probabilistic method, Moscow, Binom. Laboratoriya Znaniy, 2007.
[20] M.B. Lagutin, Pictorial mathematical statistics, М. Б. Лагутин, Наглядная математическая статистика, Moscow, Binom. Laboratoriya Znaniy, 2007.
[21] E. Leman, Э. Леман, Theory of point estimation, Moscow, Nauka, 1991.
[22] A.A. Borovkov, Mathematical statistics. Estimation of parameters. Verification of hypothesis, Moscow, Nauka, 1984.
[23] B.A. Sevastianov, Lectures on probability and mathematical statistics, Moscow, Nauka, 1982.