Paseo aleatorio en gráfico de lollipop

Question

Hola estoy tratando de demostrar espera Golpear tiempo en la Paleta gráfica. Es una gráfica en la $n$ vértices con la camarilla en $n/2$ vértices y la ruta de acceso se unió a este. Vamos vértice $i$ ser un vértice en la camarilla, el vértice $j$ ser el vértice en el camino y la camarilla de cumplir, y $k$ ser el vértice en el otro extremo de la ruta. ¿Cuál es el $H(i,k)$$H(k,i)$. El resultado sólo puede ser asintótica.

Sé $H(i,k)=O(n^3)$$H(k,i)=O(n^2)$, pero no sé cómo terminar la prueba. Sé que $H(i,j)=n/2$ e al $t$ es el primer vértice en el camino, vecino de $j$,$H(i,t)=\frac{n/2}{P(j,t)}=\frac{n*(n+1)}{2}$, supongo.

Pero, ¿cómo puedo finalizar la prueba, y cómo puedo probar $H(k,i)$. Sé $H(k,j)=\frac{n^2}{4}$, pero ¿cómo puedo hacer $H(k,i)$ fuera de ella. Bueno espero sus comprensible, cualquier ayuda es apreciada. Juan.

Answer 1

Para $H(i,k)$, el promedio de bateo de tiempo de $k$ a partir de a $i$, hay un truco para simplificar los cálculos. Todos los estados de la camarilla (con la excepción de $j$) son equivalentes y se pueden resumir en un estado. Esto le da una caminata al azar en un lineal gráfico con la no-igualdad de probabilidades.

Yo uso $N$ en lugar de su $n/2$, y me re-etiquetar los escombros de la gráfica como $\{-1,0,1,2,\dots, N\}$, de modo que el estado $i$ está etiquetada $-1$, estado$j$$0$, y el estado $k$$N$.

Tenemos $$H(-1,N)=H(-1,0)+H(0,1)+H(1,2)+\cdots +H(N-1,N),$$ y los términos en el lado derecho son bastante fáciles de calcular. Para una caminata al azar en una camarilla tenemos $H(-1,0)=N-1$ ( $N$ , como lo escribió), y los demás pueden ser calculados usando $$H(i,i+1)=1+p(i,i-1)[H(i-1,i)+H(i,i+1)]\ \mbox{ for }\ 0\leq i<N,$$
y $$p(i,i+1)=\begin{cases}1/(N-1) & i=-1\\[5pt] 1/N & i=0\\[5pt] 1/2 & 1\leq i<N.\end{casos} $$

Si mis cálculos son correctos, el resultado final es $$H(i,k)=H(-1,N)=N^3+N-1.$$

Por ejemplo, he aquí el tiempo de espera para golpear $k$ de cada estado, al $N=3$.

---

Añadido: Siguiente joriki la sugerencia, he calculado $$H(k,i)=N^2+N+3.$$ Por ejemplo, he aquí el tiempo de espera para golpear $i$ de cada estado, al $N=3$.

Answer 2

Aquí es una manera alternativa de llegar a la conclusión acerca de la $H(i,k)$ sobre la base de los argumentos formulados en Juan de la pregunta. Como se mencionó, $H(i,t)=\Theta(n^2)$. Suponiendo que la ruta de acceso entre el $t$ $k$ es tomado por separado, el camino debería tomar otro$\Theta(n)^2$, hasta alcanzar los $k$. Pero en nuestro caso, se va a pasar a través de $t$ y volver a la camarilla de un número de veces. Basado en el tiempo de retorno para el extremo de una ruta de acceso ($2m$), podemos ver que esto sucederá $\Theta(n)$ veces, de dónde $H(i,k)=\Theta(n^3)$.

Este argumento puede encontrarse en la página 8 de Lovàsz de la encuesta.