Repurpose of a repurpose of a misunderstood probability problem
Let G be a finite graph and for every pair of vertices let P: Vert(G) \times Vert(G) \to [0, 1] be a matrix of transition probabilities for a random walk on G (so \sum_{x a neighbor of y} P(x, y) = 1) such that any vertex is reachable from any other vertex with nonzero probability. Assume as well that P(x, y) = P(y, x) for any x, y \in Vert(G), and that there is a group of symmetries \Gamma acting transitively on the vertices, such that P(\gamma x, \gamma y) = P(x, y) for all \gamma \in \Gamma.
Fix a vertex v_0 \in Vert(G), consider the two following games.
Game 1:
A token starts at vertex v_0 player 1 does a random step according to the probabilities P, then the next turn player 2 moves the same token again according to P, and so on. Each player gets a point for each vertex (not including v_0) that they visit first.
Game 2:
Each player has their own token both starting at v_0, player one moves her token according to P, then player 2 moves her token according to P, and so on. Scoring is the same.
Show the expected score difference of the two players is the same in both games.
Bonus: drop the condition that P(x, y) = P(y, x) and replace it with the condition \pi(x)P(x, y) = \pi(y) P(y, x) for all x, y, where \pi is the stationary distribution of the random walk P. Also drop the condition about the vertex transitive group of symmetries. Instead of fixing a vertex v_0, choose a vertex v_0 ~ \pi, and show that the same conclusion holds for the two games above, taking into account the random choice of v_0.