Skip to main content
4 of 6
added 2 characters in body; added 158 characters in body

Expected number of crossings of the diagonal of a lattice path?

If we uniformly choose a lattice path from $(0,0)$ to $(n, n)$ (i.e. at each step we can move from $(x,y)$ to $(x+1,y)$ or $(x,y+1)$), what is the expected number of times that the path crosses the diagonal?

From http://onlinelibrary.wiley.com/doi/10.2307/3314829/pdf we see that the probability that a uniformly chosen path has $r$ crossings is $2\binom{n-1}{r} / \binom{n+r+1}{n}$. And so the expectation is $2 (n!) (n-1)! \sum_{r=0}^{n-3} \frac{(r+2)(r+1)}{(n+r+2)!(n-r-2)!}$

Is a closed form possible for this expression? Even an asymptote would be helpful.

Previous edit of this had omitted brackets around n! in the final expression making T. Amdeberhan's solution correct, but for the wrong question. Sorry.