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

Question

I am a biologist and apply for a job for which I need to resolve this issue. This is an open book test where the Internet and any other resources are fair play. Here is the question - I was fixated on how to approach it and the pointers will be appreciated. My intuition is located below.

Background

Your neighbor is a farmer with two cows, Clarabel and Bernadette. Each cow has its own square handle, which is 11 meters high (see. First picture). The farmer travels from the city and plans to leave the cows in their pens, which are completely filled with grass. Cows start at the center of the feather and slowly move around the feather, eating grass. They move around the pen very slowly, always stopping to eat or relax after each step. If you divide the feather into 1 m of squares, cows can move one square in any direction at each step (for example, on a chessboard), as shown in the second figure.

After each turn, the cow will spend 20 minutes on a new square grass, if available. As soon as the grass in the square is eaten, it disappears forever. If the cow moves to the square, the grass of which has already been eaten, then the cow will spend 20 minutes of rest in this square. After 20 minutes, resting or eating, the cow moves to another square. If the cow is in the square next to the fence, she will never try to move towards the fence. Cows never remain in the same area twice in a row - they always move to another after resting or eating. The first image shows an example of how a pen might look after a few hours, with brown spots indicating the squares that were grazed.

The first cow, Clarabel, has nothing to do with the direction when she moves. She is equally inclined to move in any direction at any time. Let p be the probability that it moves in the direction as shown in the first figure below.

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

Questions

• If the farmer returns after 48 hours, what percentage of grass in her pen do you expect Clarabelle to eat?
• How long do you expect Bernadette to eat 50% of the grass in her pen?
• Suppose that if one of the cows leaves for 24 hours without food, she will die. Is the cow expected to survive longer?

My intuition

This seems to model a random walk through a two-dimensional grid. I can, for example, find out the probability that on 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 when it passes. Would get acquainted with any information.

Edit: The ultimate goal here would be to write some kind of program for this. This is not a purely mathematical question, and therefore the message here.

Answer 1

Here is a way to calculate probabilities (for Clarabelle):

• Start with grid 0 , except for 1 in cell (6, 6) , this is your probability grid for time t = 0 .

• At time t + 1 probability p(x, y, t + 1) be on the cell (x, y) is defined as follows: p(x, y, t + 1) = p1 * p(x + 1, y, t) + p2 * p(x + 1, y - 1, t) + ... (you have eight members in total).

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

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

If you want to know the probability that the cell has already been eaten, just 1 - Pn , where Pn , if the probability that the cell has not been visited is:

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

Here is the code that calculates this probability using numpy in Python (basically it considers the Markov chain , where state X is the set of all cells | X | = 121, and the transition matrix is ​​T = {T _ij }, where T _ij is the probability of transition 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 complicated, because your p1, p2, ... is 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 approaches to solving such problems: analytically or using modeling.

If you simulate a process using the Monte Carlo method, you can easily find the answers by averaging the results of many runs.

I would suggest that this is what you expect to do, unless you are guided otherwise.