Bidimensional Bounded Random Walk

[actcs]

A grid of 4x4 is given
.__.__.__.__.
| | | | |
.__.__.__.__.
| | | | |
.__.__o__.__.
| | | | |
.__.__.__.__.
| | | | |
.__.__.__.__.

A ball is located at the center of the grid which is to perform a 5 step random walk with equal probability in any direction.

If it touches the grid's edges it'll stop

I need to find the probability of the event in which the ball stays in the inner 3x3 grid (that's to say, it never touches the grid's edges)

---What I've already done:

I was told to use the multinomial distribution, however I found that some cases doesn't even exist (e.g: When I tried to find the probability (using a multinomial distribution) in which the ball moves 2 steps down and 3 steps up, I realized that it was impossible because it cannot give the three up steps first), also I realized that the ball can never touch the corners

Instead of that I did a kind of tree to help me to work out how many 5 step walks were posible in which the ball remained at the inner 3x3 grid. I found out that that number is 1296

But in order to work out how many walks are posible in which the ball stays at the grid's edges, it must be considered that there are from 2 step to 5 step walks

I mean, is there any "easier" way of working out this rather than doing an exhaustive analysis?

 

[Adeimantus]

1296 seems a little high for the number of paths that stay inside the inner 3x3 grid, since the total number of 5 step random walks is 4^5 = 2^10 = 1024. If you are able to count the number of random walks that stay inside the inner 3x3 grid, you would just divide that number by 1024 to get the probability. But I can't think of an easy way of counting how many stay inside the inner 3x3 grid. The only way I can think of involves computing the 5th power of a 9x9 matrix (not as bad as it sounds, actually) and then adding up the elements of one of the rows. Number the nine points in the inner 3x3 grid 1-9, and then create a matrix where entry (i,j) is a 1 if point i and point j are exactly one step apart, and 0 if they are not. Call this 9x9 matrix A. Then entry (i,j) of A^n is the number of ways you can reach point j in n steps starting from point i, all the while staying within the 3x3 inner grid. There is a certain way of numbering the points that makes the matrix multiplication easier. Try to arrange it so that you have square blocks of zeros in the upper left and lower right of matrix A.

 

[actcs]

Well, you're completely right about the total number of possible random walks, I must have miscalculated. On the other hand, to calculate the probability it isn't just as simple as dividing by 1024 once we have worked out the number of random walks which stay in the inner 3x3 grid, that's because it has to be taken into account the fact that whenever the ball hits the edges it stops, furthermore there are some walks that don't even exist (e.g. up up up down down), so the only thing we can say about the total number of possible random walks is that they are less than 1024. Besides that, I don't understand your point on how to calculate the random walks in which the ball stays in the inner 3x3 grid. Could you please be a little more specific? By the way, thanks for replying

 

[Rogerio]

...
If it touches the grid's edges it'll stop

I need to find the probability of the event in which the ball stays in the inner 3x3 grid (that's to say, it never touches the grid's edges)
...

Let's analyse the allowed sequences:
You may have horizontal (H) and vertical (V) moves.
Considering the horizontal moves:
After the first H move (left or right), the sequence of H moves is determined.
The same applies to the vertical moves.

So, let's say we have 3 H's and 2 V's.
Then, there will be 10 different sequences of H's and V's.
And, for each sequence, the first "H" can be "left" or "right". Similarly, the first "V" can be "up or "down".
So, there are 10*2*2 = 40 real sequences made of 3 horizontal moves and 2 vertical moves.

Then, the number of paths allowed is:
5H and 0V -> 2 * 1
4H and 1V -> 4 * 5
3H and 2V -> 4 * 10
2H and 3V -> 4 * 10
1H and 4V -> 4 * 5
0H and 5V -> 2 * 1

Total = 2 + 20 + 40 + 40 + 20 + 2 = 124

As the probability of each path is (1/4)**5 = 1/1024 , the probability of a "allowed walk" is 124/1024 = 12.1%

 

[Adeimantus]

... On the other hand, to calculate the probability it isn't just as simple as dividing by 1024 once we have worked out the number of random walks which stay in the inner 3x3 grid, that's because it has to be taken into account the fact that whenever the ball hits the edges it stops, furthermore there are some walks that doesn't even exist (e.g. up up up down down), so the only thing we can say about the total number of possible random walks is that they are less than 1024. ...

I see what you are saying about the ball getting "absorbed" by the edges of the 4x4 grid. So not all 1024 random walks are actually possible on the 4x4 grid. But for the purpose of calculating the probability that the ball stays in the inner 3x3 grid, I'm pretty sure it doesn't matter what happens to it once it leaves the 3x3 grid. Imagine you let the ball do two sets of one million random walks. In the first million random walks, there are no absorbing edges: for each random walk, the ball completes a 5 step walk completely unhindered (it is on an infinite grid). In the second set of one million random walks, the edges of the 4x4 grid are an absorbing boundary, so that the ball either goes 5 steps (within the 4x4 grid) or is absorbed before the 5th step. The second experiment corresponds to your problem. The fraction of random walks that leave the inner 3x3 grid is the same in the first experiment as it is in the second experiment. Once the ball leaves the inner 3x3 grid, the random walk is a "failure", and it doesn't matter if the ball is absorbed or completes the 5 steps. So, it seems to me, that you can calculate the probability in your problem by ignoring the 4x4 absorbing grid and simply calculate the fraction of all 5 step random walks that never leave the inner 3x3 grid (the "successes").

The matrix I was talking about is a sort of "transition matrix". There are 9 points or "states" in the inner 3x3 grid. So in the 9x9 matrix A, the element A_ij is the number of ways you can get from state i to state j in exactly one step. Clearly the A_ij are all 1 or 0, depending on whether or not states i and j are exactly one step apart. So if you numbered the states of the inner 3x3 grid as follows

1 2 3
4 5 6
7 8 9

there is one way to get from state 1 to state 2 in one step, but zero ways to get from state 1 to state 5 in one step (it takes at least two steps). So A_12 = 1 and A_15 = 0 in this numbering of the states. Note that the diagonal elements are zero A_ii = 0. If you work out the rest of the A_ij, you will see that most of the elements are 0, and that the 0's do not form nice blocks. It would be convenient if they did. So instead try a numbering such as

x 2 x
3 5 1
x 4 x

You can fill in the x's with 6-9 however you like. Now the matrix A_ij should have most of the 0's grouped into square blocks on the diagonal. This will make computing powers of A easier.

Look at the i-j th element of A^2:

[A^2]_ij = A_i1*A_1j + A_i2*A_2j + ... + A_i9*A_9j

This is the number of ways of getting from state i to state j in exactly 2 steps, using only states in the inner 3x3 grid as intermediates. Generally, [A^n]_ij gives the number of ways of getting from state i to state j in n steps.

This is admittedly a brute force approach. I think Rogerio's approach is more elegant, but it looks to me like he undercounted the sequences that stay inside the 3x3 grid. But I'll have to think about it some more.

 

[Rogerio]

After the first H move (left or right), the sequence of H moves is determined.

In fact, it is not.
So, I have to think about it.

 

[Rogerio]

After the first H move, the next one is forced. But, then, the third H move can be right or left, and so on. So, the H and V moves have to be considered in pairs.
Rewriting the calculations...

Then, the number of paths allowed is:
5H and 0V -> 2 * 1 * 2^2
4H and 1V -> 4 * 5 * 2^1
3H and 2V -> 4 * 10 * 2^1
2H and 3V -> 4 * 10 * 2^1
1H and 4V -> 4 * 5 * 2^1
0H and 5V -> 2 * 1 * 2^2

The total is 8 + 40 + 80 + 80 + 40 + 8 = 256.

So , the probability is 256/1024 = 25%.


(of course this was brute force, too. Once the number of paths is 256, I suspect there is another way much more immediate...)