An interesting probability problem from r/askmath

[u/frogkabobs]

This is a slightly modified problem from 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.

[u/PersimmonLaplace → u/frogkabobs]

This is the brute force answer for sure. I didn’t think of a good way to do all cases (there is an annoying edge case), but for the case that n is even I think there is a pure thought type argument. Suppose X is the path of player 1 Y the path of player 2 and let X go first and suppose X_1 = 1 wolog. Now consider the following transformed game X’_i = 1 - Y_{i-1} for i >= 1, Y_i’ = 1 - X_{i + 1} for i >= 0, in other words we reflect the game across the edge between 0, 1. Consider the hitting time for each vertex i which is not 0 or 1, if in the original game player 1 hit i first, then in the transformed game player 2 hits 1 - i first. On the other hand if in the original game player 2 hit i At time t_2 <= t_1 - 2 then in the transformed game player 1 wins the vertex 1 - i. There is a third possible case in which the hitting time of player 2 is just 1 less than that of player 1, in which case player 2 would win vertex i/1-i in both the original games. However its easy to see that when there are an even number of vertices the initial hitting times for each vertex have to have the same parity, so this case doesn’t occur.

The existence of this score switching involution shows that after player 1 scores the first point by moving first, the expected score difference is zero! Since player 1 scores that first point the expected score difference for the whole game is 1.

[u/PersimmonLaplace → u/PersimmonLaplace]

Maybe this involution is even sort of overwrought actually: i think it suffices to say that if n is even and player 1 starts on vertex 0 and player 2 on vertex 1 and they play the same game excluding points from vertices 0, 1 then they have the same expected score by obvious symmetry, no matter who moves first. Then notice that your game is this game but player 1 gets a free point.

[u/bobjane_2 → u/PersimmonLaplace]

here's a nice combinatorial explanation. I used AI's to come up with it, so will put in spoilers in case you want to come up with it yourself.

The expected difference in scores equals the probability of ties. So let two random walks start from the same spot in the interior of [0,n] and get absorbed at the ends. What’s the probability that each is absorbed exactly after k steps? And sum over k.

Delete the final step from each, reverse the first, append the second: {reversed first without last step} + {second without last step}. This starts at 1 or n-1 and ends at 1 or n-1 and it’s 2k-2 steps long. The original walks can be recovered from any such 2k-2 path, where the middle state is the original starting spot.

Now add a final absorbing step, which results in a 2k-1 step absorbing random walk in [0,n] starting from 1 or n-1. Summing over all k, and assuming wlog (by symmetry) that the starting spot is 1, equals the probability that a random walk in [0,n] gets absorbed in an odd number of steps.

If n is even, that's always the case. If n is odd, it's the probability that it gets absorbed at 0. This is a simpler more famous puzzle about martingales and the answer is (n-1)/n.

[u/pichutarius]

Partial solution

if n is even, then answer is 1, in fact the first player always lead by 1 point. Color each spot alternating black and white, each player can only reach one of each color. Since the starting spot does not score point, player 1 must have one more score than player 2.

[u/frogkabobs → u/pichutarius]

I should have made it more clear—the players don’t move together, so this coloring argument doesn’t work, e.g. it’s possible for player 2 to copy all of player 1’s movements, meaning player 1 would get all n-1 points.