Solution to Problem #3

The three questions were:
1. Is the ant more likely to exit through point A or point B?
ANSWER: Point A (barely). The ant will exit at A with probability 61/121, and
at B with probability 60/121.  (Work for all problems is given below.)

2. On average, how long will it take the ant to exit the grid (either
through point A or point B)?
ANSWER: The expected number of steps before hitting A or B is 349/35=9.971....

3. If the ant is prohibited from immediately doubling back on its path, how
does this affect the answers to the two previous questions?
ANSWER: The ant is still more likely to exit at point A (477/908 vs.
431/908).  The average number of steps decreases to 344/57=6.035....

Work:  Let us number the vertices of the grid 1,2,3, ...,12, starting in
the upper left corner (so that vertex 3 = B, vertex 9 = X, and vertex 10 =
A).

1. Let a_k = P[exit at B | start at vertex k].  Note that a3=1 and a10=0,
and in general, a_k = 1-a_(13-k).  Thus it suffices to determine a1, a2,
..., a6.
We do this with the equations
   a1 = (a2+a4)/2
   a2 = (a1+a3+a5)/3
   a3 = 1
   a4 = (a1+a5+(1-a6))/3
   a5 = (a2+a4+a6+(1-a5))/4
   a6 = (a3+a5+(1-a4))/3
This system is easily solved (esp. if you a TI-92 or some other CAS
available) and yields
   (a1,a2,a3,a4,a5,a6) = (75/121, 89/121, 1, 61/121, 71/121, 84/121)
With a9 = 1-a4, we have the answer noted above (as well as some other
information).

2.  Let t_k be the expected number of steps before exiting the grid, when
starting at vertex k.  Now t1=t12, t2=t11, t3=t10=0, etc.  We solve for t1,
t2, ..., t6 using the system:
   t1 = 1+ (t2+t4)/2
   t2 = 1+ (t1+t3+t5)/3
   t3 = 0
   t4 = 1+ (t1+t5+t7)/3    = 1+ (t1+t5+t6)/3
   t5 = 1+ (t2+t4+t6+t8)/4 = 1+ (t2+t4+t6+t5)/4
   t6 = 1+ (t3+t5+t9)/3    = 1+ (t3+t5+t4)/3
which yields
   (t1,t2,t3,t4,t5,t6) = (68/7, 261/35, 0, 349/35, 338/35, 264/35)
Recalling that t9 = t4 gives the answer noted above.

3.  When doubling back is not allowed, the random walk is not a Markov
process anymore, but by considering ordered pairs of vertices (i,j) to mean
"the ant travels from vertex i to vertex j," we see that we have a Markov
process when we consider transitions from (i,j) to (j,k), where i is not
equal to k.

If a_ij = P[exit at B | start with (i,j)], then we have
  a12 = (a25 + a23)/2
  a14 = (a45 + a47)/2
etc.  Note that a21=a14, a23=a63=1, and a41=a12.  Here is the matrix for
the resulting system (copied from Mathematica input); confirmation of the
entries in this matrix is left as an exercise :-)

  ant3={
  { 2, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0},
  { 0, 2, 0,-1,-1, 0, 0, 0, 0, 0, 0},
  { 0, 0, 3, 0, 0, 0,-1,-1,-1, 0, 0},
  { 0, 0, 0, 3, 0,-1, 0,-1,-1, 0, 0},
  { 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0},
  { 0,-1, 0, 0, 0, 2, 0, 0, 0, 0, 0},
  {-1, 0, 0, 0,-1, 0, 2, 0, 0, 0, 0},
  { 0, 0, 0, 0, 0, 0, 0, 2, 0, 0,-1},
  { 0, 0, 0, 0, 0, 1, 1, 1, 3, 0, 0},
  { 0, 0, 0, 0, 0,-1,-1, 0,-1, 3, 0},
  { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2}};

To solve the system we enter:
  {1,0,0,0,1,1,0,1,3,0,2} . Transpose[Inverse[ant3]]
This gives as output:
   687  93   233  529  215  160  451  151  343  239  75
  {---, ---, ---, ---, ---, ---, ---, ---, ---, ---, ---}
   908  227  454  908  908  227  908  227  908  454  227
which are the values of
  {a12, a14, a25, a45, a47, a52, a54, a56, a58, a65, a69}.

Now
   P[exit at A | start at vertex 9] = P[exit at B | start at vertex 4]
which equals
   (a41 + a45 + a47)/3 = (a12 + a45 + a47)/3 = 477/908.

For the exit time, let t_ij be the expected number of steps to exit,
starting with (i,j) --- including that first step from i to j.  Then
t23=t63=1, t21=1+t14, and t41=1+t12.  We then have the system:
  t12 = 1 + (t25 + t23)/2 = 1 + (t25 + 1)/2
  t14 = 1 + (t45 + t47)/2
etc., which leads to the matrix
  ant4={
  { 2, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0},
  { 0, 2, 0,-1,-1, 0, 0, 0, 0, 0, 0},
  { 0, 0, 3, 0, 0, 0,-1,-1,-1, 0, 0},
  { 0, 0, 0, 3, 0,-1, 0,-1,-1, 0, 0},
  { 0, 0, 0, 0, 2, 0, 0, 0, 0,-1, 0},
  { 0,-1, 0, 0, 0, 2, 0, 0, 0, 0, 0},
  {-1, 0, 0, 0,-1, 0, 2, 0, 0, 0, 0},
  { 0, 0, 0, 0, 0, 0, 0, 2, 0, 0,-1},
  { 0, 0, 0, 0, 0,-1,-1,-1, 3, 0, 0},
  { 0, 0, 0, 0, 0,-1,-1, 0,-1, 3, 0},
  {-1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 2}};

(Note this is the same as the previous matrix except that all off-diagonal
entries are negative.) To solve the system we enter:
  {3,2,3,3,3,4,3,3,3,3,3} . Transpose[Inverse[ant4]]
which gives as output:
   1796  2621  2718  111  1815  1966  107  1852  110  2756  2830
  {----, ----, ----, ---, ----, ----, ---, ----, ---, ----, ----}
   437   437   437   19   437   437   19   437   19   437   437
which are the values of
  {t12, t14, t25, t45, t47, t52, t54, t56, t58, t65, t69}.

Finally we note that
   Exp. # of steps starting at 9 = Exp. # of steps starting at 4
which equals
   (t41 + t45 + t47)/3 = (1+t12 + t45 + t47)/3 = 344/57.