MATH 4800 (Fall '08)
Research Experiences for Undergraduates
Random Walk: Modeling, Theory, and Applications
Time & Place: Tue 10:45 a.m. - 12:05 p.m. in
JWB 240 and
Thu 10:45 a.m. - 12:05 p.m. in
LCB 215
Instructor:
Firas Rassoul-Agha
Phone: (801) 585-1647,
E-Mail:
firas@math.utah.edu
Office Hour: by email or by appointment, at
LCB 209
You can find some matlab codes here.
Material:
November 13 We will discuss an "energy-relaxation" algorithm to generate
self-avoiding walks. Take a look at this paper. This paper is more clear and more complete.
November 11 We discussed and shaped the Coin-Detector project.
Week 10 homework: No Homework this week. Started working on the projects.
November 6 We discussed the Self-Avoiding-Walk project.
November 4 We discussed the pivot algorithm.
Week 9 homework:
Code the pivot algorithm and see how large of a walk you can generate in a reasonable time (say in 30 minutes).
October 30 I talked about the two projects (the self-avoiding walk project and the change-point-detection project).
October 28 I talked more about the pivot algorithm.
Week 8 homework:
Write a code that takes an array "coins" of 0s and 1s and computes
the longest run of 1s. Then, given a significance level alpha and using
Table 1 of this paper
predicts whether or not the sequence of coins came out of fair coin tosses.
Test how well this works by first using coins=round(rand(1,200)) and then
again by setting coins to a sequence of 200 0s and 1s that you type by
hand (as randomly as you can!). Can you trick this test?
Improve the above code by looking at the longest run of 1s up to time n
with n varying from 1 to length(coins). That is: now we look at the whole
process. See if you can trick it this time!
Code the dymerization algorithm to generate a self avoiding walk in 2d then
in 3d. Try to see how long of a walk you can generate in a
"reasonable" time.
October 23 We saw how to improve the heat equation solver (by not going
all the way to the boundary). (
Here is the result with
resolution N=400 and 500 samples.)
Then, we talked about the dymerization algorithm
for generating self avoiding walks and then about the pivot algorithm.
October 21 We considered the following problem: we are given a sequence
of n heads and tails and would like to check if this sequence comes from
tossing a coin that comes up heads with probability p, or not. The key was to
observe the longest run of, say, heads. Call that Rn. It turns
out that as n grows, the average value of Rn is equivalent to
log(n(1-p))/log(1/p) while its variance converges to a constant! This leads
to the simple test: check that Rn is close enough to the average
value. This is based on this paper.
Week 7 homework:
Solve the heat equation on the square [0,1]2 with boundary
conditions: f(0,y)=-1, f(1,y)=2, f(x,0)=0, f(x,1)=1, for 0< x<1 and 0< y<1
and f(0,0)=f(0,1)=f(1,0)=f(1,1)=3. Plot your solution in color, with higher
values of f being more red (hot) and lower values of f being more blue (cold).
Compute the integral, from 0 to 1, of 2B dB.
Now compute the above integral numerically. Use the right-most-point and
the left-most-point methods. Are the two answers the same? If not, then which
one is the correct one? Can you say why that is?
What is the integral, from 0 to 1, of B2 dB? (It is OK if your
final answer is in terms of B(1) and the integral of B dt, from 0 to 1.)
Simulate a lot of samples of a lot of fair coin tosses and check the large deviations
principle works with the rate function we got in the lecture.
October 9: I explained a bit what stochastic integrals are and we
computed our first stochastic integral! Then, we talked a bit about
large deviations for coin tosses; we considered n tosses of a coin that
comes up heads with probability p and computed the asymptotics of the
probability the fraction of heads turns out to be s (instead of p).
October 7: Mike showed how BM is related to the heat equation.
Here are some notes.
Week 6 homework:
Play with the BM (Brownian Motion) code I posted to get a picture of
what its paths look like.
Write a code that simulates the process Y(t) which is the solution
to dY=a(Y)dB+b(Y)dt, where B is BM and a and b are some given functions.
The initial condition is Y(0)=0.
Use your code to simulate the solution to dY=2B dB, Y(0)=0.
Compare the resulting Y with B2. Do you see how d(B2) is not 2B dB?
Let Z=B2. What is the stochastic differential equation (SDE) that Z
satisfies? That is: what is a and what is b? Now simulate the solution of this
SDE and compare it with Z. Ito's formula works, doesn't it?!
October 2: Yunhye presented Ito's calculus, in the form of Ito's
formula. We saw how it is different from the classical calculs and computed
our first "stochastic integral". I then talked about how
to simulate diffusions.
September 30:
We saw how Donsker's theorem coincides with how Brownian motion was discovered,
explains Einstein's predicates (a)-(d), and implies the reflection pricniple.
We then talked about how BM is recurrent in 1d, not point recurrent in multi-d,
region-recurrent in 2d, and transient in d=3 and highr. We also discussed how
BM is space-filling in 2d, even though it is not point recurrent. [Analogy was
made with P(U=x)=0, for all x, while P(U=x for some x)=1, where U is uniformly
distributed.]
Yunhye then presented part 2 of lecture 9 of
the notes where Ito's diffusions are introduced (and so we saw what "white
noise" means).
Week 5 homework:
Play with the CLT and LIL (Law of Iterated Logarithm) codes I posted and
understand how they work AND the difference between CLT and LIL. Try to explain
this difference in your own words.
Write a code to see how the expected number of returns to 0 by time n
compares to log n/π, for a 2d walk, and seems to be bounded for a 3d walk.
Write a simple code to generate self-avoiding random walks in d=2 and
d=3. For starters, generate a classical simple random walk lots of times
and pick one that does not self intersect.
If you want to generate one self-avoiding walk of length n (large)
with the above "naive" method, how many classical random walks
do you need to generate? (Hint: your answer should depend on the connectivity
constant.) Can you give a lower bound? (Hint: you will need to find an
upper bound on the connectivity constant.)
Do you think the above method is reasonable?
September 25: We talked again about CLT and LIL and I presented the
second research project.
Yunhye presented the history of Brownian motion
(still following
these notes) and we saw how it can be produced
from random walks by rescaling space and time appropriately.
September 23: Dave lectured on multi-d simple random walk
and the self-avoiding
walk (always following these notes). Then I presented one of the two projects
we will be working on. Essentially, it has to do with figuring out how
to (efficiently) simulate self avoiding walks.
Week 4 homework:
Finish the proof that P(S2j+1=1)~(2/π(2j+1))1/2, where Sn is a 1d simple random walk.
Write a code to see how the expected number of returns to 0 by time n
compares to (2n/π)1/2, for a 1d simple random walk.
Write a code that plots the path of a 1d walk (Sn verses n)
and see how it takes a long time to get to any prefixed level L.
September 17: We saw how a 1d simple random walk reaches every point,
with probability 1, but is never expected to get there! (This is related to
the
St. Petersburg paradox in economics.)
For this, we observed that the set of
paths where the walk gets from 0 to 1 in at most n steps is in 1-1
correspondance with the set of paths where the walk starts from 0 and is at 0
or 1 after exactly n steps.
September 15: Nate proved Markov's and Chebyshev's inequalities
following these notes) and we
saw the proof of the strong law of large numbers (including a discussion of
sets of measure 0).
Week 3 homework:
Prove that if X and Y are independent, then Var(X+Y)=Var(X)+Var(Y).
Code a simple one-dimensional random walk and explore the properties
Nate proved in the lecture (mean is 0, variance grows like n, etc).
Code the coin experiment, with M coins and coin i coming up 1 with
probability 1/i. Use 100000 samples of this experiment and compute the
average number of 1's. See how it grows with M.
Code the same experiment as above, with say M=100, but now the probability
of coin i coming up 1 being 1/i2. See how the expected number of 1's is
bounded by 2!
Rewrite the proof that the expected number of 1's (in the above case) must be bounded by 2.
Code one sample of a simple random walk up to time n=N and plot
Sn/n1/2 as a function of n. See how, even though it is supposed to blow
up, you will never see that it increases too much, with even the largest
N your software can handle! The reason for this is that this quantity
oscillates between (2 log log n)1/2 and -(2 log log n)1/2, which grows
incredibly slowly! Compute this value for the largest n that matlab takes
and see for yourself.
Code M samples of a simple random walk up to time n=N. Plot the histogram
of Sn/n1/2
after having normalized it by M (use hist(S(:,N)/sqrt(N))/M). Plot these
histograms on the same figure (but with different colors),
for n=10,100,1000, and 10000. Then plot the pdf of a standard normal, again on
the same figure. Do you see what the central limit is saying?
Think well about your codes and then explain, in your own words, how the above two facts do not contradict.
(That Sn/n1/2 blows up as n grows, but its histogram
looks like the one of a standard normal as n grows.)
September 11: We saw the different types of convergence (L
p, in probability, and almost-surely) and looked at an example that showed
how convergence in probability
does not imply almost-sure convergence. We also saw that if
the convergence in probability happens fast enough, then it does imply
the almost-sure convergence. I also explained how this would prove the
strong law of large numbers for a simple symmetric random walk. Nate will
now prove that P(|S
n/n|>ε) does converge to 0 "fast enough",
for any positive ε,
which will prove that S
n/n converges to 0 almost-surely.
September 9: Nate covered lecture 1 of these notes.
Here is a link
to a visualization of the central limit theorem, using the Galton board.
Week 2 homework:
Do more exercises from the notes and check your
answers with simulations.
Prove the properties of a probability measure
that I mentioned in class are satisfied.
Find a counterexample
of three sets that are pair-wise independent but not totally independent.
Check out the exercises at this and
this websites. They will
hopefully help clarify things about what random variables are.
These lecture notes may also help clarifying many things.
September 4: We introduced what a probability means (on a finite or
countable space), looked at its properties, introduced random variables,
functions of them, distributions, expected values, and what it means
to be identically distributed. We derived the Bayes rule for the uniform
distribution on a finite state space and used it to define independence of
events (under an arbitrary probability measure) and independence of random
variables (in both cases, both pair-wise and total independence were
discussed).
September 1: We continued with the notes.
August 28: We talked about simulations and got introduced to matlab. Now you can check your answers by simulating the experiments!
August 26: We started with
these nice notes on combinatorial probability.
Do as many exercises as you can!
