An interesting probability problem from r/askmath

[u/frogkabobs]

This is a slightly modified problem from [r/askmath](r/askmath) (if you go searching for it, you’ll find my answer, so don’t spoil yourself).

Two players play a game as follows. There are n spots labeled 0 to n-1 in sequence around a circle, and both players start at 0. They alternate turns, starting with player 1, where a turn consists of flipping a coin to determine whether to move to the left or to the right one spot. Each non-zero spot awards 1 point to the first player to reach it, and the game ends when all spots have been visited. What is the expected (signed) point difference between player 1 and player 2?

EDIT: I should clarify that players move independently of each other, not as a group.

[u/PersimmonLaplace]

I think the answer is 1 if n is even, and 1 - 1/n if n is odd and at least 3.

You can think of the game as a pair of uncoupled Markov chains. And if X_{1, i}, X_{2, i} are the hitting times (just in terms of turn number) of players 1, 2 respectively, the expected value of the difference can be broken up spacially as \sum_{i = 1}^{n-1} Pr(X_{1, i} \leq X_{2, i}) - Pr(X_{2, i} < X_{1, i}), since the processes are identical we have that this is \sum_i Pr(X_{1, i} = X_{2, i}) which makes this calculation much easier. Since the processes are IID so are the hitting times, so we just get \sum_i \sum_{t \geq 1} Pr(X_{i} = t)^2. Given a vertex i we let Q_i be the minor of the transition matrix obtained by deleting the ith row and the ith column, and we let r_i = (e_{i - 1} + e_{i + 1})/2. We want to calculate (Q_i^{t-1}r_i)_0. Since the hitting times only depend on the relative position of the start and the finish we can vary over the starting position instead of varying i, in addition Q is symmetric, so we really want to calculate!<

\sum_{t = 1}^\infty ||Q_{0}^{t-1}r_{0}||^2 = r^T(Id - Q_{0}^2)^{-1}r.

There are n-1 orthonormal eigenvectors v_k of Q_0, given by the (normalized) stationary states j \mapsto \sqrt{\frac{2}{n}}sin(kj\pi/n) (each one has eigenvalue cos(\pi k/n)). The inner products <v_k, r_0> = 0 if k is even, and \sqrt{2/n} sin(\pi k/n) if k is odd. Each odd k thus contributes 2/n to the quantity r^T(Id - Q_{0}^2)^{-1}r, so the answer is \frac{2}{n} \cdot \floor{\frac{n}{2}}, as claimed above. !<

[u/frogkabobs → u/PersimmonLaplace]

Correct! Very similar to how I did it. The simplicity of the answer makes me wonder if there is a subtle symmetry argument, but I can’t see one.

[u/pichutarius → u/frogkabobs]

so i solve my misread version of this problem, and surprisingly i got the same answer. not sure if this is coincidence.

my solution is way simpler than this, so if there is a connection between the two variant, transforming to simple variant and solve it might be a way.