Hormigas en movimiento de vértice a vértice de un poliedro

Question

En un poliedro regular, hay una hormiga en cada vértice. En una ronda, cada hormiga camina a un lado de vértice, cada vértice adyacente, con igual probabilidad. Deje $P(r)$ probabilidad de que después de r rondas, cada vértice todavía tiene exactamente una hormiga.

Qué $P(r)$ convergen como r tiende a infinito?

¿Cómo funciona la función de comportarse? Es monótono?

Por ejemplo, $P(1)$ de tetraedro es $\frac{1}{9}$; $P(1)$ de octaedro es $\frac{5}{256}$.

Answer 1

Usted tiene una cadena de Markov con los estados, siendo la distribución de los números de hormigas en cada vértice. Ciertamente, la probabilidad de cada distribución se reunirán, por lo que específicamente $P(r)$ convergerán para algo. Si las probabilidades de transición entre los estados que puede calcular la distribución de equilibrio. Un tetraedro es muy sencilla ya que los vértices están conectados de modo que todos los que nos preocupamos es la lista de los números en cada vértice. Usted puede hacer una matriz de probabilidades, como $(4,0,0,0)$ $(4,0,0,0)$ con una probabilidad de $3/81$, $(3,1,0,0)$ con una probabilidad de $24/81$, $(2,2,0,0)$ con una probabilidad de $18/81$ $(2,1,1,0)$ con una probabilidad de $36/81$. Hacer de la totalidad de la matriz, encontrar el autovalor dominante y su correspondiente vector propio y usted tendrá la limitación de la distribución. Luego, puede multiplicar la matriz por la puesta en marcha de la probabilidad de $1$ $(1,1,1,1)$ y ver si la probabilidad nunca disminuye.

Answer 2

Para poliedros donde hay una cara con un número impar de vértices, como la triangular en las caras de un octaedro, no es necesario el pleno de la cadena de Markov de tratamiento para ver lo que sucede. Sólo tener en cuenta la naturaleza de la "limitación" de la distribución. Dicen que es la versión de el problema con un octaedro (6 vértices). A lo largo de muchos cambios cada hormiga tiene la misma probabilidad de que se ocupa de cualquier vértice de modo que no se $6^6$ igualmente probables ant-vértice permutaciones. Fuera de estos, $6!$ permutaciones tienen cada hormiga en otro vértice de modo que su convergentes valor de $P(r)$$6!/6^6=5/324=0.0154...$ . Claramente para $n$ vértices de la convergentes valor de $P(r)$$n!/n^n$, si tenemos impar de vértices de las caras.

Como se señaló en los comentarios (Josh B.), este enfoque no cuando los rostros, todos tienen un número par de vértices, para, a continuación, los vértices se dividen en dos alternante de los grupos y la convergencia a una distribución aleatoria no se logra.

Ross Millikan sugiere un método para lidiar con este alternante caso. La etiqueta de un conjunto de alternante vértices a y el otro B. empezamos con igual número de hormigas en los vértices y las hormigas en los vértices B ($n/2$ a cada uno) para tener una oportunidad de conseguir todas las hormigas en diferentes vértices. Si esta restricción se satisface, entonces en el caso limitante tenemos una probabilidad de $((n/2)!)/((n/2)^{n/2})$ para las hormigas ser distribuido en la vértices, e igual para el factor B los vértices. Esto da un total de probabilidad $P(\infty)=((n/2)!)^2/((n/2)^n)$ para el alternante caso. Para un cubo con todas las caras que tienen cuatro vértices y $n=8$, el resultado es $(4!)^2/(4^8)=9/1024=0.008789...$ .