# Transient random walk on 3-color 3-regular tree

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.

• 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? – Berry van Peer Feb 24 at 21:17
• @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. – Mr. G Feb 24 at 22:24
• Alright, looks like I still got some work to do, but you pointed me in the right direction. Thank you for your help. – Berry van Peer Feb 25 at 10:59