Counterexample to $\operatorname{br} T = 1 \iff T \textrm{ recurrent}$:
This counterexample uses the following notation: $T$ is a locally finite infinite tree with root $o$, i.e.
the number of vertices is infinite but the degree of every node is finite. All considered random
walks are simple random walks starting at the root, i.e. random walks which take each edge with
equal probability. The random walk is recurrent if it returns to the root with probability
$1$ (and hence returns to the root infinitely often almost surely), and transient if it
only returns to the root with probability $< 1$, i.e. the probability of never returning is positive.
The branching number $\operatorname{br} T$ of a tree $T$ is defined as in 1, page 80 / Equation 3.4.
A spherically symmetric tree is a tree such that every node at distance $n$ from the root
has the same number of children. By 1, page 4 / Exercise 1.2, it holds that
$\operatorname{br} T = \operatorname{gr} T$ (if the latter exists) for every spherically symmetric tree where $\operatorname{gr} T$ is the
growth rate given by $\operatorname{gr} T := \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}}$ with $T_n$ being the set
of vertices at distance $n$ from the root.
In the following, random walk will be used for simple random walk. As it depends entirely on the
tree $T$ whether the simple random walk is recurrent or transient, the formulation $T$ is recurrent or
transient will be used, meaning that the simple random walk on $T$ starting at the root is
recurrent or transient.
It holds that $\operatorname{br} T = 1 \impliedby T \textrm{ recurrent}$. See 1, Theorem 3.5.
However, $\operatorname{br} T = 1 \implies T \textrm{ recurrent}$ is wrong, as the following example shows:
Consider the infinte binary tree. Let $T_n$ as above. Then, replace every edge exiting $T_n$ with
a chain of $n$ nodes. See Figure 1: at every level $T_n$ of the original binary tree, linearly
many (exactly $n$) generations with only one child per node are added, indicated in blue.
From now on, call this tree $T$ ($T$ is on the right in Figure 1). Claim: $\operatorname{br} T = 1$
and the random walk on $T$ is transient.
Proof:
First, $\operatorname{br} T = 1$ is shown, followed by the proof of transience.
$T$ is spherically symmetric, so $\operatorname{br} T = \operatorname{gr} T = \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}}$.
It holds that
\begin{align*}
\left|T_n\right| = 2^k \textrm{ for } \frac{k\left(k-1\right)}{2} < n \leq \frac{k\left(k+1\right)}{2}
\end{align*}
This can be seen easily: $2^k$ is the number of nodes on level $k$ in the original binary tree.
Adding first $1$, then $2$, then $3$, and so on nodes in between the levels, $2^k$ is now the number
of nodes for all levels between $1 + 2 + \ldots + k - 1 = \frac{k\left(k-1\right)}{2}$ (exclusive) and
$1 + 2 + \ldots + k = \frac{k\left(k+1\right)}{2}$ (inclusive), also see Figure 1.
This implies, selecting the appropriate $k$:
\begin{align*}
\sqrt[k+1]{4} = \left(2^k\right)^{\frac{2}{k\left(k+1\right)}} \leq \left|T_n\right|^{\frac{1}{n}} < \left(2^k\right)^{\frac{2}{k\left(k-1\right)}} = \sqrt[k-1]{4}
\end{align*}
Both sides converge to $1$ for $k \to \infty$, and as $k \to \infty$ for $n \to \infty$,
we conclude $\operatorname{gr} T = \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}} = 1$.
To show that $T$ is transient, we use the following Theorem 11 from 2 /
Theorem 2.11 from 1 (these two theorems are the same):
the random walk on $T$ is transient if, and only if, the tree admits a finite energy source flow.
A flow is a map $f: E \to \left[0, \infty\right)$ with the set of edges $E$ (outward-oriented)
of $T$, such that the incoming flow at every node (except from the root) from its parent is the same as the sum of the outgoing flows
to its children. The energy of the flow is defined as $\sum_{e \in E} f\left(e\right)^2$.
Hence, it suffices to show the existence of such an $f$ for the considered $T$ with finite energy.
Define $f$ as follows: for the edges exiting the root, set $f\left(e\right) = \frac{1}{2}$. Then,
whenever a node has two children, split the flow equally among them. See Figure 2:
the flow $f$ is indicated in blue for selected edges.
It remains to calculate the energy of the flow. This is simple: there are exactly $2^n \cdot n$
edges with a flow of $\frac{1}{2^n}$, also see Figure 2 again. It then follows
that $\sum_{e \in E} f\left(e\right)^2 = \sum_{n = 1}^\infty 2^n \cdot n \cdot \left(\frac{1}{2^n}\right)^2$
which is convergent by the root test. In fact, $\sum_{n = 1}^\infty 2^n \cdot n \cdot \left(\frac{1}{2^n}\right)^2 = 2$.
Hence, the energy of $f$ is finite and we can conclude that $T$ is transient.
In general, edge-colorings of the complete graph without a tricolored triangle are called Gallai colorings. These are studied generally, not just with three colors available, though if we only use $2$ colors the problem is a bit easy :)
The paper Edge Colorings of Complete Graphs Without Tricolored Triangles by Gyárfás and Simonyi gives a good overview and in particular contains a proof of the following result (Theorem A in the paper):
Any Gallai coloring can be obtained by substituting complete graphs with Gallai colorings into vertices of $2$-colored complete graphs.
Let me elaborate on this idea. It is a way of building bigger Gallai colorings out of smaller ones. Suppose we have already found Gallai colorings of complete graphs on $n_1, n_2, \dots, n_k$ vertices. (Sometimes $n_i = 1$, in which case there is nothing to color; that's fine.) We also take an arbitrary $2$-coloring of the complete graph on $k$ vertices; that will be our "glue". Call the small Gallai colorings $C_1, C_2, \dots, C_k$ and call the "glue" $G$.
Now, to color the complete graph on $n_1 + n_2 + \dots + n_k$ vertices, begin by placing disjoint copies of $C_1, C_2, \dots, C_k$. What's left is to color the edges between these copies. For this, we give all the edges between $C_i$ and $C_j$ the same color: the color of edge $ij$ in $G$.
Any triangle in the resulting coloring has one of three types:
- It could be entirely contained in a small Gallai coloring, in which case it is not tricolored by assumption.
- It could have two vertices in one small coloring $C_i$ and the third in another, $C_j$; then two of its edges get their color from edge $ij$ of $G$, and have the same color.
- It could have all three vertices in different small colorings; then all three of its edges are colored using $G$, which only has $2$ colors.
The really interesting bit is that this recipe gives us all the possible Gallai colorings.
The recipe also lets us disprove other conjectures we might have about Gallai colorings. For example, in a three-color Gallai coloring of $K_6$, it is not necessarily true that some partition $A,B$ exists where all edges between $A$ and $B$ are the same color. One way to get there is to color $K_5$ by coloring a $5$-cycle red and its complement blue. Then, substitute a green edge in place of one of the vertices of $K_5$, as described above.
Best Answer
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.