Solution to Problem #3



Erich Friedman of Stetson University found the exact answers to the first two questions, Darryl K. Nester of Bluffton College found exact answers to all four questions, and Ryan Moats of Omaha NE and Philippe Fondanaiche of Paris (France) wrote computer simulations which confirmed Nester's calculations. Here is Darryl Nester's solution:

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.



Back to the Archives
Back to the Math Department Homepage.