The goal of this class is to acquire mathematical tools and engineering insight about networks whose structure is random.
Many communication networks, such as the global Internet and its multiple interconnected autonomous domains, mobile ad hoc and embedded sensor networks, social networks, and peer-to-peer overlay networks, usually evade detailed engineering and exhaustive measurement to rely instead on principles of self-organization. This new world of massive scale, lack of central control, and randomness requires new theoretical tools to reason about networks and their behavior, as well as new approaches to engineer for and measure aggregate properties. Most of these tools are borrowed from other fields, such as random graph theory, statistical physics, nonlinear dynamical systems, random algorithms, developmental biology, and game theory.
This course will bring together elements of these theories and their application to "large-scale, self-organized or uncontrolled" networks. It will provide an introduction to and perspective on this emerging field, and an opportunity to track and discuss new developments. The course will balance mathematical rigor with practical lessons for engineering.
In this course, various aspects of probability theory are considered. The first part is devoted to the main theorems in the
field (law of large numbers, central limit theorem), while the second part focuses on the theory of martingales in discrete
The study of Markov chains finds many applications in computer science
and communications. The goal of the course is to get familiar with the
theory of Markov chains, and to get an overview of some applications of
this theory to problems of interest in communications, computer and