Present the paper: Mixing of random walks and other diffusions on a graph - A survey by L. Lovasz and P. Wrinkler
  • Trang chủ
  • Present the paper: Mixing of random walks and other diffusions on a graph - A survey by L. Lovasz and P. Wrinkler

Present the paper: Mixing of random walks and other diffusions on a graph - A survey by L. Lovasz and P. Wrinkler

Thời gian: 09:30 đến 11:00 Ngày 14/04/2016

Địa điểm: C2-714

Báo cáo viên: Nguyễn Hoàng Thạch

Tóm tắt:

This survey provides a compact overview of two processes on graphs: random walks and chip-firing games (CFG). I will present the "random walk" part of the survey. The authors give the definitions of mixing time, hitting time for random walks on finite graphs. They briefly introduce two tools for estimating the speed of mixing, namely eigenvalues and conductance. Then they define stopping rules and give a set of optimal stopping rules. Finally, they discuss an alternative notion mixing time and its properties.