A simple random walk

Random walk on a clock

In this exercise, we will explore and illustrate various key concepts with a simple example. Consider the a random walk on \(5\) states: \(S = \{a,b,c,d,e\}\), which we picture to be positioned on clock, in clockwise order. Consider the following walk, where we start at \(X_0=a\). We a roll a fair dice, and use it to decide to move clockwise to the state \(b\), counterclockwise to the state \(e\), or stay put, all with equal probability; similarly, at each state, we roll a fair independent dice, to determine whether to move forward, back, or stay put. We follow our position on this clock as \(X= (X_0, X_1, X_2, \ldots)\).

We are interested in the following questions:

• For large values of \(n\), what is the law of the single random variable \(X_n\)? Explore by coding.

  • Does it make it difference, if we had started at any other point; that is, if \(X_0=b\), then how does this effect the distribution of \(X_n\), when \(n\) is large? Explore by coding.

• What happens if we start \(X_0\) at a point uniformly at random on \(S\)?

• Consider two independent random walks on the clock \(X\) and \(Y\), where \(X_0=a\) and \(Y_0=b\). Prove that if \(T = \inf\{n \geq 1: X_n=Y_n\}\), then \(\mathbb{P}(T < \infty)=1\). Hint: every \(5\) steps, there is a probability that \(X\) stays put, and \(Y\) goes forward, in which case, they will meet.

  • Consider the following coupling of \(X\) and \(Y\), run them independently until they meet, that is use independent dice to determine their movements, but after they meet, use the same dice, so that there movements are now synchronized: call the coupled random walk \((X', Y')\), and let \(T\) be the first time they meet, and when forever after they are binded. Notice that individually, \(X'\) has the same distribution as \(X\) and \(Y'\) has the same distribution as \(Y\). Now show that for every \(s \in S\), we have \(\lim_{n \to \infty}|\mathbb{P}(X_n' = s) - \mathbb{P}(Y_n'=s)| =0\)

Partial solutions

We will first code the three-sided fair coin from a fair dice. Then we will use the dice and modular arithmetic to code the walk. Specifically, we envision the walk on \(S=\{0,1,2,3,4\}\) and add \(-1,1\) or \(0\) with equal probability, where \(4+1 = 0 \bmod 5\).

Code

three <- function(){
  dice = sample(1:6, 1)
  move = 0
  if(dice <3){move <- 1}
  if(dice > 4){move <- -1}
  move
}
walk <-function(s,n){
  x=s
  current=s
  k=0
  while(k <n+1){
    current <- (current + three()) %% 5
    x <- c(x, current)
    k <-k+1}
  current
    
  }

x = replicate(1000, walk(0,500))
p = c(mean(x==0), mean(x==1),mean(x==2),mean(x==3), mean(x==4) )
p

## [1] 0.196 0.198 0.187 0.208 0.211

x = replicate(1000, walk(1,500))
q = c(mean(x==0), mean(x==1),mean(x==2),mean(x==3), mean(x==4) )
q

## [1] 0.189 0.198 0.207 0.194 0.212

Endnotes

• Version: 02 December 2023
• Source