Friday, January 18, 2013

Random Walks and Brownian Motion

This Tuesday, Jan 15,  we had our  first Discovery Cafe  meeting in 2013. I had promised before to give some introductory lectures on random walks and Brownian motions. So  we started the year with this. Notice that now we meet at 3:30 PM on Tuesdays. Ruth took some  notes and I am just  using these notes here. I leave out many details. For references you can check out these two books:  1 and 2

There are two problems that at first look quite unrelated but our first task is to understand  the close relation  between the two. Random walks and the Dirichlet problem.  In one dimension, on a finite set of points 0, 1, .....up to n, a  walker randomly walks around. The chances of going forward or backward is   % 50 each . Let P(i) be the probability of the random walker hitting  the right end  point  n before hitting the end point 0, when he starts at i. Say point n  is the jail, where the police can keep the drunk overnight, and  point 0 can be the drunk's home. So we are looking at the probability that he will end up at the police station, versus ending up at home. This  process is potentially infinite - the drunk can take up to an infinite number of steps back and forth without hitting either boundary. But never mind this at the moment and we neglect this possibility. We come back to this in the  next week when we carefully define our probability space.

Finding  the probability distribution P(i) is closely related to another problem, the discrete Dirichlet problem. We are looking for a function  f(i) for i=1, ....n-1, with given boundary values  f(0)=0 and f(n)=1, and such that f satisfies  the equation
$$f(i) = \frac{f(i + 1) + f(i-1)}{2}$$
We say f has the mean value property. We shall see that this equation is the discrete analogue of
$$ \Delta f=0$$
where \( \Delta  f =  f'' \) is the second derivative operator, the Laplace operator in dimension one. Thus f can be regarded   as a discrete harmonic function with given boundary  values f(0) and f(n).

 We checked that this Dirichlet problem has a unique solution. While a proof of this fact in dimension one is very easy and one can write in fact simple formula for f (what is it ?), existence of solutions in higher dimensions even in this discrete case is not totally trivial and in particular no simple formula exist. So the point of this probabilistic approach is that it works in all dimensions with minor modifications.  First of all uniqueness follows from the following  maximum principle:

Lemma (maximum principle): Any harmonic  function achieves  its maximum on the boundary points.

This easily follows from the mean value property. Then we used this maximum principle to prove uniqueness:
for any two solutions the difference \( f_1-f_2 \) is also a solution with boundary values equal to zero. This  will violate the maximum principle unless \( f_1 = f_2 \) at all points.

Our next goal was to show that the the probability function P(i) has the mean value property. Since it clearly satisfies the required boundary conditions,  this will prove that P is the harmonic function we were looking for. This is the first relation between random walks and the Dirichlet problem.

This all follows from a cute property of probabilities: Let X be a probability space, L and R be two mutually exclusive events that cover the whole X. Then for any event E we have
 $$Prob (E)= Prob (E; L) Prob (L) $$
$$+ Prob (E; R)Prob (R)$$

 Starting your random walk at i, let L = going left,  R = going right, E = the event of getting to the end  point n  before getting to 0. Now it is not difficult to check, using the above probability identity,  that  P has the mean value property and since it clearly satisfies the boundary conditions it must be the solution of the Dirichlet problem. 

Next week we shall carefully defines the probability space X, as the space of all random walks and show how to define a probability measure on it, and will give a general formula for the solution in terms of integration over this path space. We shall then move to higher dimensions where things can get more even interesting!   Here is graphs of some random walks all starting  at the origin and going up to 100 steps.