r/mathriddles • u/pichutarius • 23d ago
Medium repurpose of a misunderstood probability problem
This is a slightly modified problem from a recently problem , where i misinterpret as two players moving a stone around a C_n graph. To spell it out:
Two players play a game as follows. There are n nodes around a circle, a stone is placed at one of the node. Player alternate turns, moving the stone to one of the two adjacent nodes with equal probability. Each non initial node awards 1 point to the first player to reach it, the game ends when all nodes have been visited. What is the expected (signed) point difference between the players?
alternatively, prove that the expected difference is if n is even then 1 else 1-1/n. which is surprising because this answer is same as the original problem. maybe there is a connection that transform the two variant?
1
u/DuggieHS 23d ago
Let n be the number of nodes, d the expected score difference. For n=2, d=1. N=3, after the initial turn, each player has a 50% chance to end the game with a score, so d=2sum(1/2)2n+0sum(1/2)2n+1=2/3. Label the positions clockwise from the initial, with the initial position labeled 0.
For n even, the first player can only land on odd labeled spaces and the second can only land on even labeled spaces. Since the place labeled 0 (an even label) is worth nothing, the second player scores one less than the first, as there are n/2 spaces for player one to score on but only n/2-1 spaces for player 2 to score from. Thus the difference in scores is 1, and though the number of turns/path is random, the final score is not.
N=5, you probably want to use a transition matrix or something, but player 1 scores, then player 2 has a .5 chance of scoring, and then either way player 1 has a 50% chance of scoring (this position is the same as in game n=3). This goes on until the first score after the initial guaranteed score, the opposite player is guaranteed the next score as there are 3 consecutive nonscoring positions adjacent to scoring positions and we end up in a case like n=4. Once this is scored, we finally reach a new position, where either the player who scored second scores by eventually making it in the same direction as the previous score (just once in the desired direction) or the player who scored the third point scores by going all the way around the circle in the opposite direction, that is 4 more counterclockwise movements than clockwise (if we assume the 3rd score came from the clockwise direction).
Not doing the math here, but you can see how the game generally proceeds and how the positions are all related to the positions of the smaller games.
2
u/PersimmonLaplace 23d ago
There’s a clear reason the two problems are equivalent anyway: for each node let T_j be the hitting time of the original Markov process, in the original game the expected value is \sum_j Pr( T_j = T_j’) where T_j’ is another iid stone, in your game the Markov chain is the same player 1 gets a point if T_j is odd whereas player 2 gets it otherwise, so you’re trying to calculate \sum_j E[(-1)^{T_j + 1}].
It turns out that these are equal by standard results on hitting times. Let r be the vector which is the average of e_1 and e_{n-1}. The sum \sum_j \sum_t (-1)^{t + 1} Pr(T_j = t) = 1^T \cdot (1 + Q)^{-1} \cdot r
Where 1 is the uniform n-1 vector with all entries 1, Q is the transition matrix of the absorptive Markov process we get by removing the node 0 (the 1,1 minor of the original transition matrix), and r is as above. On the other hand 1 = (1 - Q)^{-1} \cdot r by explicit computation. Plugging this in we get r\cdot (1 - Q^2)^{-1} \cdot r which is the sum over all nodes of the probability that the hitting times for each node of two independent trials are equal, by the work in my answer to the original question.