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\)

- Consider the following

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\).

```
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`

- Version: 02 December 2023
- Source