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]
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_{j\ge 1}(-1)^{j+1}\binom{2n}{n+kj}\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}). $$