Getting From Here To There On A Lattice Grid

Paths can be separated into pairs, where each pair is related by switching the ups and rights (so e.g. ("up right up up right" pairs with "right up right right up"). The key observation is that the sum of the areas under the paths in a pair is the area of the rectangle whose corners are at (0,0) and the end of the path. To see this, tilt your head 90 degrees. :)

There are $\binom{129}{m}$ paths with $m$ "ups," and they pair with $\binom{129}{m}$ paths with $129-m$ ups. So the sum of all the areas is $\sum_{m=0}^{64} m(129-m) \binom{129}{m} = \sum_{m=1}^{64} \frac{129 \cdot 128 \cdot 127!}{(m-1)!(128-m)!} = (129 \cdot 128) \sum_{n=0}^{63} \binom{127}{n} = 129 \cdot 128 \cdot 2^{126}$ (by symmetry).

Then the mean is $\frac{129 \cdot 128 \cdot 2^{126}}{2^{129}} = 129 \cdot 16$ , and $8$ more than that is $\fbox{2072}$ .

Here is a short program for a simulation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import random

def simulation():

    path = [(random.random()>=0.5) for x in xrange(129)]

    x = 0

    y = 0

    area = 0

    for i in path:

        if i:

            x += 1

            area += y

        else:

            y += 1

    return area

print sum([simulation() for i in xrange(100000)])/100000.0

That returns approximately $\boxed{2064}$ , 8 more than which is 2072

Let $E_n$ be the expected area after $n$ steps. Notice that if we are at step $n$ , we have two possibility (both equally likely)

• The $n+1$ -th step goes up ( $E_n=E_{n+1}$ )
• The $n+1$ -th step goes right ( $E_n=E_{n+1}+\overline{h}(n-1)$ )

where $\overline{h}(n-1)$ is the maximum average height of the path (the $y$ -coordinate of the ending point) at step $n-1$ . It's easy to show that $\overline{h}(n-1)$ follows a binomial distribution, hence

$\displaystyle \overline{h}(n-1)=\sum_{k=0}^{n-1} k \binom{n-1}{k} \frac{1}{2^{n-1}}=\frac{n-1}{2}$ .

We can eventually write a recurrence for $E_n$ :

$\displaystyle \begin{cases} E_n=\frac{1}{2}E_{n-1}+\frac{1}{2}\Big(E_{n-1}+\frac{n-1}{2}\Big) \\ E_1=0 \end{cases}$

which solution is

$\displaystyle E_n=\frac{1}{8}n(n-1)$

Eventually

$\displaystyle E_{129}+8=\frac{1}{8} \cdot 128 \cdot 129=\boxed{2072}$