On a regular polyhedron, there is one ant on each vertex. In one round, every ant walks to an adjacent vertex, each adjacent vertex with equal probability. Let $P(r)$ be probability that after r rounds, each vertex still has exactly one ant.
Does $P(r)$ converge as r tends to infinity?
How does the function behave? Is it monotonic?
For example, $P(1)$ of tetrahedron is $\frac{1}{9}$; $P(1)$ of octahedron is $\frac{5}{256}$.
Best Answer
You have a Markov chain with the states being the distribution of numbers of ants on each vertex. Certainly the probability of each distribution will converge, so specifically $P(r)$ will converge to something. If you work out the transition probabilities between all the states you can compute the equilibrium distribution. A tetrahedron is quite simple because the vertices are all connected so all we care about is the list of numbers at each vertex. You can make a matrix of probabilities, like $(4,0,0,0)$ goes to $(4,0,0,0)$ with probability $3/81$, to $(3,1,0,0)$ with probability $24/81$, to $(2,2,0,0)$ with probability $18/81$ and to $(2,1,1,0)$ with probability $36/81$. Make the whole matrix, find the dominant eigenvalue and its corresponding eigenvector and you will have the limiting distribution. You can then multiply the matrix by the starting probability of $1$ in $(1,1,1,1)$ and see if the probability ever decreases.