Recorrido aleatorio transitorio en un árbol de tres colores

Question

Supongamos que $T=(V,E)$ es un árbol 3-regular con raíz $0$ . Supongamos que $0$ es de color verde. Todos los demás vértices se colorean de azul, rojo o verde, de manera que cada vértice tiene exactamente un vecino de cada color. Son posibles múltiples coloraciones. Sólo hay que elegir uno.

Dejemos que $R=(R(n))_{n \geq 0}$ sea un paseo aleatorio sobre $V$ que comienza en la raíz, por lo que $R(0)=0$ . En cada paso, pasa al vecino (más cercano) coloreado $x\in\{\text{blue},\text{red},\text{green}\}$ con probabilidad $p_x$ . Supongamos que $p_{\text{blue}},p_{\text{red}},p_{\text{green}}>0$ y $p_{\text{blue}}+p_{\text{red}}+p_{\text{green}}=1$ . Se sabe que $R$ es transitoria. Para cada subárbol inducido por los vértices L, M, R (ver figura) deseo calcular la probabilidad de que $R$ "escapa al infinito" en ese subárbol específico. Este problema es trivial si $p_{\text{blue}},p_{\text{red}},p_{\text{green}}=\frac{1}{3}$ para cada subárbol inducido por L, M, R el paseo $R$ se escapa en él con probabilidad $\frac{1}{3}$ por simetría. He intentado utilizar argumentos de simetría similares en el caso general sin éxito. ¿Puede alguien ayudarme con el caso general?

Answer 1

Su proceso puede pensarse como un paseo aleatorio sobre las letras $r, g$ y $b$ . Representaré a $R_{n}$ como una cadena como $ggbbgb$ . Denote $|R_n|$ como el número de símbolos de dicha cadena.

Su pregunta es, creo: ¿cuáles son las probabilidades de que la primera "letra" de la palabra límite sea $r, g$ o $b$ ?

Necesitaremos la primera variable aleatoria de visita $T(x) = \min_{k \geq 1} \{R_{k} = x \}$ y las funciones generadoras $S_{i, j} = E[\lambda^{T(j)} I_{|R| = 2} | R_0 = i]$ para $i, j \in \{r, g, b \}$ . En palabras, $S_{i, j}$ es la función generadora de la primera visita al nodo más cercano de color $j$ , empezando por el color $i$ . Soy un poco perezoso y utilizo la simetría traslacional, es decir, el hecho de que todos los vértices de un color determinado tienen el mismo aspecto. De un análisis de primer paso se deduce que tenemos nueve ecuaciones

\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}

donde estoy indexando las permutaciones $r, g, b$ por $1, 2, 3$ . A continuación, definiré la función generadora de retorno $S_{\text{self}}(i) = E[\lambda^{T(i)} | R_0 = i]$ es decir, la función generadora de la primera vuelta a la palabra actual. Tenemos $$ 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} $$ Por último, necesitamos la probabilidad de escape. Será más fácil calcular la probabilidad de no escapar. La función generadora de no escapar del nodo $i$ es la función generadora de la primera visita al nodo raíz verde o a sí mismo. Por lo tanto, $$ S_{\text{not escape}}(i) = \lambda(p_g + p_b S_{b, i} + p_r S_{r, i}) $$ Así que la probabilidad de escapar es $$ p_{\text{escape}}^{(i)} = 1 - (p_g + p_b P_{b, i} + p_r P_{r, i}) \tag{3} $$ donde he introducido la notación $P_{i, j} = S_{i, j}(\lambda = 1)$ . Si se combina todo esto, la probabilidad de escapar de cualquier nodo individual $P_{\text{escape}}^{(i)}$ es \begin{align} P_{\text{escape}}^{(i)} = \frac{P_{g, i} p_{\text{escape}}^{(i)}}{1 - P_{\text{self}}^{(i)}} \end{align} Queda por resolver la Ec. (1) numéricamente para hallar las ecuaciones (2) y (3). Se puede comprobar que $S_{i, j} = (3 - \sqrt{9 - 8 \lambda^2})/4\lambda$ en el caso simétrico, lo que lleva a $P_{\text{escape}}^{(i)} = 1/3$ como se esperaba.