Anthill Problem

Problem Description

• An ant leaves home (anthill located at 0,0) in search of food. It can move horizontally or vertically +1, -1 coordinate at a time

• Food is located in a rectangular perimeter surrounding the anthill at a distance of 2 coordinate points away

• The ant explores the space at random, (meaning it will take a step in any direction at any point according to a discrete uniform probability distribution) · We’d like to know, on average, how many steps will it take on until the ant reaches food ?

Approach:

• We can set up the problem as a Discrete Time Markov Chain, a nice approach since it allows us to reduce complexity and focus only on essential information

• There are four states of interest here: (a) anthill (origin point) (b) edge point (c) corner point and (d) food point

• The next state is only determined by the present state, we require no information from the past

• The four states are determined by the geometry of the boundary chosen, but once we have this state space representation, we can write down a transition matrix, which contains everything we need to solve

Solution:

• This DTMC is irreducible and positive recurrent, meaning there exists a unique stationary distribution. The stationary distribution tells us information about a full cycle between states in the chain. In this case we are not interested in a full cycle, rather a path from state 0 to state 4

• One step equations give a simple linear system that can be solved

• Matrix form: (I-Q)^-1 we can simply input this into a matrix inverter and have our solution immediately *

• Verification : We can quickly verify a small finite example like this using simulation · Python Code included at the end

Generalizations:

• If we were to use a circular/generalized closed boundary (iterative search)

• If we were to change the dimensions of the rectangle

• Ant finds food and returns home (thus completing a full cycle, but must go through the food state)

• Higher dimensional search space

Simulation Code :

import numpy as np

import random

import matplotlib.pyplot as plt

P = np.array([[0, 1, 0, 0], [.25, 0, .5, .25], [0, .5, 0, .5], [0, 0, 0, 1]])

def main():

dist = []

for i in range(0, 500):

dist.append(sample())

plt.hist(dist)

plt.show()

def sample(n=1000):

trials , Sn = 0, 0

while trials < n:

Sn += simulate()

trials += 1

return Sn/n

def step(i , P ):

next_states = np.where(P[i,:] > 0)[0]

state_dist = P[i,:][next_states]

cumul = np.cumsum(state_dist)

rand = random.uniform(0,1)

for i in range(0, len(next_states)):

if rand <= cumul[i]:

return next_states[i]

def simulate():

count, state = 0, 0

while state != 3:

newState = step(state, P)

count += 1

state = newState

return count

main()