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.

Flameproof

I'm voting to close this question as off-topic because it appears to be about maths, with no particular programming aspect (try math.stackexchange.com). – Quad

Actually, this is an algorithms question - the final aim is to write a program to compute the probabilities. How is this off topic? – Flameproof

You might be able to get some approximate answers using math, but due to the details an accurate answer probably requires some sort of Monte-Carlo simulation, which requires programming. So +1 and please leave it open from me ... – Cadency

OK, but the problem right now is to figure out the maths, correct? – Quad

@OliverCharlesworth Actually, I think the problem right now is to figure an algorithm to compute the exact probabilities because computing them using only equations would be very complex. See my answer which is clearly a algorithmic approach. – Dualpurpose

@OliverCharlesworth a computer program that simulates the process and aggregates statistics, as I think Lior suggested, seems to me directly about computer programming. Creative solutions like that do not have a chance to appear when you close a question just because YOU believe it is only about math. (Generally, I think SO is about PEOPLE interested in programming — who are quite frequently also interested in math — rather than about programming vs math.) – Kowtko

@גלעדברקן: Sure, that's why it requires 4 other people to agree with me before the question is closed. My feeling in this case is that because there is no specific programming angle, this question would elicit much better/targeted responses in SE site with domain experts (e.g. maths or stats). – Quad

@OliverCharlesworth A question on SO that people are interested in can be an evolving conversation that may or may not develop "specific programming angles." When you close it, you cutoff that creative process between the community of SO users - people who draw from programming and math and other fields. Why close it when people on SO are clearly interested in it? – Kowtko

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.

Dualpurpose

This might work for calculating the probability of Clarabelle being at a certain time and place, you are effectively calculating a transition matrix for a Markov Chain (see the second half of this interesting analysis of a simple game). This will not work for Bernadette, since her movement will depend on previous history. I believe that your formula for a cell already been eaten is wrong, as it is it can become more than one. Should probably be something like pe(x,y,t) = (1 - p(x,y,t)) * pe(x,y,t-1) + p(x,y,t). – Cadency

Also your solution is probably not called dynamic programming, but more calculating a Markov Chain, but your answer is good anyhow. – Cadency

@BasSwinckels As I understand dynamic programming it is one, used to calculate a Markov Chain, it is iteratively computing data to get the final answer. But this is semantic. Concerning pe, I don't really know: I know that with my formula I will get value greater than 1, so this is bad, but your formula is also wrong because if you look at the center cell, the probability will decrease while it should stay 1 (hope I make sense here... ). Concerning Bernadette, I think it will work, see the end of my answer, but not with the same type of Markov Chain of course. – Dualpurpose

@BasSwinckels See my edit for pe, I think this is a right answer: It is 1 - P where P is the probability of having never been there. – Dualpurpose

Yeah, probably something like that, need to distinguish between eating at time t and already eaten at any previous step. I am still convinced this is normally not called a DP solution, since there you typically solve a problem based on smaller sub-problems (similar, but still different from divide and conquer), and you typically use memoization to speed things up. Not every iterative scheme is DP ... – Cadency

@BasSwinckels Yes, with a bit of hindsight, you are probably right this is not DP (the way I programmed it made me things of DP but this is not). – Dualpurpose

Thank you everyone for the answers and the comments. This is really helpful. – Flameproof

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.

Woodenhead