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.