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

Question

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 $$2\frac{2^{2n - 2} + 1 - \binom{2n - 1}{n-1} - n}{\binom{2n}{n}} <_\approx \frac{2^{2n-1}}{\binom{2n}{n}} - 1 $$

Answer 1

Here's a solution.

1. Number of touches of diagonal (more simple case).

Consider generating function of lattice paths which don't touch and don't cross the diagonal: $$ Cat(z) = \dfrac{1 - \sqrt{1 - 4z}}{2} = z + z^2 + 2z^3 + 5z^4 + 14z^5 + \ldots $$ Then we take product of $ k $ Catalan generating series which stands for lattice paths touching or crossing exactly $ k$ points: $$ [z^n] (Cat(z))^k = \text{# lattice paths from $(0,0)$ to $(n,n)$ having exactly k diagonal points} $$ Then we assemble everything into bivariate generating function, adding multiple $2^k$ for two different possible sides of Catalan paths: $$ F(z,u) = \sum_{k \geq 1} 2^k(Cat(z))^k u^k = \dfrac{1}{1 - u(1 - \sqrt{1-4z})} $$ Note that if we plug $u=1$ then we obtain all possible paths from $(0,0)$ to $(n,n)$ regardless of number of diagonal crosses: $$ \dfrac{1}{\sqrt{1-4z}} = 1 + 2z + 6z^2 + 20z^3 + \ldots = \sum_{n \geq 0} {2n \choose n} z^n \enspace . $$ According to the method of bivariate generating functions, the expectation is expressed by applying the point derivative operator: $$ u \dfrac{d}{du} \sum_{n, k, \geq 0} a_{n,k} z^n u^k = \sum_{n, k, \geq 0} k a_{n,k} z^n u^k \enspace , $$ Denoting by $[z^n]f(z)$ the coefficient at $z^n$ in function $f(z)$, and by $U_n$ – random variable denoting the number of crossings, we obtain $$ \mathbb E U_n = \dfrac{[z^n] \left.u \dfrac{d}{du} F(z,u)\right|_{u=1}}{[z^n] \left.F(z,u)\right|_{u=1}} \enspace . $$ $$ \left.\dfrac{d}{du}\dfrac{1}{1 - u(1 - \sqrt{1-4z})} \right|_{u=1} = \left.\dfrac{1 - \sqrt{1-4z}}{\left[1 - u(1 - \sqrt{1-4z})\right]^2} \right|_{u=1} = \dfrac{1 - \sqrt{1-4z}}{1 - 4z} $$ Applying asymptotic extraction of coefficients, $$ \mathbb E U_n = \dfrac{[z^n] \dfrac{1}{1 - 4z}} {[z^n] \dfrac{1}{\sqrt{1 - 4z}}} = \dfrac{4^n}{2n \choose n } \sim \sqrt{ \pi n} $$

2. Number of crossings of diagonal (the same idea, the functions more clumsy). Instead of non-touching Catalan we consider non-crossing non-empty Catalan: $$ Cat^\ast(z) = \dfrac{1 - \sqrt{1 - 4z}}{2z} - 1 = z + 2z^2 + 5z^3 + 14z^4 + \ldots $$ Then we multiply Catalan generating functions in an alternating manner (times 2 for initial one): $$ [z^n] 2 (Cat^\ast(z))^k $$ and doing the same stuff as before, we arrive to bivariate gf (minus one because the board $0 \times 0$ was counted twice): $$ G(z,u) = 2 \cdot \dfrac{1}{1 - u \cdot \dfrac{1 - 2z-\sqrt{1 - 4z}}{2z}} - 1 $$ Check what happens at $u=1$: $$ G(z,1) = \dfrac{4z}{4z - 1 + \sqrt{1 - 4z}} = 1 + 2z + 6z^2 + 20z^3 + \ldots $$ After differentiation and plugging $u=1$ obtain the asymptotics: $$ \left. u \dfrac{d}{du} G(z,u) \right|_{u=1} = \dfrac{-2z - \sqrt{1-4z}+1}{z \left(1 - \frac{-2z-\sqrt{1-4z}+1}{2z}\right)^2} $$ Near the singularity $z = \frac14$ we have an expansion: $$ \left. u \dfrac{d}{du} G(z,u) \right|_{u=1} \sim \dfrac{1}{2 (1 - 4z)} $$ Finally, the asymptotics is as in the first case, divided by 2: $$ \mathbb E U_n \sim \dfrac{\sqrt{\pi n}}{2} $$

P.S. The final answer looks familiar to the expression of T.Amdeberhan which is of order $ \dfrac{1}{2}\cdot \dfrac{4^n}{ {2n \choose n}}$

Answer 2

I count $(0,0)$ and $(n,n)$ as crossings, subtract 2 if you do not want. For $k\in \{0,1,\dots,n\}$ denote by $\xi_k$ the random variable which equals 1 if $(k,k)$ lies on the path and 0 otherwise. Then the number of crossings of the diagonal equals $\sum \xi_k$. By linearity of expectation, we see that the expected number of crossings equals $\sum \mathbb{E}\xi_k=\binom{2n}n^{-1}\sum_k \binom{2k}k\binom{2(n-k)}{n-k}=4^n/\binom{2n}n$ by a well-known identity $\sum \binom{2k}k\binom{2(n-k)}{n-k}=4^n$ (see, for example, Stanley's Enumerative Combinatorics vol.1 exercise I.3(c).)

Answer 3

Yes, it has a closed form.

Edited according to your request. $$2\cdot n! (n-1)! \sum_{r=0}^{n-3} \frac{(r+2)(r+1)}{(n+r+2)!(n-r-2)!} =\frac2{\binom{2n}n}\left(2^{2n-2}+1-\binom{2n-1}{n-1}-n\right).$$