Tuesday, April 27, 2010

Problems 004

One-dimensional drunkard's walk:

Starting from Point X, you stumble discretely east (probability 1/2) and west (probability 1/2) and repeat, indefinitely. Successive stumbles are unrelated, i.e., the former does not in any way predict the latter (nor vice versa). In the long run, what is the average number of stumbles that will bring you back to Point X.

1 comment:

1. The number of ways to get back to point X for the first time in exactly 2*n stumbles is 2*C(n-1), where C(n) is the nth Catalan number. We can first take one stumble to the east, then there are C(n-1) ways of stumbling 2(n-1) times without getting back to X (for example, by bijection to the number of strings of matching parentheses of length 2(n-1)), and then take a final stumble to the west; plus the mirror images where we stumble first to the west.

Thus, the probability of it taking exactly 2*n stumbles is 2*C(n-1)/2^(2*n), and thus the expected number of stumbles is the sum from n=1 to infinity of 4*n*C(n-1)/4^n. However, C(n) is on the order of pi^(-1/2)*4^n/n^(3/2), so that expression is on the order of 1/(n*pi)^(1/2), so the sum diverges.

The expected value is infinite.