Ants moving from vertex to vertex on a polyhedron 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}$.
 A: 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.
A: For polyhedra where there is a face with an odd number of vertices, like the triangular faces of an octahedron, you don't need the full Markov chain treatment to see what happens.  Just consider the nature of the "limiting" distribution.  Say it's the version of the problem with an octahedron (6 vertices). Over many shifts each ant has an equal probability of occupying any vertex so that there are $6^6$ equally probable ant-vertex permutations.  Out of these, $6!$ permutations have each ant on a different vertex so your converged value of $P(r)$ is $6!/6^6=5/324=0.0154...$ .  Clearly for $n$ vertices the converged value of $P(r)$ is $n!/n^n$, if we have odd-vertex faces.
As pointed out in the comments (Josh B.), this approach fails when the faces all have an even number of vertices, for then the vertices get split into two alternant groups and the convergence to a random distribution is not achieved.
Ross Millikan suggests a method to deal with this alternant case.  We label one set of alternant vertices A and the other set B.  We start with equal numbers of ants on A vertices and ants on B vertices ($n/2$ apiece) to have any chance of getting all ants on separate vertices.  If this constraint is satisfied, then in the limiting case we have a probability of $((n/2)!)/((n/2)^{n/2})$ for ants being equally distributed on the A vertices, and an equal factor for the B vertices.  This gives a total probability $P(\infty)=((n/2)!)^2/((n/2)^n)$ for the alternant case.  For a cube with all faces having four vertices and $n=8$, the result is $(4!)^2/(4^8)=9/1024=0.008789...$ .
