, 2023

Solution:

Notice that the order in which the people leave the line is irrelevant. Give each right-facing person a weight of $1$, and each left-facing person a weight of $-1$. We claim the answer for some arrangement of these $2n$ people is $-2$ times the minimum prefix sum. For instance:

$$\begin{gathered} \text{ LRRLRLLLRRRRL } \rightarrow (-2)(-2) \rightarrow 4 \\ \text{ RRRLLRLLLRRL } \rightarrow (-2)(-1) \rightarrow 2 \end{gathered}$$

Proof. The final configuration is always of the form

and the minimum prefix sum is invariant. As the final configuration has minimum prefix sum $k$, we are done.

So, we want to find the expected value of the minimum prefix sum across all such strings of $1$s and $-1$s. To find this, we will instead compute the equivalent value

$$\sum_{k=1}^{\infty} \operatorname{Pr}[\text{ maximum prefix sum is } \geq k]$$

Consider the $k$th term of this sum, and the corresponding walk from $(0,0)$ to $(2n, 0)$ with L corresponding to a step of $(1,-1)$ and R corresponding to a step of $(1,1)$. Consider the point $P$ at $y=k$ with minimal $x$-coordinate, and reflect the remainder of the walk across $y=k$. This gives a path that ends at $(2n, 2k)$. Noting that this is a bijection between walks from $(0,0)$ to $(2n, 2k)$ and walks that reach $y=k$, we have

$$\begin{aligned} \sum_{k=1}^{\infty} \operatorname{Pr}[\text{ maximum prefix sum is } \geq k] & = \sum_{k=1}^{\infty} \frac{\binom{2n}{n-k}}{\binom{2n}{n}} \\ & = \frac{1}{2}\left[\left(\sum_{k=-\infty}^{\infty} \frac{\binom{2n}{n-k}}{\binom{2n}{n}}\right)-1\right] \\ & = \frac{1}{2}\left(\frac{2^{2n}}{\binom{2n}{n}}-1\right) \end{aligned}$$

Adjusting for the factor of $2$ we saved at the beginning, our final answer for $n=50$ is $\frac{2^{100}}{\binom{100}{50}}-1$.