Expected maximum deviation of lattice path Suppose there is an election with two candidates, Alice and Bob. Each candidate receives $n$ votes. As the votes are counted in a random order, what is the expected value of the maximum difference between Alice and Bob's partial totals? Note that this is process is equivalent to choosing a random lattice path from $(0,0)$ to $(n,n)$, equally likely from all $\binom{2n}n$ possibilities, and looking at the maximum distance of this path from the diagonal $y=x$ (up to a factor of $\sqrt{2}$).
I heard the problem from this blog post, where it is phrased in terms of sock matching. I ask this question because I expect it has a nice approximate answer; namely, the author of that post crunched the numbers and found that the expected value is well approximated by $\sqrt{\frac{3}2n}$, as shown in the data below. I wonder if anyone knows if this problem appears in the literature, and if they can prove or refute this claim?

Here is what I know:

*

*Let $M$ be the maximum difference in votes. In this other answer, I showed that for any $m\ge 1$, we have
$$
P(M<m) = \frac1{\binom{2n}n}\sum_{k=-\lfloor n/m\rfloor}^{\lfloor n/m\rfloor}(-1)^{k}\binom{2n}{n+km}\tag1
$$
You can then use this to compute $E[M]$, via $E[M]=\sum_{m=1}^n \big(1-P(M<m)\big)$. Furthermore, the expression in $(1)$ direcctly implies
$$
P(M<m)=\frac1{\binom{2n}n}\cdot\frac2m\cdot 2^{2n}\sum_{k=1}^{\lfloor m/2\rfloor} \bigg[\cos\left(\frac{(2k-1)\pi}{2m}\right)\bigg]^{2n}
$$
by using a roots-of-unity filter on the generating function $(x^{1/2}+x^{-1/2})^{2n}$. As $n\to \infty$, the main contribution is from the $k=1$ term, so $P(M<m)$ grows like $\frac1{\binom{2n}n}\cdot\frac2m\bigg[2\cos\left(\frac{\pi}{2m}\right)\bigg]^{2n}$.


*A somewhat related problem is finding the expected height of a random Dyck path of order $n$, which is just a random lattice path conditioned on staying above the diagonal $y=x$. In $[1]$, de Bruijn, Knuth, and Rice show that the expected height of a Dyck path is asymptotically $\sqrt{\pi n}-\frac12$. Perhaps something similar to their methods works here.



*

*Bruijn, de, N. G., Knuth, D. E., & Rice, S. O. (1972). The average height of planted plane trees. In R. C. Read
(Ed.), Graph Theory and Computing (pp. 15-22). Academic Press Inc. [PDF]

 A: Not an answer, but perhaps a step in the right direction.
Wikipedia has a nice approximate formula for $C(n,k)$ for when $n$ is large and $k$ is close to $n/2$. Using $n\to 2n$ and $k\to n-ku$ we get
$$C(2n,n-ku)\approx\frac{2^n}{\sqrt{n\pi/2}}\exp\left(\frac{-(n-2(n-ku))^2}{2n}\right)$$
$$=\frac{2^n}{\sqrt{n\pi/2}}\exp\left(\frac{-(n-ku)^2}{2n}\right)$$
$$=\frac{2^n}{\sqrt{n\pi/2}}e^{-n/2}\cdot e^{ku/n}\exp\left(\frac{-k^2u^2}{2n}\right)$$
So then going to the sum mentioned in the blog post we have
$$\mathrm{E}[U]\approx\frac{2^{n+1}e^{-n/2}}{C(2n,n)\sqrt{n\pi/2}}\sum_{u=1}^n\sum_{k=1}^{\lfloor n/u\rfloor}(-1)^{k-1}e^{ku/n}\exp\left(\frac{-k^2u^2}{2n}\right)$$
Perhaps this will submit more readily to analysis, but I'm a bit out of my depth here.
A: It actually turns out that
$$
\boxed{E[M_n]={\log 2}\;(\pi n)^{1/2}-\tfrac12+O(n^{-1/2}).}
$$
Here is a very rough outline of the proof. Using the reflection principle, for any $k\ge 1$,
$$
P(M\ge k)=\sum_{k\ge 1}(-1)^{k+1}\binom{2n}{n+k}\Big/\binom{2n}n
$$
Then, when computing $E[M_n]=\sum_{k\ge 1}P(M_n\ge k)$, you can collect like terms, and find there is a positive contribution of $\binom{2n}{n+k}$ for each odd divisor of $k$, and a negative one for each even divisor. Letting $d(k)$ be the number of divisors of $k$, the net number of times $\binom{2n}{n+k}$ added in is therefore $d(k)$ when $k$ is odd, and $d(k)-2\cdot d(k/2)$ when $k$ is even.
\begin{align}
E[M_n]
&=2\sum_{k\ge 1} d(k){\binom{2n}{n+k}}\Big/{\binom{2n}{n}}-4\sum_{k\ge 1} d(k){\binom{2n}{n+2k}}\Big/{\binom{2n}{n}}
\\&\approx 2\sum_{k\ge 1}d(k)\exp(-k^2/n)\quad\quad-4\sum_{k\ge 1}d(k)\exp(-4k^2/n)
\end{align}
The first sum is handled in the Knuth/de Bruijn/Rice paper, and they use complex analysis to show that, for all $m>0$,
$$
\sum_{k\ge 1}d(k)\exp(-k^2/n)
= (\pi n)^{1/2}\bigg(\tfrac14\log n+\tfrac34\gamma -\tfrac12\log 2\bigg)
+\tfrac14+O(n^{-m}).
$$
In their notation, this sum is $g_0(n)$, defined in equation $(26)$, with the approximation appearing at $(32)$. You can then tweak their calculations to show
$$
\sum_{k\ge 1}d(k)\exp(-4k^2/n)
= (\pi n/4)^{1/2}\bigg(\tfrac14\log (n/4)+\tfrac34\gamma -\tfrac12\log 2\bigg)
+\tfrac14+O(n^{-m}).
$$
