Виктор Алексеевич Клепцын

Модели с подкреплением: урна Пойа и теорема о пяти вершинах

В. А. Клепцын планирует провести 4 занятия.

Доступны 4 видеозаписи курса.

Урна Пойа — процесс, устроенный следующим образом. В начале в урне находится какое-то количество красных и синих шаров — например, один красный и один синий шар. На каждом шаге мы вытаскиваем из урны случайный шар, возвращаем его обратно, и добавляем ещё один того же цвета. Что мы увидим через большое число шагов?

Этот процесс может быть (игрушечной) моделью в следующей ситуации: допустим, что за новую нишу на рынке борются две более-менее равноценные программы, и каждый новый пользователь спрашивает у случайно выбранного приятеля, чем тот пользуется.

Уже в этой задаче ответ интересен — и, решая её различными способами, мы увидим сразу несколько разных математических идей: естественным образом возникнут мартингалы и дифференциальные уравнения, экспоненциально распределённые случайные величины и пуассоновский процесс.

А что будет, если новый пользователь спрашивает совета у двух друзей — иными словами, если выбираются с возвращением два шара, и третий добавляется, только если их цвета совпадают? Оказывается (и мы это увидим), ответ кардинально меняется.

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

Программа-максимум

  1. 1. Урна Пойа; прямое вычисление, сходимость и описание предела.
  2. 2. Закон больших чисел и переход к дифференциальным уравнениям.
  3. 3. Экспоненциальные величины, пуассоновский процесс и конструкция Рубина.
  4. 4. Другие весовые функции: «богатые становятся ещё богаче» и монополия в пределе.
  5. 5. Случайное блуждание с подкреплением в вершинах (vertex-reinforced random walk) и теорема о пяти вершинах.
  6. 6. Модели на графах: несколько взаимодействующих урн Пойа.

От слушателей не предполагается знакомства с теорией вероятностей (кроме, разве что, интуитивного понимания) — одной из целей курса является неформальное знакомство с её понятиями. Правда, и совсем строгих и формальных доказательств в курсе тоже почти не будет — только правдоподобные описания, «как должны обстоять дела».

Материалы


E-mail оргкомитета:

dubna@mccme.ru