text: # Variance for Random Walk On Clock Hands
  
  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!
  
  • Care to explain the down vote on a question not active for weeks? – WaveX Jul 31 '18 at 2:00
  
  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)
  
  • 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. – WaveX May 23 '18 at 5:43
  • 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. – WaveX May 23 '18 at 6:19