Теория вероятностей 2024/25 (основной поток)

Преподаватели и учебные ассистенты

Группа	БПМИ235	БПМИ236	БПМИ237	БПМИ238	БПМИ239	БПМИ2310	БПМИ2311	БПМИ2312
Лектор	Борис Демешев
Семинарист	Борис Демешев	Илья Левин	Никита Морозов	Борис Демешев	Максим Каледин	Голуба Юрьева	Вероника Владыкина	Голуба Юрьева
Ассистент	Ира Скворцова	Амелия Алаева	Алина Бадахова	Аделя Гараева	Мария Брель	Анна Зыкова-Мызина	Яна Вежновец	Кирилл Лавриненко
Ассистент курса	Никита Волянский

Цели и задачи курса

侍には目標がなく道しかない [Samurai niwa mokuhyō ga naku michi shikanai]

У самурая нет цели и ничего кроме пути.

Вероятный план:

1. Дискретное вероятностное пространство. Вероятность, математическое ожидание, теоретическая медиана. Перестановочные тесты, p-значение для перестановочного теста. Математическое ожидание = центр масс.

NB: здесь сходу рисуем дерево NB: здесь нет задач на условную вероятность

!предупреждение об обозначениях случайных величин. Российская традиция — греческие буквы, американская традиция — заглавные английские буквы. Наш курс: любые буквы. Причина: теория вероятностей применяется в разных областях, где свои традиции.

NB: Способы вычисления вероятностей и ожиданий:

   * полный перебор руками 
   * примерные вычисления руками
   * полный перебор на компьютере
   * симуляции на компьютере
   * ...

2. Методы решения задач:

• разложение величины в сумму
• метод первого шага

   !идея: позиция в игре имеет цену

• just for fun: метод рычага в геометрии через ожидание

NB: рассказать здесь про комплексную случайную величину NB: по сути здесь мы уже решаем задачи на марковские цепи не говоря страшных определений LOTUS.

3. Условная вероятность и условное ожидание. !идея: зануляем вероятности невозможных событий, а остальные — масштабируем. формула полной вероятности !идея: дерево "помнит" формулу полной вероятности формула Байеса

Независимые события. Независимые случайные величины.

4. Методы решения задач:

• производящие функции многих переменных

   функция как способ записать множество
   HTT vs TTH
   ABRACADABRA 
   !разложение по биномиальной формуле

?: можно здесь успеть функцию производящую моменты

5. Биномиальное распределение. Геометрическое и гипергеометрическое распределения. Отрицательное биномиальное распределение.

6. Равномерное распределение на множестве в R^n Функция распределения. Функция плотности и вероятностная дифференциальная форма.

   !пояснение про неудачную традиционную терминологию "непрерывная случайная величина"
   величина с функцией плотности, величина с непрерывной функцией распределения. 

Квантили, квантильная функция.

7. Характеристики случайных величин и неравенства. Дисперсия. Энтропия. Неравенство Маркова. Неравенство Чебышёва. Неравенство Йенсена.

Здесь конец модуля 1 и КР-1!

8. Пуассоновский поток. Аксиомы пуассоновского потока. Вывод экспоненциального распределения и пуассоновского распределения из аксиом. Вывод экспоненциального распределения из предпосылки об отсутсвии памяти.

9. Нормальное распределение. Нормальное распределение: предпосылки Хершела-Максвелла. Нормальное распределение: аргументация Гаусса за среднее арифметическое. Нормальное распределение: предпосылки Лэндона (до уравнения в частных производных).

10. Классические непрерывные распределения.

Гамма-распределение, бета-распределение. Вывод нормального и экспоненциального распредений как минимизации энтропии.

11. Парные характеристики случайных величин. Наилучшая линейная аппроксимация. Ковариация. Корреляция. Кросс-энтропия.

Доказательство E(XY) = E(X) E(Y) для дискретных. Ковариационная матрица и ожидание для случайных векторов.

12. Совместная и условная функция плостности. Преобразования случайных величин.

13. Функция производящая моменты и характеристическая функция. Распределение суммы случайного количества случайных величин. Случайный выбор слагаемых.

14. Финансовые приложения

Оценивание опционов на биномиальном дереве. Максимизация долгосрочной прибыли, связь с энтропией. Возможно, индексы Гиттинса.

Здесь конец модуля 2 и КР-2

15. Сигма-алгебры.

Список известных величин как способ описания информации. Идея условного ожидания как оптимального прогноза. Сигма-алгебра как способ описания информации. Измеримость случайной величины относительно сигма-алгебры. Сигма-алгебра как ОДЗ для вероятности. Борелевская сигма-алгебра. Независимые случайные величины второе определение.

16. Условное математическое ожидание. Условная дисперсия. Сумма случайного количества случайных величин.

17. Сходимости случайных величин.

Сходимость по вероятности. Закон больших чисел. Сходимость почти наверное. Усилинный закон больших чисел. Сходимость по распределению.

18. Связь сходимостей. Лемма Слуцкого.

19. Центральная предельная теорема. Доказательство через подмену слагаемых. Доказательство через характеристические функции.

Здесь контрольная.

20. Винеровский процесс Условные ожидания, инверсия.

21. Байесовский подход к оцениванию параметров

Балансовое уравнение. Идея MCMC.

22. Доказательства свойств меры

23. Алгоритм построения математического ожидания в общем случае. Лемма Фату. Теорема о мажорируемой сходимости. Теорема о монотонной сходимости.

24. Резерв.

Жемчужинки, которые, вероятно, не успеем:

А. Методы решения задач: подсчёт случаев с помощью леммы Бернсайда и теоремы Пойа о перечислении (Burnside lemma, PET = Polya Enumeration Theorem)

B. вероятностные доказательства детерминистических теорем

Оценивание

Оценка за семестр-1 = 0.2 Домашние задания семестра-1 + 0.4 Контрольная-Альфа + 0.4 Экзамен-Бета.

Финальная оценка за курс = 0.5 Оценка за семестр-1 + 0.1 Домашние задания семестра-2 + 0.2 Контрольная-Гамма + 0.2 Экзамен-Дельта.

Каждая оценка (суммарные итоги за домашние задания, контрольные, экзамены) — целое число от 0 до 100. Для перевода в 10-балльную шкалу промежуточной оценки за семестр-1 и финальной оценки используется деление на 10 с арифметическим округлением.

Домашние задания для самураев

Домашние задания одним файлом и отдельными файлами. Домашние задания имеют равный вес. В конце каждой лекции (за исключением ближайших к экзамену лекций) выдается домашнее задание сроком на две недели. Дедлайн жёсткий, однако студент имеет право просрочить три домашних задания на неделю каждое без штрафа.

Формат сдачи ДЗ: один pdf-файл (решение текстовых задач) и один ipynb-файл (решение компьютерных задач). В pdf-файл можно поместить аккуратно написанное отсканированное решение, а можно скомпилировать pdf из теха или маркдауна. Ещё можно вместо pdf-файла написать всё в ipynb. Бонусов за сдачу домашки в техе нет. Пример шаблона.

Обратите внимание: время каждого дедлайна — 21:00.

Контрольные работы и экзамен

Вес каждой задачи будет написан в тексте работы. Задачи с ненаписанным по случайности весом имеют равный вес. Для пропущенных по уважительной причине контрольных будет выделен один день для переписывания. При пропуске дня переписывания, в том числе по уважительным причинам, ещё одного шанса не предоставляется.

Контрольная работа 1 состоится 2024-11-11 в 16:20, аудитории: R401, R305, R206.

Учебные материалы

PP: Листки с задачами к курсу.

PDNA: Вероятностная ДНК = вкусные задачи по теории вероятностей.

Летопись семинаров и лекций от тайного благожелателя

Дневник самурая

2024-09-02, лекция 1: Определение события. Определение случайной величины. Аксиомы вероятности. Определение математического ожидания для дискретного случая. Линейность математического ожидания. Математическое ожидание как центр масс. Первое знакомоство с перестановочным тестом и p-значением.

Можно глянуть: главы 2.1 и 7 из WTSK, метод рычага в геометрии.

2024-09-09, лекция 2: Метод первого шага (вероятность выпадения HTH ранее HHT, ожидаемое количество шагов). Метод разложения случайной величины в сумму. Определение случайного вектора. Использование интерпретации ожидания как центра масс в геометрии. Определение теоретической медианы.

Можно глянуть: глава 2.7.2 из BItP, три стратегии решения задачи за 10 минут Visually Explained

2024-09-16, лекция 3: Получение новой информации приводит к пересчёту вероятностей. Определение условной вероятности. Формула полной вероятности. Формула Байеса. Условное математическое ожидание. Формула полного математического ожидания. Независимость пары событий. Независимость набора событий в совокупности. Независимость величин: неформальное определение. Критерий независимости произвольных величин. Критерий независимости дискретных величин.

2024-09-23, лекция 4: Доказательство критерия независимости для дискретных случайных величин: из независимости {X=x} и {Y=y} следует независимость {X in A} и {Y in B}. Независимость величин равносильна E(f(X))E(g(Y))=E(f(X)g(Y)) для произвольных f, g. Определение биномиальной, геометрической (как числа неудач до 1го успеха) и отрицательной биномиальной случайной величины. Общая идея за производящими функциями: как из функции, производящей исходы эксперимента, с помощью производных и подстановок выудить индивидуальные вероятности, совместные вероятности, ожидания любой степени E(X^a), E(X^a Y^b). Формальное определение функции, производящей вероятности, и функцию, производящей моменты, для одной случайной величины и пары случайных величин. Метатеорема: все теоремы о дискретных величинах доказываются перестановкой слагаемых. Основные дискретные распределения: биномиальное, геометрическое, отрицательное биномиальное.

2024-09-30, лекция 5: Ещё дискретные законы распределения: гипергеометрическое. Описание закона распределения через равномерное распределение на подмножестве R^n. Функция плотности как линейная часть вероятности попадания в отрезок. Равномерное распределение на отрезке. Смешанные случайные величины. LOTUS: нахождение ожидания любой функции от случайной величины для величин с функцией плотности и смешанных величин. Функция распределения. Квантильная функция.

2024-10-07, лекция 6: Две геометрии случайных величин и событий: E(XY) как скалярное произведение, Cov(X, Y) как скалярное произведение. Математическое ожидание — проекция в рамках геометрии, задаваемой E(XY). Определение и геометрический смысл дисперсии, стандартного отклонения, ковариации и корреляции. Неравенство Маркова. Неравенство Чебышёва. Неравенство Йенсена: интуитивный смысл.

2024-10-14, лекция 7: Доказательство неравенства Йенсена. Энтропия как минимальное ожидаемое число вопросов для отгадывания и формальное определение. Кросс-энтропия. Доказательство того, что кросс-энтропия больше либо равна энтропии. Совместная энтропия. Условная энтропия. Формула H(X) + H(Y|X) = H(X, Y) без доказательства. Вывод плотности экспоненциального распределения из предпосылки отсутствия памяти. Экспоненциальное распределение максимизирует энтропию при заданном ожидании и неотрицательности.

Семинары

473 = 235 + 238

2024-09-02, 06, семинар 1: задачи 1.1, 1.6, 3.5 из PP

2024-09-09, 13, семинар 2: задачи 2.1, 2.3, 12.7 из PP

2024-09-16, 20, семинар 3: задачи 7.12 и 7.4 из PP

2024-09-23, 27, семинар 4: как извлечь P(X=3), E(X), E(X^2Y) из функции, производящей список исходов, 28.16 из PP

2024-09-30, -10-04, семинар 5: 9.3в, 9.4, 9.7(абвд, кроме дисперсии, аргументы масштабирования и центра масс помимо интегралов), 9.11 из PP

2024-10-07, 11, семинар 6: вычисление Cov, Var, Corr по табличке и из функции плотности, нахождение дисперсии для отрицательного биномиального распределения по свойствам.

2024-10-14, 18, семинар 7: вычисление энтропии геометрического распределения. Изменение энтропии при линейном преобразовании для дискретной величины и величины с функцией плотности. Кросс-энтропия из экспоненциального в равномерное. Условная энтропия для дискретной таблички. Связь энтропии величины с функцией плотности и энтропия дискретной версии этой случайной величины после "огрубления" с малым шагом 1/k.

236

2024-09-06, семинар 1: в начале семинара рассмотрели основные понятия и определения для решения задач. Решили задачи 1.1, 1.6, 3.5 из PP

2024-09-13, семинар 2: нашли ожидание случайной величины с геом. распределением. Решили задачи 2.1, 12.6, 12.10 из PP.

2024-09-20, семинар 3: решили задачи 7.12, 7.4(а), 7.7, 7.13(а) из PP.

2024-09-27, семинар 4: разобрали 7.13, почти разобрали 28.3 из PP. Также рассмотрели один контрпример на независимость(тетраэдр Бернштейна).

2024-10-04, семинар 5: разобрались с определениями, решили 9.3(абв), 9.7(аб) из PP. Решили задачку про три точки на отрезке и найти вероятность получить треугольник. Также вывели формулу для мат. ожидания неотрицательной величины через функцию распределения.

2024-10-14, семинар 6: обсудили дисперсию, ковариацию, коэффициент корреляции и их геометрический смысл. Решили задачу на оценку дисперсии ограниченной величины. посчитали дисперсию геометрического, биномиального. Посчитали дисперсию в задаче о письмах и конвертах.

237

2024-09-09, семинар 1: задачи 1.1, 2.2 из PP, вероятность что n ладей не бьют друг друга при случайной расстановке на шахматной доске n на n, матожидание числа треугольников в случайном графе на n вершинах через сумму индикаторов

2024-09-13, семинар 2: задачи 2.1, 2.6, 12.3, 12.6, 12.7 (без дисперсий) из PP

2024-09-23, семинар 3: задачи 7.2, 7.13, 7.7, 7.8, плюс начали 7.15b (получили неверный ответ) из PP

2024-09-27, семинар 4: дорешали 7.15b с небольшой демонстрацией на питоне, разобрали 28.2 для нечестной монетки плюс посчитали матожидание PP

2024-10-04, семинар 5: задачи 9.1, 9.3абв, 9.11 из PP, философия про то почему бОльшая плотность не всегда означает бОльшую вероятность оказаться в окрестности данной точки (плотность может занимать слишком маленький объем)

2024-10-11, семинар 6: вспомнили определения Cov/Var/Corr, посчитали у пары дискретных величин по табличке вероятностей, посчитали дисперсию у биномиального, геометрического, непрерывного равномерного на отрезке.

239

2024-09-03, семинар 1: задачи 1.1, 1.4, пытались 1.8 из PP. Ещё успели посчитать вероятность N=k бросков монеты до выпадения первого орла, матожидание N. И ещё сделали то же для количества бросков до выпадения 3 орлов (не в серии).

2024-09-10, семинар 2: доказали формулу включения-исключения, решили несложную задачу, порешали 2.7 задачи типа 12.*

2024-09-17, семинар 3: Решили две прямых задачи на формулу Байеса и формулу полной вероятности (без большого количества вычислений). Решили задачу поиска вероятности неисправного кофе-автомата из 3 при условии, что бросили деньги в 1 и 2 и их зажевало. Ещё нашли вероятность, что мяч будет у игрока 3 после шага 10 (все садятся в круг и на каждом шаге бросают мяч соседу с вероятностью 0.3 и оставляют у себя с вероятностью 0.4).

2024-09-24, семинар 4: Вспомнили про метод первого шага, используя формулу полной вероятности и введя в некотором виде формулу полного матожидания, записали формулу для вероятностей нахождения в состоянии i через произведение переходной матрицы на вектор. Совсем немного начали производящие функции, но решили не считать 31ю производную многочлена.

2024-10-01, семинар 5: Исследуем дискретные случайные величины (Биномиальная, Геометрическая и разные похожие) с использованием техник вычислений моментов через производящую функцию. Задачи на распределения величин, посчитанных по набору величин. Первая большая задача про плотность.

2311

2024-09-06, семинар 1: вероятностное пространство, вероятность на нем, вероятность события, случайная величина и ее распределение (индикатор события, сумма двух кубиков, число бросаний монетки до первого орла), матожидание случайной величины (индикатор, один кубик, два кубика), линейность матожидания. Задачи на линейность матожидания, в том числе ЕГЭшная задача про турнир, 1.5, 3.5 с допвопросом о матожидании числа совпадений. Разговор о получении события произвольной вероятности монеткой в контексте 1.8

2024-09-13, семинар 2: Повторили матожидание суммы на примере 12.3. Обсудили условную вероятность и формулу полной вероятности, условное матожидание, решили задачи на метод первого шага 2.1, 2.3, 2.7.

2024-09-20, семинар 3: Условная вероятность, формула полной вероятности, формула Байеса: 7.1, классическая задача про болезни и тесты, простейшие задачки на общее понимание, обсуждение двух подходов: вычисления условной вероятности по формуле и составления нового вероятностного пространства и подсчет вероятности в нем. Независимые события (события "пики" и "дама" в обычной колоде и колоде с джокерами), независимые в совокупности события, построили пример попарно независимых, но не независимых в совокупности. Обсудили биномиальное распределение. решили задачу: "в корабле к отсеков, чтобы корабль затонул, нужно поразить 2. Независимо выпускают n ракет, каждая из которых поражает случайный отсек с вероятностью p. Найти вероятность потопления корабля"

2024-09-20, семинар 4: Примеры одинаково распределенных зависимых СВ, независимые СВ. Производящая функция и ее свойства. Посчитали для биномиального производящую функцию и второй момент. Обсудили, что будет меняться в случае функции, производящей моменты. Обсудили функцию, производящую множество исходов, как из нее доставать уже известные функции, как ее искать на примере бросания монетки до выпадания HT

2024-10-11, семинар 5: Составили табличку стандартных дискретных распределений, посчитали матожидание геометрического, обсудили дисперсию и ковариацию и их свойства (в дискретном случае), досчитали дисперсии основных распределений. Обсудили вероятностное пространство в общем случае, понятие СВ в общем случае. Дали определение ФР, посчитали ФР для явно заданной СВ. Дали определение плотности.

2024-10-12, семинар 6: Обсудили свойства ФР, как считать вероятность попадания в промежуток в терминах ФР. Выразили ФР 1/X, cos X. Обсудили как выражается веротяность попадания в множество через плотность. для 1/Х выразили плотность в случае абсолютной непрерывности Х. Обсудили формулу для МО в общем виде через интеграл Стильтьеса и как вычислять МО для функции, разлагающейся в сумму абсолютно нерпрерывной и функции скачков, посчитали МО для пары таких СВ

2310, 2312

2024-09-06, семинар 1: задача 1.1 из PP. Определили вероятностное пространство в виде тройки, множество исходов рассматривали конечное и счётное. Решили 3 счётные задачи на комбинаторику про колоды карт и счетные последовательности цифр. Привели геометрическое и аналитическое решения задачи про нахождение предела последовательности вероятностей. В конце нашли математическое ожидание геометрически распределённой случайной величины.

2024-09-13, семинар 2: задача 2.1 из PP. Задача на упорядоченные и неупорядоченные наборы. Задача про классическое вероятностное пространство и про пространство с неравновероятными исходами. Разобрали парадокс Монти Холла. Ввели понятия условной вероятности и независимых случайных величин. Сформулировали и обсудили идеи доказательств трёх теорем: теорема умножения вероятностей, формула полной вероятности и формула Байеса.

2024-09-20, семинар 3: Решили задачу на определение условной вероятности. Обсудили парадокс теоремы Байеса на примере задачи про редкое заболевание, а также посмотрели простую программу на Python, которая считает вероятность в зависимости от количества проведенных тестов на заболевание. Обсудили условное математическое ожидание, некоторые его свойства и рассмотрели пример с подбрасыванием кубика. В конце решили задачу на парадокс дней рождений.

2024-09-27, семинар 4: Обсудили коллизии хеш-функций и связь с атакой "дней рождений". Определили независимость или зависимость случайных величин в четырёх разных вариантах. Обсудили, что неверно утверждать, что матожидание частного независимых случайных величин равно частному матожиданий, также привели пример использования подобного факта в некоторых статьях. В конце решили задачу на поиск функции производящей исходы, а также нашли E(X), E(Y^2), E(XY) с помощью найденной функции.

2024-10-04, семинар 5: Решили две простые задачи на условную вероятность и на теорему об умножении вероятностей. Обсудили связь дерева событий с условной вероятностью и теоремой об умножении вероятностей. Нашли производящую функцию моментов для геометрически распределенной случайной величины и с помощью нее нашли матожидание. Нашли производящую функцию моментов и матожидание суммы случайного количества н.о.р случайных величин.

2024-10-11, семинар 6: Привели аналогии между дискретными и непрерывными случайными величинами. Нарисовали графики функций от случайных величин. Вспомнили определение и свойства дисперсии. Решили простую задачу на подсчет дисперсии и нашли дисперсию геометрически распределенной случайной величины. Обсудили, когда может быть матожидание и дисперсия бесконечны. Далее вспомнили неравенства Маркова и Чебышева, вывели следствия и решили 3 задачи на применение этих неравенств. Обсудили, что неравенство Маркова может давать как точную оценку, так и очень слабую. Показали, что неотрицательность случайной величины в неравенстве Маркова является существенным условием.

Источники

Источники мудрости, которые я постарался не замутить :)

WTSK: Tim Hesterberg, What Teachers Should Know About the Bootstrap: вкусное и доступное изложение бутстрэпа и перестановочных тестов.

BItP: Blitzstein, Hwang, Introduction to Probability: учебник, записи лекций, гарвардский курс.