Probability of Reaching D before E

Question

Consider a simple finite graph such as this [1]: https://i.stack.imgur.com/r0RJJ.png

If we start at $A$, what is the probability of hitting $D$ before $E$?

I know that the probability of hitting $D$ before $E$ is the same as the probability of hitting $E$ before $D$ , due to symmetry.

I calculated the transition matrix to be :

$$ P= \begin{pmatrix} 0 & 1 & 1 &1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ \end{pmatrix} $$ with states A,B,C,D,E

and the adjency matrix: $$ B= \begin{bmatrix} 0 & 1/3 & 1/3 &1/3 & 0 \\ 1/3 & 0 & 1/3 & 0 & 1/3 \\ 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ \end{bmatrix} $$ with states A,B,C,D,E

What should i do next?

Answer 1

For $L\in\{A,B,C\}$ let $p_L$ denote the probability of hitting $D$ before $E$ if we start in $L$.

To be found is $p_A$ and we have the following equalities:

• $p_A=\frac13+\frac13p_B+\frac13p_C$
• $p_B=\frac13p_A+\frac13p_C$
• $p_C=\frac12p_A+\frac12p_B$

The equalities enable us to find $p_A=\frac58$, $p_B=\frac38$ and $p_C=\frac12$.

---

More shortly it is evident that $p_C=\frac12$ and that $p_B=1-p_A$ on base of symmetry.

Then the equality under the first bullet becomes:

• $p_A=\frac13+\frac13(1-p_A)+\frac13\frac12$

And it immediately follows that $p_A=\frac58$.