Topics in Probability: Random Walks and

What is a random walk? hard to define in general. Better start with an example. Here’s THE example from the founder of the field, George Polya: ”... he and his fiancee (would) also set out for a stroll in the woods, and then suddenly I met them there. And then I met them the same morning repeatedly, I don’t remember how many times, but certainly much too often and I felt embarrassed: It looked as if I was snooping around which was, I assure you, not the case. I met them by accident- but how likely was it that it happened by accident and not on purpose?” We model this setup by two walkers, each taking a step north, south, east or west with equal probabilities every second. Will they meet? On Z2 this is equivalent to a single walker, asking if and how often he comes back. Definition. A Simple Random Walk on a graph G is a stochastic process xi with Prob(xi+1 = v) = 1 dxi for v ∼ xi, and 0 otherwise. 1 Definition. a graph G is called recurrent if a SRW on G returns to x0 with probability 1. If G is not recurrent, it is called transient. Exercise. Show that the definition does not depend on x0. Exercise. Is the 2 walkers model always equivalent to 1 walker? i.e. is there a recurrent graph where 2 independent SRWs do not meet infinitely often? Other interesting questions besides recurrency: Hitting times and hitting probabilities. Example. A man plays in the casino fair games with 1 $ bets. How much time till he earns 1$? how much is he likely to lose before he recovers? Example. A drunkard leaves his house. When is he likely to return? Example. A SRW on Z2 stops when it hits the set {(0,−1), (0, 0), (0, 1)}. What is the distribution? if the walk starts far enough does it matter in which direction? Theorem. (Stirling’s formula) lim n→∞ n!