Simple Random Walk on a Graph

The objective of these exercises is to study a random walk on a small graph through a combination of simulations and analysis using R. Please email your completed work as a pdf knit from your updated R markdown file, to tleise@amherst.edu.

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,

\[\mathbb{P}\{X_{n+1}=A\,|\ X_n=D\}=1/2\] \[\mathbb{P}\{X_{n+1}=C\,|\ X_n=A\}=1/3\] \[\mathbb{P}\{X_{n+1}=B\,|\ X_n=D\}=0\]

Determine the transition matrix \(\mathbf{P}\) for this Markov chain with states \(\{A,B,C,D,E\}\).

P <- matrix(0,5,5)
rownames(P)<-c('A','B','C','D','E')
colnames(P)<-c('A','B','C','D','E')
P

##   A B C D E
## A 0 0 0 0 0
## B 0 0 0 0 0
## C 0 0 0 0 0
## D 0 0 0 0 0
## E 0 0 0 0 0

Analysis of the Markov chain

1. Calculate the invariant probability vector \(\bar{\pi}\). 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 \(\mathbf{Q}\) and \(\mathbf{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\)?