Skip to main content
5 of 6
added 182 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.

Re-scaling T. Amdeberhan's solution to the corrected version of the problem we get expected crossings equal to $$\frac{2^{2n - 2} + 1 - \binom{2n - 1}{n-1} - n}{\binom{2n}{n}}$$