Variance for Random Walk On Clock Hands

Question

This is essentially a continuation of the problem Random Walk on Clock Hands, where we are told we are doing a random walk on a clock, and we have a 50:50 chance of either going clockwise one step or counterclockwise one step starting at the position $k \in \{1,2,3,4,5,6,7,8,9,10,11,12\}$ The goal is to reach position $12$.

The original problem shows the expected number of steps needed to reach position $12$. I'm interested in a way to calculate the variance.

Obviously if we start at position $12$ the expected number of steps would equal the variance which would be $0$. Its for the other positions I am unsure about.

I understand the basics about Markov Chains and how the answer for expected value was determined by solving a $13\times13$ system, but I really don't know whereabouts to start to find the variance. I know that one could estimate this value using programming and Monte Carlo Simulation, but I'm looking for a more math-based approach.

Thanks for any help given!

Answer 1

We will use same notation as in random walk on clock hands.

The states are as in the picture:

F                                               F
*---*---*---*---*---*---*---*---*---*---*---*---* 
0   1   2   3   4   5   6   7   8   9  10  11  12

(The end states are final.)

Let $D$ be the set $\{D\}$, and let $\tau_D$ be the first time for the random walk $X=(X_n)$ that a state in $D$ is hit.

We denote by $$ \begin{aligned} t_k &= \text{Mean value of $\tau_D$ conditioned by $X_0=k$} \\ &=\Bbb E[\tau_D|X_0=k]\ , \\[6mm] u_k &= \text{Mean value of $\tau_D^2$ conditioned by $X_0=k$} \\ &=\Bbb E[\tau_D^2|X_0=k]\ . \end{aligned} $$ Then we have $\tau_D=0$ exactly on $X_0\in \{0,12\}$.

Else, $\tau_D\ge 1$, and we can write:

$$ \begin{aligned} t_k &=\Bbb E[\tau_D|X_0=k] \\ &= \frac 12\Bbb E[\tau_D|X_0=k\text{ and }X_1=k-1] + \frac 12\Bbb E[\tau_D|X_0=k\text{ and }X_1=k+1] \\ &= \frac 12\Bbb E[1+\tau_D|X_1=k-1] + \frac 12\Bbb E[1+\tau_D|X_1=k+1] \\ &=\frac 12+\frac 12t_{k-1}+\frac 12+\frac 12t_{k+1} \\ &=1+\frac 12(t_{k-1}+t_{k+1})\ , \\[8mm] u_k &=\Bbb E[\tau_D^2|X_0=k] \\ &= \frac 12\Bbb E[\tau_D^2|X_0=k\text{ and }X_1=k-1] + \frac 12\Bbb E[\tau_D^2|X_0=k\text{ and }X_1=k+1] \\ &= \frac 12\Bbb E[(1+\tau_D)^2|X_1=k-1] + \frac 12\Bbb E[(1+\tau_D)^2|X_1=k+1] \\ &= \frac 12\Bbb E[1+2\tau_D+\tau_D^2|X_1=k-1] + \frac 12\Bbb E[1+2\tau_D+\tau_D^2|X_1=k+1] \\ &= \frac 12+\frac 12\cdot 2t_{k-1}+\frac 12 u_{k-1} + \frac 12+\frac 12\cdot 2t_{k+1}+\frac 12 u_{k+1} \\ &=1 +(t_{k-1}+t_{k+1}) +\frac 12(u_{k-1}+u_{k+1}) \ . \end{aligned} $$ We already have the solution for $(t_k)_{0\le k\le 12}$, the formula is at loc. cit. $$t_k=k(12-k)\ .$$ (We expect a symmetry w.r.t. $k\leftrightarrow 12-k$.)

The system for $(u_k)_{0\le k\le 12}$ can be solved by computer in this century, sage for instance:

u = var( 'u0,u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11,u12' )
def t(k):    return k*(12-k)

eqs = [ u[0] == 0, u[12] == 0 ]
for k in [1..11]:
    eqs.append( u[k] == 1 + (u[k-1] + u[k+1]) / 2 + t(k-1) + t(k+1)
solve( eqs, u )

Results (with a manual split):

[[u0 == 0, u1 == 561, u2 == 1080, u3 == 1521, u4 == 1856, u5 == 2065,
  u6 == 2136,
  u7 == 2065, u8 == 1856, u9 == 1521, u10 == 1080, u11 == 561, u12 == 0]]

After i calculated some divided differences, there was a good sign that an interpolation with a polynomial of degree $4$ is possible, we have two roots, so...

sage: var( 'a,b,c' );
sage: def P(k): return k*(12-k)*(a*k^2+b*k+c) 
sage: solve( [ P(1)==561, P(2)==1080, P(3)==1521 ], [a,b,c] )
[[a == (-1/3), b == 4, c == (142/3)]]

This leads to the formula $$ P(k) = \frac 13k(12-k)\Big(\ 142+k(12-k)\ \Big)\ . $$ Check:

sage: P(k) = k*(12-k)*( 142+k*(12-k) )/3
sage: [ P(k) for k in [0..12] ]
[0, 561, 1080, 1521, 1856, 2065, 2136, 2065, 1856, 1521, 1080, 561, 0]

recovering the solution.

The corresponding variances are: $$ \boxed{\qquad u_k-t_k^2= \frac 23\, k(12-k)\Big(\ 71-k(12-k)\ )\ . \qquad} $$ These values are:

[0, 440, 680, 792, 832, 840, 840, 840, 832, 792, 680, 440, 0]

---

Simulation, sage again:

R = Zmod(12)
choices = [ R(-1), R(+1) ]
import random

def tau(start):
    n = 0
    position = start
    while position != R(0):
        position += random.choice( choices )
        n += 1
    return n

N = 10**6    # trials
Moment1_SUM = [ 0. for r in R ]    # so far 
Moment2_SUM = [ 0. for r in R ]    # so far 
Var         = [ 0. for r in R ]    # so far 

for k in [0..11]:
    print "k = %s" % k

    for n in xrange(N):
        t = tau( R(k) )
        Moment1_SUM[k] += t
        Moment2_SUM[k] += t^2

    Moment1_SUM[k] /= N
    Moment2_SUM[k] /= N
    Var[k] = Moment2_SUM[k] - Moment1_SUM[k]^2

print "1.st moments ~ %s (statistically)" % [ '%.2f' % s for s in Moment1_SUM ]
print "2.nd moments ~ %s (statistically)" % [ '%.2f' % s for s in Moment2_SUM ]
print "Variances    ~ %s (statistically)" % [ '%.2f' % s for s in Var         ]

Results this time:

1.st moments ~ ['0.00', '10.98', '20.01', '26.98', '32.03', '34.98', '36.01', '35.04', '32.02', '26.98', '20.00', '11.01'] (statistically)
2.nd moments ~ ['0.00', '559.11', '1081.61', '1520.62', '1858.41', '2062.27', '2137.60', '2069.82', '1858.17', '1518.16', '1077.71', '562.67'] (statistically)
Variances    ~ ['0.00', '438.47', '681.06', '792.82', '832.28', '838.41', '840.76', '841.84', '832.92', '790.44', '677.81', '441.46'] (statistically)