Interesting Math Problem

Interesting Math Problem

Math Problems Home | Home | Send Feedback

Random(ish) walk on a square

Consider the square ABCD shown at left. A "walker" starts at A, and walks to B. Then, at each corner, he decides, with 3/4 probability, to continue in the same direction (clockwise or counter-clockwise), and with 1/4 probability, he goes the other way.
The problem then is:
a) What are the probabilities of the various path lengths which return to A?
b) What is the expected path length which returns to A?

We can start by looking at various short paths, and computing their probabilities:

Length ... Path ... Probability:
 2 ABA 1/4

 4 ABCBA 9/64
 4 ABCDA 27/64 ... subtotal: 36/64 = 9/4^2

 6 ABCBCBA 9/1024
 6 ABCBCDA 27/1024
 6 ABCDCDA 27/1024
 6 ABCDCBA 81/1024 ... subtotal 144/1024=9*16/4^5 = 9/4^3

 8 ABCBCBCBA 9/16384
 8 ABCBCDCDA 27/16384
 8 ABCBCBCDA 27/16384
 8 ABCDCDCDA 27/16384
 8 ABCBCDCBA 81/16384
 8 ABCDCBCBA 81/16384
 8 ABCDCDCBA 81/16384
 8 ABCDCBCDA 243/16384 ... subtotal 576/16384 = 9*64/4^7 = 9/4^4

10 16 paths ... subtotal 2304/262144
12 32 paths ... subtotal 9216/4194304
14 64 paths ... subtotal 36864/67108864

Continuing in the same fashion, we have:
For path length 2n, 2^(n-1) paths, and total probability of 9/4^n.

The infinite sum of all those probabilities, after the first, is
9 * (1/16 / (1-1/4)) = 9 * 1/16 * 4/3 = 3/4,
which when added to the 1/4 of the first term = 1, covering all possibilities.

Expected path length is
(1/4 * 2) + (4 * 9/16) + (6 * 9/64) + (8 * 9/256) + (10 * 9/1024) + ... =
1/2 + 2 1/4 + 54/64 + 72/256 + 90/1024 + ... =
2 3/4 + a series that adds up to 1 1/4 = 4.
(Sorry, I don't have a proof for that last bit.)

Probability of a path length > 4 = 1 - P(path length 2) - P(path length 4) = 1 - 1/4 - 9/16 = 3/16.

Having done all that, Eric Hart has provided a much simpler solution:

Let A' = expected path length of a path that starts AB and ends at A.
Let C' = expected path length of a path that starts at C and ends at A.

Starting with path AB, you then move back to A (probability 1/4),
and have a path length of 2, or you move on to C (probability 3/4),
and then have a path of length 2 + C'.

On average then, path length starting at A =
2 * 1/4 + 3/4 (C'+2).

From C you can go to C{B or D}A with probability 3/4 (from B or D),
or C{B or D}{back to C} with probability 1/4 (from B or D).
That makes C' = 3/4 * 2 + 1/4 * (2 + C').

Solving that for C' we get:
C' = 3/2 + 1/2 + C'/4
3/4 C' = 2
C' = 8/3.

Then A' = 1/2 + 3/4 C' = 1/2 + 3/4 * (2 + 8/3) = 1/2 + 3 1/2 = 4.

Links to pages which describe similar, but not identical, problems:
stackexchange.com
blogspot.com