Question

Consider a graph with nodes \(1,2, \ldots, n\) and the \(\left(\begin{array}{l}n \\\ 2\end{array}\right) \operatorname{arcs}(t, j), i \neq j, i, j,=1, \ldots, n\) (See Section 3.6.2 for appropriate definitions.) Suppose that a particle moves along this graph as follows: Events occur along the arcs \((i, j)\) according to independent Poisson processes with rates \(\lambda_{i j} .\) An event along arc \((i, j)\) causes that arc to become excited. If the particle is at node \(i\) at the moment that \((i, j)\) becomes excited, it instantaneously moves to node \(j, i, j=1, \ldots, n .\) Let \(P_{j}\) denote the proportion of time that the particle is at node \(j .\) Show that $$ P_{j}=\frac{1}{n} $$ Hint: Use time reversibility.

Short answer

First, we express the probability of moving from node i to node j as $p_{ij} = \frac{\lambda_{ij}}{\sum_{k \neq i} \lambda_{ik}}$. Then, we use the concept of time reversibility with the equation $P_i p_{ij} = P_j p_{ji}$. Rearranging the equation and applying summation to find $P_i$, we obtain $P_i = \frac{1}{\sum_{j=1}^{n}\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}}}$. As this expression is independent of i, the proportion of time the particle is at node j, $P_j$, is independent of j as well. Therefore, with n nodes in total, we can conclude that \(P_j = \frac{1}{n}\).

Step-by-step solution

Events and Probabilities

First, we need to express the probability of moving from node i to node j. Since events along arc (i,j) occur according to a Poisson process with rate λ_{ij}, we can write the probability p_{ij} as: $$ p_{ij} = \frac{\lambda_{ij}}{\sum_{k \neq i} \lambda_{ik}} $$ Notice that we divide by the summation of all λ values for node i, excluding λ_{ii} since i ≠ j.

Time Reversibility

Now, we recall that a Markov chain is time-reversible if: $$ P_i p_{ij} = P_j p_{ji} $$ for all i and j. Here, P_i and P_j represent the proportions of time that the particle is at nodes i and j, respectively. Using the expression for p_{ij} from Step 1, we have: $$ P_i\frac{\lambda_{ij}}{\sum_{k \neq i} \lambda_{ik}} = P_j\frac{\lambda_{ji}}{\sum_{k \neq j} \lambda_{jk}} $$

Rearrange the Equation

Now we can rearrange the time-reversibility equation to get an expression involving P_j: $$ P_j = P_i\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}} $$

Applying the Summation

Sum P_j over all j from 1 to n: $$ \begin{aligned} \sum_{j=1}^{n} P_{j} &= \sum_{j=1}^{n} P_i\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}} \\ &= P_i\sum_{j=1}^{n}\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}}. \end{aligned} $$ Recall that the sum of all P_j values is equal to 1, as they are probabilities: $$ 1 = P_i\sum_{j=1}^{n}\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}} $$

Solve for P_i

In order to find the value of P_i, we divide both sides of the above equation by the summation: $$ P_i = \frac{1}{\sum_{j=1}^{n}\frac{\lambda_{ij}}{\lambda_{ji}}\frac{\sum_{k \neq j} \lambda_{jk}}{\sum_{k \neq i} \lambda_{ik}}} $$ Notice that this expression for P_i is independent of i, meaning that the proportion of time the particle is at any node i is the same.

Conclude P_j = 1/n

Since our expression for P_i is independent of i, we can conclude that the proportion of time the particle is at node j, P_j, is also independent of j. Therefore, since there are n nodes in total, we can conclude that $$ P_j = \frac{1}{n} $$