Repurpose of a repurpose of a misunderstood probability problem

[u/PersimmonLaplace]

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.

[u/bobjane_2]

This doesn't appear to be true.

import numpy as np
P = [
    [0, 1/3, 1/3, 1/6, 1/6],
    [1/3, 0, 1/3, 1/6, 1/6],
    [1/3, 1/3, 0, 1/6, 1/6],
    [1/6, 1/6, 1/6, 0, 1/2],
    [1/6, 1/6, 1/6, 1/2, 0],
]
# another nice P that fails...some zero entries, but 1 connected component
P = [
    [0, 1/4, 1/4, 1/4, 1/4],
    [1/4, 0, 3/4, 0, 0],
    [1/4, 3/4, 0, 0, 0],
    [1/4, 0, 0, 0, 3/4],
    [1/4, 0, 0, 3/4, 0],
]
P = np.array(P, dtype=float)
N = len(P)
D1 = 0.0
D2 = 0.0

for y in range(1,N):
    states = [i for i in range(N) if i != y]
    # Q: transitions that avoid y, r: probability of hitting y on the next step
    Q = P[np.ix_(states, states)]
    r = P[states, y]

    # Game 1:
    # g_i = E_i[(-1)^T_y]
    # g = -(Q g + r), so (I + Q)g = -r
    g = np.linalg.solve(np.eye(N - 1) + Q, -r)
    D1 -= g[0]

    # Game 2:
    # X[i,j] = probability two independent walks,
    # starting at i,j, first hit y on the same step.
    # X = r r^T + Q X Q^T
    A = np.eye((N - 1) ** 2) - np.kron(Q, Q)
    b = np.outer(r, r).reshape(-1, order="F")
    X = np.linalg.solve(A, b).reshape(N - 1, N - 1, order="F")
    D2 += X[0, 0]

print("D1 =", D1)
print("D2 =", D2)

[u/PersimmonLaplace → u/bobjane_2]

Ah I think you’re right! Although the Bonus statement is still true for both examples. I have added a very important hypothesis about symmetry of the random walk, with this it’s true.