Hay un hexágono y una hormiga está realizando un paseo aleatorio por las aristas y líneas que unen el centro y el vértice con igual probabilidad para elegir la siguiente arista/línea. ¿Cuál es el número esperado de pasos (una arista/línea equivale a un paso) que necesita hasta llegar de nuevo al centro?
Hay una situación similar pregunta aquí pero tenemos un centro en este caso.
Respuestas
¿Demasiados anuncios?
2 enfoques:
1) Cadenas de Markov. Su problema puede ser modelado por una cadena de Markov donde cada vértice es un estado. Su Matriz de Transición se parece (asumiendo que el centro es un estado absorbente):
$$ TM=\begin{pmatrix} 0& 0& 0& 0& 0& 0& 0\\ 1/3& 0 & 1/3& 0& 0& 0& 1/3\\ 1/3& 1/3& 0& 1/3& 0& 0& 0\\ 1/3& 0 & 1/3& 0& 1/3& 0& 0\\ 1/3& 0 & 0& 1/3& 0& 1/3& 0\\ 1/3& 0 & 0& 0& 1/3& 0& 1/3\\ 1/3& 1/3 & 0& 0& 0& 1/3& 0\\ \end{pmatrix} $$
donde estoy etiquetando la primera fila/columna como el centro y las otras filas/columnas como el resto de los vértices en el sentido de las agujas del reloj desde la parte superior.
Entonces para calcular los pasos medios para volver al centro desde cada vértice se puede calcular:
$$(Id-TM)^{-1}\begin{pmatrix} 0\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \end{pmatrix}=\begin{pmatrix} 0\\ 3\\ 3\\ 3\\ 3\\ 3\\ 3\\ \end{pmatrix}$$
Así que se necesitan 3 pasos para llegar desde cualquier vértice hasta el centro más el paso para salir del centro así que finalmente necesita 4 pasos en total .
2) Serie. Como se ha comentado anteriormente y observando la simetría del problema, las cadenas de Markov parecen una exageración.
Puede calcular $$1+\sum_{i=1}^{\infty}iP(i)$$ donde $$P(i)=\frac{1}{3}\left(\frac{2}{3}\right)^{i-1}$$ ya que tiene 1 de las tres posibilidades de volver al paso $i$ después de haber recorrido los vértices exteriores para $i-1$ pasos.
Usando eso $$\sum_{i=1}^{\infty}ik^{i-1}=\left(\sum_{i=0}^{\infty}k^{i}\right)'=\frac{1}{(1-k)^2} $$ se obtiene $$1+\sum_{i=1}^{\infty}iP(i)=4$$ como en el caso anterior.
CodingBytes
Puntos
102
Denota por $E_{\rm rim}$ el número esperado de pasos adicionales cuando la hormiga se sitúa en un vértice exterior. A continuación, $$E_{\rm rim}=1+{2\over3}E_{\rm rim}\ ,$$ por lo que $E_{\rm rim}=3$ y el número esperado al inicio es $E_0=1+E_{\rm rim}=4$ . Por cierto: La información de que el borde es un hexágono es superflua; podría ser cualquier $n$ -gon con $n\geq2$ .
Bram28
Puntos
18
La hormiga dará 1 paso para salir, y luego puede dar 1 paso para volver a entrar, o puede dar 1 paso por el exterior y luego volver a entrar, o ... En otras palabras, dará 1 paso para salir más 1 o más pasos para volver a entrar.
Por lo tanto, dejemos que $P(i)$ sea la probabilidad de tomar $i$ pasos para volver a entrar. Entonces, el número esperado de pasos para volver a entrar es el número de pasos $i$ multiplicado por la probabilidad de $P(i)$ para todos $i$ que va de 1 a infinito. Añade 1 por el paso inicial para salir, y obtienes que el número esperado de pasos es:
$1+\sum^\infty_{i=1} i*P(i)$ (por lo que será una serie geométrica)
En cuanto a $P(i)$ Lo dejaré a tu criterio, pero Pieter te ha dado una buena pista.
