University:
Amherst College
Course:
MATH 365 | Stochastic Processes
Academic year:

2014
Views:

429

Pages:

2
Author:

ice0ver13toy

Math 365 Simple Random Walk on a Graph The objective of this lab is to study a random walk on a small graph through a combination of simulations and analysis using R. Please email your R script with answers to the exercises included as comments to tleise@amherst.edu. 1 Problem set-up Consider the simple random walk on the graph shown below. We define a Markov chain which moves from vertex to vertex by randomly following an edge to an adjacent vertex. For example, P{Xn+1 = A|Xn = D} = 1/2, P{Xn+1 = C|Xn = A} = 1/3 and P{Xn+1 = B|Xn = D} = 0. A B C D E Determine the transition matrix P for this Markov chain with states {A, B, C, D, E}. 2 Analysis of the Markov chain 1. Calculate the invariant probability vector π̄. In the long run, about what fraction of the time is spent at vertex A? 2. Suppose the random walk begins at vertex A. What is the expected number of steps until the walk returns to A? We can use simulations to generate the distribution of return times, as the expected value doesn’t tell the full story. First define a function that can randomly step from vertex to vertex: takestep <- function(x) { switch(x, sample(c(2,3,4),1), #A sample(c(1,3,5),1), #B sample(c(1,2),1), #C sample(c(1,5),1), #D sample(c(2,4),1)) #E } Next define a function that finds the return time to a desired vertex for each simulation: waitingtime <- function(vertex) { x <- vertex for (j in 1:10000) { x <- takestep(x) ifelse(x==vertex, return(j),-1) # takes steps until hits vertex again } } Run many simulations and plot a histogram of the return times: nsims <- 100000 sims <- matrix(0,nsims) for (k in 1:nsims) sims[k] <- waitingtime(1) # vertex A hist(sims,(min(sims)-1):(max(sims)+1),freq=FALSE, xlab="Number of steps",xlim=c(0,20), main=paste("Mean first return time is",mean(sims))) 3. Suppose the random walk begins at vertex C. What is the expected number of steps until the walker reaches A? Hint: Make A an absorbing state, then calculate matrices Q and M. 4. Suppose the random walk begins at vertex C. What is the expected number of visits to B before the walker reaches A? 5. Suppose the random walk begins at vertex B. What is the probability that the walker reaches A before C?

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock