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

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