Suppose I randomly and blindly walk back and forth along this hallway, which may or may not happen in reality. The safest place to start is in the middle, next to the department’s main office. How long will it take before I bump into a wall at one of the ends?
Formally, let be independent random variables which take values with equal probability . These are the steps of the symmetric random walk. Starting from , after steps I end up at the point . The sequence is a martingale, being the sum of independent random variables with zero mean. Less obviously, for every number the sequence is also a martingale, even though the increments are not independent of each other. The reason for is that . It is convenient to write in what follows. We check the martingale property of this by conditioning on some value and computing .
If our hallway is the interval , we should investigate the stopping time . The optional stopping time theorem applies to because whenever . Thus, . In terms of this means .
Now, is either or ; both happen with and in both cases has the same distribution. Therefore, . We end up with the Laplace transform of ,
(I would not want to write in such a formula.) Since N is an integer and , a magical identity applies:
being the Nth Чебышёв polynomial of the first kind. (Compare to which holds for .) Thus,
One more change of notation: let , so that . The formula
gives us the probabilities for each , assuming we can expand the reciprocal of the Чебышёв polynomial into a power series. Let’s check two simple cases:
- if , then and . Hence which is correct: the walk immediately hits one of the walls .
- if , then , hence . This means can never be odd (which makes sense, since it must always have the parity of ), and the probability of hitting a wall in exactly steps is . A moment’s reflection confirms that the answer is right.
For a serious example, with , I used Maple:
with(plots): n:=150: ser:=series(1/ChebyshevT(10, 1/x),x=0,2*n+1): for i from 1 to 2*n do a[i]:=coeff(ser, x^i) end do: listplot([seq(a[i],i=1..2*n)], color=blue, thickness=2);
By default listplot connects the dots, and since every other term is zero, the plot has a trippy pattern.
Obviously, it’s impossible to hit a wall in fewer than steps. The formula confirms this: writing a rational function with numerator , we see that no terms with can appear in the expansion.
(This post is an exercise which I should have done long ago but never did. Thanks are due to Ted Cox for a walk-through.)