Problem:
In the coordinate plane, a closed lattice loop of length is a sequence of lattice points such that and are both the origin and for each . A closed lattice loop of length is chosen uniformly at random from all such loops. Let be the maximum integer such that the line with equation passes through at least one point of the loop. Compute the expected number of indices such that and lies on .
(A lattice point is a point with integer coordinates.)
Solution
Solution:
We claim that if is replaced with , the answer is .
Write the path as a sequence of , , , and moves. The possible sequences that can result are precisely those with an equal number of 's and 's, and an equal number of 's and 's. We first project this sequence onto a single dimension by converting each and to a , and each and to a . The resulting sequence will have an equal number of 's and 's.
We claim that every such sequence of 's and 's corresponds to the same number of closed lattice loops. Indeed, given such a sequence, a corresponding lattice loop can be made by replacing all 's with 's and 's, and all 's with 's and 's, so that there are an equal number of 's and 's. Nothing in this replacement process is order-dependent, so the number of ways to create this loop does not depend on the initial sequence.
We can see that each of the 's move the path towards and the 's move the path away. Hence, we can think of the path as a one-dimensional walk, starting and ending in the same place, where the points on correspond exactly to the maxima of this one-dimensional walk.
Using Catalan numbers, the probability that any given point is at the maxima is
and thus by linearity, the expected number of such that is on is .
Plugging in gives a final answer of .