Comparación de las probabilidades de acierto frente a la comparación de los tiempos medios de acierto de un paseo aleatorio sobre un gráfico

Question

Estoy intentando comprender los paseos aleatorios sobre grafos y si una intuición que tengo puede hacerse rigurosa matemáticamente, y si además es cierta.

Sea $G$ sea un grafo no dirigido, finito y conexo con $n$ vértices y realizamos un simple paseo aleatorio sobre $G$ . Supongamos que tenemos tres vértices distintos $a$ , $b$ , $c$ y que nuestro paseo aleatorio comienza en $a$ . A continuación, podemos definir los tiempos medios de impacto $h_{ab}$ , $h_{ac}$ que son el número esperado de pasos hasta llegar a $b$ y $c$ respectivamente. Cada uno de ellos puede calcularse resolviendo un sistema lineal de ecuaciones. Ahora, mi pregunta es la siguiente.

Supongamos de nuevo que nuestro paseo comienza en $a$ . Si sabemos que la probabilidad de alcanzar $b$ sin pasar por $c$ es estrictamente mayor que la probabilidad de alcanzar $c$ sin pasar por $b$ entonces podemos decir que $h_{ab} < h_{ac}$ ?

El razonamiento intuitivo sería que si tenemos más posibilidades de llegar a un punto sin pasar por el otro, en lugar de al revés, entonces debería tener sentido que llegáramos a ese punto también más rápido de media.

¿Cómo puede hacerse matemáticamente riguroso? ¿Es cierto?

Answer 1

Creo que es falso. Esto se debe a que los caminos de $a$ a $b$ vía $c$ aunque tenga una probabilidad baja, puede tener un tiempo medio de acierto lo suficientemente grande como para superar la diferencia de probabilidad. A continuación se expone un ejemplo (siento no poder construir uno sencillo). Básicamente, al pasar de $a$ a $b$ podemos quedar "atrapados" durante algún tiempo en el subgrafo situado debajo del nodo $c$ y esto aumenta el tiempo medio de impacto $h_{ab}$ .

Denote por $p_{ab} \;(p_{ac})$ la probabilidad de caminar desde $a$ a $b \;(c)$ evitar $c \;(b)$ . Entonces,

\begin{align} p_{ab} &= 3\cdot \dfrac{1}{4}\cdot \dfrac{1}{2} + 3\cdot \dfrac{1}{4}\cdot \dfrac{1}{2}\cdot p_{ab} = \dfrac{3}{8} + \dfrac{3}{8} p_{ab} \\ \therefore\quad p_{ab} &= \dfrac{3}{5} \\ & \\ p_{ac} &= \dfrac{1}{4} + 3\cdot \dfrac{1}{4}\cdot \dfrac{1}{2}\cdot p_{ac} = \dfrac{1}{4} + \dfrac{3}{8} p_{ac} \\ \therefore\quad p_{ac} &= \dfrac{2}{5} \lt p_{ab}. \end{align}

Tiempos medios de golpe:

\begin{align} h_{ac} &= \dfrac{1}{4}\cdot 1 + 3\cdot\dfrac{1}{4}\cdot\dfrac{1}{2}(2 + h_{ac}) + 3\cdot\dfrac{1}{4}\cdot\dfrac{1}{2}(2 + h_{bc}) \\ &= \dfrac{7}{4} + \dfrac{3}{4} h_{ac} \qquad\qquad\text{since $h_{bc} = h_{ac}$} \\ \therefore\quad h_{ac} &= 7. \\ & \\ h_{ab} &= 3\cdot\dfrac{1}{4}\cdot\dfrac{1}{2}\cdot 2 + 3\cdot\dfrac{1}{4}\cdot \dfrac{1}{2}\cdot (2 + h_{ab}) + \dfrac{1}{4}(1 + h_{cb}) = \dfrac{7}{4} + \dfrac{3}{8} h_{ab} + \dfrac{1}{4} h_{cb} \\ \therefore\quad h_{ab} &= \dfrac{14}{5} + \dfrac{2}{5} h_{cb} \\ & \\ h_{cb} &= \dfrac{1}{6}(1 + h_{ab}) + \dfrac{1}{6}\cdot 1 + \dfrac{4}{6}(1 + h_{gb}) = 1 + \dfrac{1}{6}h_{ab} + \dfrac{2}{3}h_{gb} \\ & \\ h_{gb} &= \dfrac{1}{2}(1 + h_{cb}) + \dfrac{1}{2}(2 + h_{gb}) = \dfrac{3}{2} + \dfrac{1}{2}h_{cb} + \dfrac{1}{2}h_{gb} \\ \therefore\quad h_{gb} &= 3 + h_{cb} \\ & \\ h_{cb} &= 1 + \dfrac{1}{6} h_{ab} + 2 + \dfrac{2}{3} h_{cb} = 3 + \dfrac{1}{6} h_{ab} + \dfrac{2}{3} h_{cb} \\ \therefore\quad h_{cb} &= 9 + \dfrac{1}{2} h_{ab} \\ \therefore\quad h_{ab} &= \dfrac{14}{5} + \dfrac{2}{5}(9 + \dfrac{1}{2}h_{ab}) = \dfrac{32}{5} + \dfrac{1}{5} h_{ab} \\ \therefore\quad h_{ab} &= 8 \gt h_{ac}. \end{align}