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:

nytmarkov01

 

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

nytmarkov02

 

Advertisements
Categories: Mathematica, Mathematics
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: