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.

  • $\begingroup$ Do you mean "continuous time Markov process"? If $X$ is actually continuous, i.e. has continuous paths, then it can only be constant. $\endgroup$ – Nate Eldredge Feb 21 '20 at 15:39
  • $\begingroup$ Is "continuous Markov process" a "continuous-time Markov process"? $\endgroup$ – Mateusz Kwaśnicki Feb 21 '20 at 15:39
  • $\begingroup$ Yes "continuous-time", I edited the question. $\endgroup$ – RaphaelB4 Feb 21 '20 at 15:49
  • $\begingroup$ The are further restrictions — see my answer below — but I have no idea what they are, the counter-example given in my answer does not provide any insight. An unrelated question: why on earth would one call the state space of a Markov chain $\Omega$? $\endgroup$ – Mateusz Kwaśnicki Feb 23 '20 at 21:41

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]

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.


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.

  • 1
    $\begingroup$ In the displayed equation, the third equality is wrong: we have $\mathbb{E}_x[T_y \circ \theta_{T_z} | \mathscr{F}_{T_z}] = \mathbb{E}_z[T_y]$ a.s., but $T_y \circ \theta_{T_z} = T_y - T_z$ only on the event $\{T_y > T_z\}$. Also, there are extremely few functions that satisfy $d(x,y) = d(x,z) + d(z,y)$ for every triple $x, y, z$... $\endgroup$ – Mateusz Kwaśnicki Mar 2 '20 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.