I am looking at different configurations of particles on a $d$-ary tree with $n$ nodes and $lfloor frac{n}{2}rfloor$ particles. If we start at a configuration $x$, an edge is selected uniformly at random and if that edge has one particle and one empty space, then the particle and empty space are swapped. If the selected edge has two particles or no particles, then we remain at $x$. In this case, I am trying to find a metric $rho (x,y)$ between configurations $x$ and $y$ that differ along a single edge such that $(1)$ is satisfied.

$$mathbb{E} (rho(X_1,Y_1))-rho(x,y) leq 0 tag{1}$$

where $X_1,Y_1$ correspond to one move starting from $x,y$ respectively and $mathbb{E}$ is the expectation. The following figure gives an example for $d=2$. Notice that $x,y$ differ only along one edge.

For the above figure,

$$mathbb{E} (rho(X_1,Y_1))-rho(x,y) = -frac{1}{n-1}rho(x,y)+frac{d-1}{n-1}(rho(x,y)+rho(y,y^{+}))+frac{d}{n-1}(rho(x,y)+rho(x,x^{+}))+frac{1}{n-1}(rho(x,y)+rho(y,y^{-})) tag{2}$$

Because we decrease the distance in one move by $rho(x,y)$ only when we select the edge along which $x,y$ differ, which happens with probability $frac{1}{n-1}$ and in all other cases we increase the distance after one move. Let $x,y$ differ at height $h$ from the root. If we select another edge at height $h$ apart from the edge along which $x,y$ differ, which happens with probability $frac{d-1}{n-1}$, then $x$ remains at $x$ and $y$ moves to $y^{+}$ and that explains the second term in $(2)$. If we select an edge at height $h+1$, which happens with probability $frac{d}{n-1}$, then $x$ moves to $x^+$ and $y$ remains at $y$ and that explains the third term in $(2)$. Similarly, if we select an edge at height $h-1$, which happens with probability $frac{1}{n-1}$, then $x$ remains at $x$ and $y$ moves to $y^-$ and that explains the fourth term in $(2)$.

My attempt: I have tried $rho(x,y)=h$ and $rho(x,y)=alpha^{h}$ for $alpha>1$ a constant but both of them did not satisfy $(1)$ mainly for the reason that the distance increases in too many ways while the distance decreases only when we select one particular edge i.e. the one along which $x,y$ differ. Any thoughts about how to find $rho(x,y)$? Or how to pose this as a different problem?