Ori Gurel-Gurevich

Consider the classical balls-and-bins setup: n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. What happens when instead of throwing balls completely by random, there...

A simple random walk (SRW) on a graph is a Markov chain whose state space is the vertex set and the next state distribution is uniform among the neighbors of the current state. A graph is called recurrent if a SRW on it returns to the starting vertex...

Let T be the return time to the origin of a simple random walk on an infinite recurrent graph. We show that T is heavy tailed and non-concentrated. More precisely, we have i) P(T>t) > c/sqrt(t) ii) P(T=t|T>=t) C log(t)/t Inequality i) is attained...

Abstract: We will explore the relation between random walks on graphs and the properties of the graph as an electric network. We will use these to prove some classic theorems of Polya (about recurrence and transience of lattices), and some less...