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.
The values $k\leq 20$ aren't too big to brute force. Because you need to come back, you only have to consider the graph up to $\frac{k}{2}$ distance to the origin. Then remove the origin and for each pair of neighbors of the origin count $k-2$-walks on that graph starting from first and ending in second. Sum those up and that's your answer. We get
2 : 3
4 : 6
6 : 30
8 : 180
10 : 1188
12 : 8322
14 : 60714
16 : 456174
18 : 3504630
20 : 27398106
Here's the Sage code I used:
def f(k):
if k<2: return 0
g = Graph()
lim = k//2
for y in range(-lim, lim+1):
for x in range(-lim, lim+1):
g.add_edge((x,y), (x+1, y))
if (x+y)%2==0: g.add_edge((x,y), (x,y-1))
g.delete_vertex((0,0))
vs = list(g.vertices())
origNbs = [vs.index(v) for v in [(-1,0), (1,0), (0,-1)]]
A = g.adjacency_matrix()
A = A^(k-2)
return sum(A[vI][vJ] for vI in origNbs for vJ in origNbs)
for k in range(2, 21, 2):
print (k, ": ", f(k))
I'm probably exaggerating on the $y$-range because you need two steps to move a level, but it's not too slow even like that.
Best Answer
For this problem there are just three states: In state $S_1$ the ant sits at the starting position, in state $S_2$ the ant sits on one of the four adjacent positions, and in state $S_3$ the ant sits at the vertex opposite to the starting vertex. Denote by $${\bf p}(n)=\left[\matrix{p_1(n)\cr p_2(n)\cr p_3(n)\cr}\right]\qquad(n\geq0)$$ the probabilities that after $n\geq0$ steps the ant is in state $S_i$ $\>(1\leq i\leq3)$. Then ${\bf p}(0)=(1,0,0)$. The rules of the game then say that $${\bf p}(n+1)=A\>{\bf p}(n)\qquad(n\geq0)$$ with $$A:=\left[\matrix{0&{1\over4}&0\cr 1&{1\over2}&1\cr0&{1\over4}&0\cr}\right]\ .$$ This is the essential step. E.g., the second column of $A$: When the ant is in state $S_2$ then it will move to state $S_1$ with probability ${1\over4}$, remain in state $S_2$ with probability ${1\over2}$, and move to state $S_3$ with probability ${1\over4}$. We now have to compute $p_1(6)$, which is the first component of $$A^{6}\left[\matrix{1\cr0\cr0\cr}\right]=\left[\matrix{{11\over64}\cr{21\over32}\cr{11\over64}\cr}\right]\ .$$