随机过程
This course studies stochastic processes with reinforcement, in which past observations influence future dynamics. The course is organized around three interconnected topics (see Syllabus) and a common question: How does feedback shape the long-term behavior of a stochastic system?
The course emphasizes representative examples, probabilistic ideas, and qualitative understanding rather than technically demanding proofs. Martingales, exchangeability, coupling, stochastic approximation, concentration inequalities, and hidden Markov structures will be introduced through the models in which they arise.
Each meeting consists of three 45-minute periods. Lectures will be combined with in-class problem sessions, during which the instructor and students work through examples, calculations, simulations, and selected proof arguments together.
As this is a non-credit course, there will be no formal examination or assessment. No regular take-home homework will be assigned. Optional reading and computational experiments may be suggested for interested students.
The course emphasizes representative examples, probabilistic ideas, and qualitative understanding rather than technically demanding proofs. Martingales, exchangeability, coupling, stochastic approximation, concentration inequalities, and hidden Markov structures will be introduced through the models in which they arise.
Each meeting consists of three 45-minute periods. Lectures will be combined with in-class problem sessions, during which the instructor and students work through examples, calculations, simulations, and selected proof arguments together.
As this is a non-credit course, there will be no formal examination or assessment. No regular take-home homework will be assigned. Optional reading and computational experiments may be suggested for interested students.
Lecturer
Date
4th September, 2026 ~ 8th January, 2027
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Friday | 09:50 - 12:15 | RUC | - | - | - |
Prerequisite
A solid undergraduate course in probability is recommended. Familiarity with conditional expectation, Markov chains, and basic convergence concepts is helpful. Martingale and concentration methods needed in the course will be reviewed or introduced as they arise. The course is intended primarily for senior undergraduate students and beginning graduate students interested in probability and stochastic processes. It is also recommended that the audience take the course “Online Learning” by Yuval Peres in parallel with this course
Syllabus
1. Urn Models (Weeks 1–4): Classical Pólya urns, exchangeability and random limits, generalized and nonlinear urns, stochastic approximation, and phase transitions caused by different reinforcement strengths.
2. Reinforced Random Walks (Weeks 5–10): Vertex-reinforced, edge-reinforced, and step-reinforced random walks, with emphasis on one-dimensional models. Topics include local times, strong reinforcement and trapping, localization of vertex-reinforced walks, partial exchangeability and random-environment representations, spatial Markov descriptions of local-time processes, the elephant random walk and its phase transition, and random recursive tree representations. Results on higher-dimensional lattices and general graphs will be discussed at a survey level.
3. Stochastic Multi-Armed Bandits (Weeks 11–15): Stochastic bandit models, regret, failures of naïve reinforcement and greedy policies, explore-then-commit, Upper Confidence Bound algorithms, information-theoretic lower bounds, and Thompson sampling. Particular attention will be paid to the relationship between reinforcement, learning, and the exploration–exploitation tradeoff.
4. Comparative Case Studies (Week 16): A comparison of random limits, localization, lock-in, and controlled exploration across urns, reinforced random walks, and stochastic bandits.
2. Reinforced Random Walks (Weeks 5–10): Vertex-reinforced, edge-reinforced, and step-reinforced random walks, with emphasis on one-dimensional models. Topics include local times, strong reinforcement and trapping, localization of vertex-reinforced walks, partial exchangeability and random-environment representations, spatial Markov descriptions of local-time processes, the elephant random walk and its phase transition, and random recursive tree representations. Results on higher-dimensional lattices and general graphs will be discussed at a survey level.
3. Stochastic Multi-Armed Bandits (Weeks 11–15): Stochastic bandit models, regret, failures of naïve reinforcement and greedy policies, explore-then-commit, Upper Confidence Bound algorithms, information-theoretic lower bounds, and Thompson sampling. Particular attention will be paid to the relationship between reinforcement, learning, and the exploration–exploitation tradeoff.
4. Comparative Case Studies (Week 16): A comparison of random limits, localization, lock-in, and controlled exploration across urns, reinforced random walks, and stochastic bandits.
Reference
R. Pemantle, A Survey of Random Processes with Reinforcement, Probability Surveys 4 (2007), 1–79.
T. Lattimore and C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.
A. Slivkins, Introduction to Multi-Armed Bandits, Foundations and Trends in Machine Learning, 2019.
Additional notes and selected research articles will be provided by the instructor.
T. Lattimore and C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.
A. Slivkins, Introduction to Multi-Armed Bandits, Foundations and Trends in Machine Learning, 2019.
Additional notes and selected research articles will be provided by the instructor.
Audience
Advanced Undergraduate
, Graduate
Video Public
Yes
Notes Public
Yes
Language
Chinese
Lecturer Intro
Shuo Qin has been the first Chern Instructor at BIMSA. He obtained a Ph.D. in mathematics in 2024 from New York University under the supervision of Prof. Pierre Tarrès. His work is in probability theory, especially in random processes with memory or reinforcement.