-1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Care to explain the down vote on a question not active for weeks? $\endgroup$ – WaveX Jul 31 '18 at 2:00
1
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Very nice, exactly what I was looking for. +1 and I'm happy to see that the variances are high, as I was expecting them to be from a few trials of my own. $\endgroup$ – WaveX May 23 '18 at 5:43
  • $\begingroup$ I'm no expert on Sage syntax, but I am able to tell that it is simulating the experiment over and over and finding sample variances with a large sample, and then we can compare these point estimates to the population variances. $\endgroup$ – WaveX May 23 '18 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.