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.

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.

ReplyDeleteThus, 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.