What is the area covered by a Random walk in a 2D grid?

Question

I am a biologist and applying for a job, for which I need to solve this question. It is an open book test, where the internet and any other resources are fair game. Here's the question - I'm stuck on how to approach it and would appreciate pointers. My intuition is posted underneath.

Background

Your neighbor is a farmer with two cows, Clarabelle and Bernadette. Each cow has its own square pen that is 11m on a side (see first figure). The farmer is heading out of town for a trip and plans to leave the cows in their respective pens, which are completely filled with grass to start. The cows begin in the center of the pen, and will slowly move around the pen eating the grass. They move around the pen very slowly, always pausing to eat or rest after every step. If you divide the pen into 1m squares, the cows can move one square in any direction each step (like a king on a chess board), as shown in the second figure.

After each move, the cow will spend 20 minutes in the new square eating grass, if it is available. Once the grass in a square is eaten, it is gone forever. If the cow moves to a square whose grass was already eaten, then the cow will spend 20 minutes resting in that square. After 20 minutes, whether resting or eating, the cow moves to another square. If a cow is in a square adjacent to the fence, she will never try to move in the direction of the fence. The cows never stay in the same square twice in a row -- they always move to a different one after resting or eating. The first figure shows an example of what a pen might look like after some hours, with the brown spots indicating squares that have been grazed.

The first cow, Clarabelle, has no preference for direction when she moves. She is equally likely to move in any direction at all times. Let p be the probability that she moves in a direction, as shown in the first figure below.

The second cow, Bernadette, prefers to move towards squares with grass. She is twice as likely to move towards a space that has grass as she is towards a space that she has already eaten, as shown in the second figure below.

Questions

• If the farmer returns after 48 hours, what percentage of the grass in her pen do you expect Clarabelle to have eaten?
• How long do you expect it will take for Bernadette to eat 50% of the grass in her pen?
• Suppose that if either of the cows go 24 hours without eating any grass, she will die. Which cow is expected to survive longer?

My intuition

This appears to be modeling a random walk through a 2 dimensional grid. I can for instance figure out the probability of being at a particular node in the grid, after a given time. But I'm not sure how to think about the area covered by the cow as it walks through. Would appreciate any insights.

Edit: The final aim here would be for me to write some sort of a program for this. This isn't a purely mathematics question and thus the post here.

Answer 1

Here is a way of computing the probabilities (for Clarabelle):

1. Start with a grid of 0, except 1 on the (6, 6) cell, this is your probability grid for time t = 0.

2. At time t + 1, the probability p(x, y, t + 1) of being on cell (x, y) is given by: p(x, y, t + 1) = p1 * p(x + 1, y, t) + p2 * p(x + 1, y - 1, t) + ... (you have eight term in the sum).

Note that all the pi are not equals: the probability can be 1/3 (corner), 1/5 (edge), or 1/8 (any other cell).

You can dynamically update your grid by running this for each step t = 0 to t = 144 (48h).

If you want to know the probability for a cell already been eaten, it is simply 1 - Pn where Pn if the probability of the cell never been visited, which is:

(1 - p(x, y, 0)) * (1 - p(x, y, 1)) * (1 - p(x, y, 2)) * ...

Here is a code that compute these probability using numpy in Python (basically, this is considering a Markov Chain where the state X is the set of all cells |X| = 121, and the transition matrix T = {T_ij} where T_ij is the probability of moving from i to j):

GridSize = 11
TranSize = GridSize * GridSize
T_Matrix = np.zeros((TranSize, TranSize), dtype = float)

for u in range(T_Matrix.shape[0]):
    for v in range(T_Matrix.shape[1]):
        ux, uy = u % GridSize, u // GridSize
        vx, vy = v % GridSize, v // GridSize
        if u == v or abs(ux - vx) > 1 or abs(uy - vy) > 1:
            p = 0
        elif (ux == 0 or ux == 10) and (uy == 0 or uy == 10):
            p = 1/3
        elif ux == 0 or ux == 10 or uy == 10 or uy == 0:
            p = 0.2
        else:
            p = 0.125
        T_Matrix[u, v] = p

pxy = np.zeros((TranSize, ), dtype = float)
pxy[11 * 5 + 5] = 1
eat = 1 - pxy

for _ in range(144):
    pxy = pxy.dot(T_Matrix)
    eat *= (1 - pxy)

print((1 - eat).reshape((GridSize, GridSize)))

The algorithm for Bernadette is a bit more complex because your p1, p2, ... are probabilistic, so you get two terms for each adjacent cell.

Once you have all these probabilities, you can easily find what you want.

Answer 2

There are two ways to approach such problems: analytically or via simulation.

If you'll simulate the process using a Monte-Carlo based method, you can easily find the answers by averaging the results of many trails.

I would assume that this is what you're expected to do, unless you were guided otherwise.