Present the paper: Mixing of random walks and other diffusions on a graph - A survey by L. Lovasz and P. Wrinkler (part 2)
  • Home
  • Present the paper: Mixing of random walks and other diffusions on a graph - A survey by L. Lovasz and P. Wrinkler (part 2)

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

Time: 09:30 to  11:00 Ngày 21/04/2016

Venue/Location: P701

Speaker: Hoàng Ngọc Thạch

Content:
Báo cáo viên: Nguyễn Hoàng Thạch
Cơ quan: Viện Toán học, VAST
Abstract:

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.