Home > Mathematica, Mathematics > Ants on a Grid

## Ants on a Grid

The New York Times Number play puzzle about ants on a grid provided the opportunity to play with the `DiscreteMarkovProcess` function in Mathematica.

The puzzle:

An ant is sitting on an 8×8 2-D grid board — in other words, a board with eight vertical grid lines and eight horizontal grid lines. The ant is initially at the intersection of the third horizontal line and fifth vertical line. The ant moves to an adjacent intersection along the grid lines, being equally likely to move in any one of the four directions (up, down, left, right).

If the ant reaches a horizontal boundary, it survives; if the ant reaches a vertical boundary, it dies.

What is the probability the ant survives?

My approach:
Code the grid. The prob variable codes the degree of each node. Nodes of degree 2 are the corners. Nodes of degree 3 are boundaries (either death or survival), the remaining nodes are inside.
``` set = Flatten[Table[{i, j}, {i, 8}, {j, 8}], 1]; rules = MapThread[Rule, {set, Range[64]}]; tup = Drop[Tuples[{0, 1}, 2], -1]; ectab = Table[Union[# + j & /@ tup, j - # & /@ tup], {j,set}]; prob = (Length@Intersection[set, #] & /@ ectab) - 1; classes = Intersection[set, #] & /@ ectab; ```
Code the aborbing and non-absorbing states:
``` never = {1, 8, 57, 64}; surv = Union[Range[2, 7], Range[58, 63]]; death = Union[Range[9, 49, 8], Range[16, 56, 8]]; inside = Flatten[Position[prob, 4]]; ```
Build the transition matrix:
``` f[u_] := {u[[3]], #} -> 0.25 & /@ Drop[u, {3}] /. rules f[ectab[[4]]] in = Flatten[Table[f[ectab[[j]]], {j, inside}], 1]; absorb = # -> 1 & /@ Union[ Thread[{surv, surv}], Thread[{never, never}], Thread[{death, death}]]; markov = SparseArray[Union[absorb, in]] ```
Write functions to calculate the stationary distribution for starting node:
``` sf[u_] := Module[{s, d}, s = ReplacePart[ConstantArray[0, {64}], (u /. rules) -> 1]; StationaryDistribution@DiscreteMarkovProcess[s, markov]]; survf[u_] := Probability[Or @@ (x == # & /@ surv), x \[Distributed] sf[u]] ```

The probability of survival starting at (3,5) is `survf[{3,5}] is 17/29 approximately 0.586207.`

The underlying graph is shown below:

The symmetries are illustrated in the bar chart, The plane is at probability 0,5: