BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv5.2.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Eurandom
X-ORIGINAL-URL:https://www.eurandom.tue.nl
X-WR-CALDESC:Events for Eurandom
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20201208T154500
DTEND;TZID=UTC:20201208T164500
DTSTAMP:20201020T222027
CREATED:20201005T120646Z
LAST-MODIFIED:20201005T120646Z
UID:3809-1607442300-1607445900@www.eurandom.tue.nl
SUMMARY:Eindhoven SPOR Seminar
DESCRIPTION:Guillem Perarnau \nExtremal stationary values for directed random graphs \nIn this talk\, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given (bounded) degrees. While for undirected graphs the stationary distribution is simply determined by the degrees\, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk\, as shown by Bordenave\, Caputo\, and Salez. However\, typical results provide no information on the minimum value\, which is important for many applications. Recently\, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk\, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form n^{-(1+C+o(1))}\, for a constant C determined by the degree distribution. In particular\, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods\, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories\, controlled by large deviation rate functions. As a by-product of our proof\, we also determine the hitting and cover time in random digraphs. This is joint work with Xing Shi Cai.
URL:https://www.eurandom.tue.nl/event/eindhoven-spor-seminar-4/
LOCATION:MS Teams
CATEGORIES:STO Seminar
END:VEVENT
END:VCALENDAR