Suppose that $T=(V,E)$ is a 3-regular tree with root $0$. Suppose that $0$ is colored green. All other vertices are colored blue, red or green, such that each vertex has exactly one neighbour of each color. Multiple colorings are possible. Just pick one.

Let $R=(R(n))_{n \geq 0}$ be a random walk on $V$ that starts at the root, so $R(0)=0$. At each step, it steps to the (nearest) neighbour colored $x\in\{\text{blue},\text{red},\text{green}\}$ with probability $p_x$. Assume that $p_{\text{blue}},p_{\text{red}},p_{\text{green}}>0$ and $p_{\text{blue}}+p_{\text{red}}+p_{\text{green}}=1$. It is known that $R$ is transient. For each subtree induced by vertices L, M, R (see figure) I wish to compute the probability that $R$ "escapes to infinity" in that specific subtree. This problem is trivial if $p_{\text{blue}},p_{\text{red}},p_{\text{green}}=\frac{1}{3}$: for each subtree induced by L, M, R the walk $R$ escapes in it with probability $\frac{1}{3}$ by symmetry. I have tried to use similar symmetry arguments in the general case without succes. Can anyone help me with the general case?


Your process can be thought of as a random walk on the letters $r, g$ and $b$. I will represent $R_{n}$ as a string such as $ggbbgb$. Denote $|R_n|$ as the number of symbols in such a string.

Your question is, I believe: what are the probabilities that the first "letter" in the limiting word is $r, g$ or $b$?

We'll need the first visit random variable $T(x) = \min_{k \geq 1} \{R_{k} = x \}$ and the generating functions $S_{i, j} = E[\lambda^{T(j)} I_{|R| = 2} | R_0 = i]$ for $i, j \in \{r, g, b \}$. In words, $S_{i, j}$ is the generating function for the first visit to the nearest node of color $j$, starting at color $i$. I'm being a bit lazy and using translational symmetry, i.e the fact that every vertex of a given color looks the same. It follows from a first-step anaylsis that we have nine equations

\begin{align} S_{i, j} = \lambda(p_{j} + p_{j + 1} S_{j + 1, i} S_{i, j} + p_{j + 2} S_{j + 2, i} S_{i, j}) \tag{1} \end{align}

where I'm indexing the permutations $r, g, b$ by $1, 2, 3$. Next, I'll define the return generating function $S_{\text{self}}(i) = E[\lambda^{T(i)} | R_0 = i]$, i.e. the generating function for the first return to the current word. We have $$ S_{\text{self}}(i) = \lambda(p_{j} S_{j, i} + p_{j+1} S_{j+1, i} + p_{j+2} S_{j+2, i}) \tag{2} $$ Finally, we need the escape probability. It will be easier to calculate the probability of not escaping. The generating function for not escaping from node $i$ is the generating function for the first visit to the green root node or to itself. Hence, $$ S_{\text{not escape}}(i) = \lambda(p_g + p_b S_{b, i} + p_r S_{r, i}) $$ So the probability of escaping is $$ p_{\text{escape}}^{(i)} = 1 - (p_g + p_b P_{b, i} + p_r P_{r, i}) \tag{3} $$ where I have introduced the notation $P_{i, j} = S_{i, j}(\lambda = 1)$. Putting this all together, the probability of escaping from any individual node $P_{\text{escape}}^{(i)}$ is \begin{align} P_{\text{escape}}^{(i)} = \frac{P_{g, i} p_{\text{escape}}^{(i)}}{1 - P_{\text{self}}^{(i)}} \end{align} It remains to solve Eq. (1) numerically in order to find Eqs. (2) and (3). One can check that $S_{i, j} = (3 - \sqrt{9 - 8 \lambda^2})/4\lambda$ in the symmetric case, which leads to $P_{\text{escape}}^{(i)} = 1/3$ as expected.

  • $\begingroup$ Thank you for your response. I like your answer. In the symmetric case (1) is easily solved since all $S(i,j)$ are equal. However, I fail to see how to "solve Eq. (1) numerically" in general. Could you eloborate on how to do that? Also, although I read here math.stackexchange.com/questions/25430/… that "Closed form formulas are overrated", I would like to find a closed formula for $P_{\text{escape}}^{(i)}$. Do you think that would be possible here? $\endgroup$ – Berry van Peer Feb 24 at 21:17
  • $\begingroup$ @BerryvanPeer My feelings are that it isn't possible to solve Eq. (1) exactly for an arbitrary $p_r, p_b, p_g$. Some ideas: 1. You only need the solution for $\lambda = 1$. 2. There will be a solution such that each $P_{i, j}$ is in $[0, 1]$, which means that your numerical method only needs to look in that region. 3. It may be possible to get a closed form solution in the case where two of the probabilities are equal. Say $p_r = p_g = q$, then $p_b = 1 - q$ and your system only has one parameter. I bet you can get something like a quartic equation for one of the $P_{i, j}$ after symmetry. $\endgroup$ – Mr. G Feb 24 at 22:24
  • $\begingroup$ Alright, looks like I still got some work to do, but you pointed me in the right direction. Thank you for your help. $\endgroup$ – Berry van Peer Feb 25 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.