Версия 17:32, 5 декабря 2024

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

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

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

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

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

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

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

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

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

Оценивание

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

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

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

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

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

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

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

Ведомость с оценками за ДЗ

Оценки за кр1

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

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

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

Резервный день 1 для пропустивших по уважительной причине состоится 2024-12-02 в 19:40, R405

Показ контрольной 1:

• задачи 3, 4, 5, 6: очно, четверг, Макс, Борис, 2024-12-05, 18:10-21:00, G408
• задачи 1, 2: заочно до 2024-12-08, Вероника, https://t.me/Moskchan

Экзамен, модуль 2 состоится 2024-12-24 в 9:30, аудитории R301, R304, R401, R404, демо, условие.

Экзамен, модуль 3 состоится 2025-03-26 в 14:40, аудитории R301, R404, R405, R503, демо, условие.

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

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

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

Видео-летопись семинаров и лекций и конспект от тайного благожелателя (updated 2024-10-23]

Cambridge statistical tables

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

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) без доказательства. Вывод плотности экспоненциального распределения из предпосылки отсутствия памяти. Экспоненциальное распределение максимизирует энтропию при заданном ожидании и неотрицательности.

• Cristopher Olah, Visual Information Theory, https://colah.github.io/posts/2015-09-Visual-Information/

• Grand Sanderson, Solving Wordle using information theory, youtube.

• Artem Kirsanov, Key equation behind probability, youtube. У Артёма кросс-энтропия обозначена H(P, Q), а не CE(P||Q)).

• Конспект аналогичной старой лекции псмо на русском.

• Keith Conrad, Maximal entropy distributions.

2024-10-21, лекция 8: Ковариационная матрица и её свойства. Совместная функция плотности. Условная функция плотности. Критерий независимости в терминах функций плотности и распределения. Связь индивидуальной и совместной функций плотности и функций распределения. Смена плотности при замене переменных: домножение на якобиан и неформально про дифференциальные формы. Формула свёртки. Разложение совместной плотности для графической модели. Представление произвольной совместной функции распределения с помощью копулы.

• Про дифференциальные формы: videos by Michael Penn, short intro by Dony Arapura

• What is a convolution от 3b1b

• From graphical models to Probabilistic ML

2024-11-11, лекция 9: Пуассоновский поток: аксиомы. Вывод пуассоновского распределения количества событий и экспоненциального времени между событиями из аксиом. Сумма независимых пуассоновских потоков — это пуассоновский поток (половина доказательства). Вероятность того, что одна экспоненциальная величина будет меньше другой, независимой.

2024-11-18, лекция 10: Гамма-распределение как сумма нескольких экспоненциальных: вывод плотности через вероятность попадания в малый отрезок. Обобщение плотности на случай положительного параметра $a$. Гамма-функция. Бета-распределение как отношение гамма-распределений. Бета-функция.

2024-11-25, лекция 11: Вывод нормального распределения из предпосылок Гаусса. Вывод нормального распределения из предпосылок Гершеля — Максвелла.

• Saul Stahl, The Evolution of the Normal Distribution: вывод Гаусса с историей.

• Grand Sanderson, Why pi is in the normal? вывод Гершеля—Максвелла

• James Stein, Normal Distribution: глава про нормальное распределение (Гаусс, Гершель—Максвелл, Лэндон etc)

• William Herschel, концерт для габоя

• William Herschel, On the theory of Probabilities: вывод нормального распределения словами на стр. 189-191

2024-12-02, лекция 12: многомерное нормальное распределение. Функция плотности невырожденного многомерного нормального. Функция производящая моменты для многомерного нормального. Формула Иссерлиса с ненулевыми ожиданиями и доказательством. Условное распределение: вывод условного ожидания и условной дисперсии через разложение величины в сумму независимых.

• альтернативный вывод условного многомерного нормального распределения
• Хитрый лис Иссерлис

Семинары

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.

2024-10-21, -11-01, семинар 8: 16.18, 16.23 из PP, свёртка двух экспоненциальных величин

2024-11-11, 15, семинар 9: задачи на пуассоновский поток из PP

2024-11-18, 22, семинар 10: задачи на бета и гамма-распределение

2024-11-25, 29, семинар 11: задачи на нормальное распределение, 18.1, 18.2, 18.3, 18.5 из PP

2024-12-02, 06, семинар 12: задачи на многомерное нормальное: 24.16аб, 24.17аб, 24.18, 24.10 из PP

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, посчитали у пары дискретных величин по табличке вероятностей, посчитали дисперсию у биномиального, геометрического, непрерывного равномерного на отрезке.

2024-10-18, семинар 7: вычисление энтропии геометрического распределения; ограниченность энтропии снизу и сверху в дискретном случае; изменение энтропии при линейном преобразовании для дискретной величины и величины с функцией плотности; условная энтропия, KL дивергенция и кросс-энтропия, неотрицательность KL, интерпретация на пальцах с точки зрения теории информации.

2024-11-01, семинар 8: 16.18, 16.23 из PP, свёртка двух экспоненциальных величин

2024-11-08, семинар 9: решали пробный вариант КР

2024-11-15, семинар 10: 13.1, 13.2, 13.5, 13.7 из PP

2024-11-22, семинар 11: разбор КР

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: Исследуем дискретные случайные величины (Биномиальная, Геометрическая и разные похожие) с использованием техник вычислений моментов через производящую функцию. Задачи на распределения величин, посчитанных по набору величин. Первая большая задача про плотность.

2024-10-08, семинар 6: разминочная про плотность и функцию распределения. Считаем дисперсию, ковариацию и корреляцию по 2x2 таблице и в равномерном распределении на круге и квадрате [-1,1]х[-1,1].

2024-10-15, семинар 7: пара задач про экспоненциальное распределение, расчёты по теории информации(считаем всякое, чтобы привыкнуть).

2024-10-22, семинар 8: письменные источники не сохранились до наших дней. Согласно преданиям, оьсуждали двери и около контрольной. Говорят, ввели пуассоновский процесс.

2024-???, семинар 9: решаем задачи на пуассоновское в разных формах и обсуждаем омалые в порядковых статистиках.

2024-???, семинар 10: учимся интерпретироввть гауссовское, пользоваться таблицами для функции Лапласа, а также немного работать с многомерным гауссовским.

2024-3-12, семинар 11: Копаем во все стороны многомерное гауссовское: считаем вероятности для линейных комбинаций гауссовских, проверяем зависимость, вычисляем условные законы, матожидания и ковариационные матрицы, вспоминаем спектральное разложение и разложение Холецкого.

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/Х выразили плотность в случае абсолютной непрерывности Х. Обсудили формулу для МО в общем виде через интеграл Стильтьеса и как вычислять МО для функции, разлагающейся в сумму абсолютно нерпрерывной и функции скачков, посчитали МО для пары таких СВ

2024-10-18, семинар 7: Обсудили геометрию, заданную скалярным произведением EXY и cov(X,Y), поиск ортогонального элемента и проекции. Посчитали энтропию и кросс-энтропию в дискретном и непрерывном случаях, посчиали совместную и условную энтропию в дискретном случае (23.2, 23.4, 23.9)

2024-11-01, семинар 9: Совместная плотность и ф.р., подсчет вероятностей, маргинальные плотности, замена переменной через якобиан, свертка, матожидание

2024-11-09, семинар 10: Условная плотность, формула условной вероятности. Задача на восстановление маргинальной плотности по условной. Разбор задач из "Летучей мыши"

2024-11-19, семинар 11: Разбор контрольной работы

2024-11-22, семинар 12: Пуассоновский поток - решали задачки из задачника

2024-11-29, семинар 13: Нормальное распределение - задачи из PP, повторили функцию, порождающую моменты, обсудили ее свойства в абсолютно непрерывном случае

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 задачи на применение этих неравенств. Обсудили, что неравенство Маркова может давать как точную оценку, так и очень слабую. Показали, что неотрицательность случайной величины в неравенстве Маркова является существенным условием.

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

2024-11-1, семинар 8: Разобрали демо-вариант контрольной работы "Тыква".

2024-11-8, семинар 9: Разобрали демо-вариант контрольной работы "Летучая мышь".

2024-11-15, семинар 10: Понятие случайного процесса. Определение пуассоновского процесса, его свойства. Три простые задачи на пуассоновское распределение. Задачи 13.1 и 13.4 из PP.

2024-11-22, семинар 11: Определения Бета-функции и Гамма-функции. Бета и Гамма распределения, их функции плотности и графики. Нахождение моды случайных величин, имеющих Бета и Гамма распределения. Связь пуассоновского процесса с Гамма распределением. В конце нашли производящую функцию моментов Гамма распределения.

Источники

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

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

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