Теория вероятностей 2024/25 (основной поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Цели и задачи курса)
Строка 8: Строка 8:
  
 
У самурая нет цели и ничего кроме пути.
 
У самурая нет цели и ничего кроме пути.
 +
 +
Вероятный план:
 +
<div class="mw-collapsible mw-collapsed" style="width:1000px; overflow: hidden;">
 +
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. вероятностные доказательства детерминистических теорем
 +
 +
</div>
  
 
== Оценивание ==
 
== Оценивание ==

Версия 18:59, 12 сентября 2024

О курсе

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

侍には目標がなく道しかない [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.

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

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

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

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

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

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

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

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

Можно глянуть: главы 2.1 и 7 из WTSK

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

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


Семинары

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


237

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

239

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

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

2311

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

Источники

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

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

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

Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_вероятностей_2024/25_(основной_поток)&oldid=86274»