A stopping time that gives the metric

Question

Let $\Omega$ a finite metric space with $\forall x,y,z\in \Omega:d(x,y)<d(x,z)+d(z,y)$. Does there exists a continuous-time Markov process $X$ on $\Omega$ such that $$\mathbb{E}_x(T_y)=d(x,y)$$ for all $x,y\in \Omega$ with $T_y:=\inf \{t\geq 0, X_t=y \}$ and $\mathbb{E}_x$ is for the conditon $X_0=x$?

Remark: since one can first go to $z$ and then to $y$ we have by the Markov property $\mathbb{E}_x(T_y)\leq \mathbb{E}_x(T_z)+\mathbb{E}_z(T_y)$ so the triangular inequality. But is it the only constraint?

So far, I tried to express $\mathbb{E}_x(T_y)$ using the resolvant of the stochastic matrix or to look for some connection with the resistance network (see for example the book "Markov Chain and Mixing Times" by Levin, Peres and Wilmer) but I haven't find anything very successful.

Answer 1

Suppose we have $n$ states $\{1, 2, \ldots, n\}$, and call transition rates $q_{ij}$. Set, as usual, $q_{ii} = -\sum_{j \ne i} q_{ij}$. Also, write $d_{ij}$ for $d(i,j)$. For $i \ne j$ we have $$ d_{ij} = \frac{1}{-q_{ii}} \biggl( 1 + \sum_{k \ne i} q_{ik} d_{kj} \biggr) , $$ that is, $$ 0 = 1 + \sum_k q_{ik} d_{kj} . $$ This system can be solved explicitly, and if I typed it correctly to Mathematica, when $n = 5$ and $$ d_{ij} = \min\{1 + |i - j|, 3\} , $$ we obtain $q_{24} = -\tfrac{1}{4} < 0$, which is not possible.

Mathematica code:

nn = 5;
d[i_, j_] := If[i == j, 0, Min[Abs[i - j] + 1, 3]];
eqns = Flatten@
   Table[If[i == j, 0 == Sum[q[i, k], {k, 1, nn}], 
     0 == 1 + Sum[q[i, k] d[k, j], {k, 1, nn}]], {i, 1, nn}, {j, 1, nn}];
vars = Flatten@Table[q[i, j], {i, 1, nn}, {j, 1, nn}];
q[2, 4] /. Solve[eqns, vars]

Answer 2

Note that clearly $d(x,x) = \mathbb E_x(T_x) = 0$, which is good. In general, even for reversible Markov chains, equivalently electrical networks, the Levin--Peres--Wilmer book is good for these, as is the Lyons--Peres Probability on Trees; for lecture notes, see the second half of these, written by Sousi.

There is the so-called hitting/commute-time identities (see Lyons--Peres, Proposition 2.20 and Corollary 2.21). These imply that $$ \mathbb E_x(T_y) = \sum \pi(z) v_{x \to y}(z) \quad \text{where} \quad \text{$v_{x \to y}$ is the voltage wrt to a unit current $x \to y$} $$ and $$ \mathbb E_x(T_y) + \mathbb E_y(T_x) = R_\mathrm{eff}(x,y) \sum c(e) \quad \text{where} \quad \text{$c(e)$ is the conductance of edge $e$ and $R_\mathrm{eff}$ is the "effective resistance"}. $$ For a more precise description, see one of the above references.

In short, it's pretty difficult to me to see how you are going get this voltage-sum to be the same when swapping $x$ with $y$. In fact, Question 5 here shows, for SRW, that $$ \mathbb E_x(T_y) = \textstyle \tfrac12 \sum_z \deg(z) \bigl( R_\mathrm{eff}(x,y) + R_\mathrm{eff}(y,z) - R_\mathrm{eff}(x,z) \bigr). $$ In the SRW case, $\pi(z) = \deg(z) / \sum_u \deg(u)$ and the conductances are all units. Replacing $\deg$ appropriately, you can get the more general formula for any reversible Markov chain.

Of course, if you define $d$ via the commute time, eg $$ d(x,y) := \mathbb E_x(T_y) + \mathbb E_y(T_x) \qquad \text{(or half this, as you see fit)}, $$ then you're in business.

Answer 3

In the case that $X$ is strong Markov and $\mathbb E_x[T_y] = d(x,y) < \infty$ for all $x,y\in \Omega$ we have the following. Take $x,y,z\in\Omega$. \begin{align*} \mathbb E_x[T_y] & = \mathbb E_x[\mathbb E_x[T_y | \mathscr F_{T_z}]] \\ & = \mathbb E_x[\mathbb E_x[T_y - T_z | \mathscr F_{T_z}] + T_z] \\ & = \mathbb E_x[\mathbb E_z[T_y] + T_z] \\ & = \mathbb E_z[T_y] + \mathbb E_x[T_z]. \end{align*} That is, $$ d(x,y) = d(z,y) + d(x,z). $$ This contradicts your requirement that $$ d(x,y) < d(z,y) + d(x,z). $$ This requirement also necessitates the assumption that $\mathbb E_x[T_y] = d(x,y) < \infty$ for all $x,y$. You might have luck with a Markov process which isn't strong Markov, since they can have more exotic behaviour with respect to $\mathscr F_0$-measurable events.