User nathanael berestycki - MathOverflow

Markov chains: invariant measures and explosion

2012-08-21T16:47:18Z

The following seems like such an elementary question, but I didn't get anywhere with it.

Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (so one which explodes in finite time almost surely.) My question is: what does an invariant measure represent?

To fix ideas, consider the Markov chain on $S={0,1,\ldots},$ which moves to the right with probability $2/3$ and to the left with probability $1/3$, and has total jump rate $q_i = 3^{i}$ at state $i \ge 1$. (To make computations nice, say that for $i=0$ the chain can only go to the right with total rate $q_0 = 2/3$).

Then it is elementary to check that this chain admits an invariant measure $$ \pi_i = \pi_0 (\frac{2}{3})^i, $$ obtained by solving the detailed balance equations. Of course the chain is also transient. Elementary Markov chain theory immediately implies that the chain is explosive, meaning that it will accumulate an infinite number of jumps in finite time almost surely.

The questions that is troubling me (even in such a basic example!) is the following: what does $\pi$ represent for this chain?

The following is a natural guess. Assume that the chain starts at $X_0$ distributed according to $\pi$. Then at the first explosion time $\zeta_0$, let the chain come back at an independent position also chosen according to $\pi$. Keep going in this fashion forever: each time the chain explodes, let it come back at a position sampled from $\pi$.

Question 1. Let $t>0$ be arbitrary. Is it true that $X_t$ has the law of $\pi$?

Question 2. If we start and restart the chain after each explosion with some given measure $\nu$ (which could be distinct from $\pi$), does $X_t$ converge in distribution to a certain measure $\mu$ as $t\to \infty$ (which could for instance be some mixture of $\pi$ and $\nu$) ?

Answer by Nathanael Berestycki for Is the maximum tree-path length distributed lognormally (in the limit) ?

2011-12-31T15:35:57Z

Unless I misunderstood your question, this can be entirely rephrased in terms of branching random walks. This goes as follows: at time 0 there is 1 individual at position 0. Each individual gives birth to two descendants, whose position is the position of the parent plus a jump, where all jumps are i.i.d. random variable. You are asking about the maximum position at time $k$, $M_k$.

This is a much studied problem, with deep links to traveling wave partial differential equations such as the Fisher-KPP equation. (Eg, in the space-time continuous case where branching random walk is replaced by branching Brownian motion, the function $u(t,x) = \mathbb{P}(M_t >x)$ solves the KPP equation with initial condition $u(0,x) = 1_{x<0}$.)

See this recent paper http://front.math.ucdavis.edu/1101.1810 by Elie Aidekon, which provides complete answers to your question under minimal assumptions on the jump distribution. The main result is then that $M_k - ck + (3/2) \log k$ converges to a random variable, where $c$ is a constant that is easy to compute. The distribution of the limiting random variable doesn't have to be either Gumbel or lognormal.

In the space-time continuous case where branching random walk is replaced by branching Brownian motion, this result is a famous result originally due to Maury Bramson (1983): Convergence of solutions of the Kolmogorov equation to travelling waves. Mem. Amer. Math. Soc. 44, no. 285.

Correlations in last-passage percolation

2011-12-18T16:21:44Z

Consider the last passage percolation model on $\mathbb{Z}^2$ with, say, geometric weights on each edge. By a landmark result of Johansson (http://arxiv.org/abs/math/9903134), we know that if $T_n(\alpha)$ is the passage time (or distance) between the origin and the point of coordinates $(\alpha n, n)$, then $$ \frac{T_n(\alpha) - \omega(\alpha) n}{\sigma(\alpha)n^{1/3}}\to X, $$ where $X$ has the Tracy-Widom distribution. Here $\omega(\alpha), \sigma(\alpha)$ are two constants whose value is known and is not important for this question.

I am interested in the following natural question:

Q1) Given $\alpha, \beta$, and letting $\gamma_n(\alpha)$ denote the geodesic between 0 and $(\alpha n, n)$, how many edges do $\gamma_n(\alpha)$ and $\gamma_n(\beta)$ share?

Intuitively, one possible way to approach this question is to first ask

Q2) How big is the covariance between between $T_n(\alpha)$ and $T_n(\beta)$?

The reason why these two questions seem related is that one would expect $\text{cov}(T_n(\alpha), T_n(\beta)) $ to be roughly proportional to the number of edges on $\gamma_n(\alpha)\cap \gamma_n(\beta)$. (At least this is what happens for deterministic paths).

Presumably, Johannson's result tells us that var$(T_n(\alpha))$ is of order $n^{2/3}$ (though it's not a straightforward consequence of that result), so Cauchy-Schwarz implies that the covariance is at most of order $n^{2/3}$. This would suggest that $|\gamma_n(\alpha)\cap \gamma_n(\beta)|$ is at most of order $n^{2/3}$. However, it is hard to believe that this is sharp!

Does anyone know if these questions have been studied ? And what if we only know that $\text{var} (T_n(\alpha)) = o(n)$ (as in this paper, http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aop/1068646373, by Benjamini Kalai and Schramm), does it follows that $|\gamma_n(\alpha) \cap \gamma_n(\beta)| = o(n)$?

Answer by Nathanael Berestycki for Comparing two measures on trees on $n$ vertices

2011-12-17T09:55:58Z

It's a nice question. The following is not an answer but too long to put in comment. I think in general you want to ask "how much can you tell of the underlying graph given a sample from the uniform spanning tree". There is a great algorithm due to David Wilson to sample the UST, which consists in growing the tree by successively running loop-erased random walks. See eg http://en.wikipedia.org/wiki/Loop-erased_random_walk.

Here I think you can try to generate the graph at the same time as the loop-erased random walks, which means that for a while you can couple a loop-erased random walk on the complete graph with one on $G(n,p)$. Not sure this method will allow you to go all the way to the connectivity threshsold $p = (1+ \epsilon) \log n / n$, though. Perhaps it would be easier to start with $p=1/2$ !

Answer by Nathanael Berestycki for Stopping time of a Markov chain

2011-12-17T09:44:42Z

I think your approach is generally correct. I will note that for your first phase, so long as $A(t) < \epsilon n$, the process $A(t)$ is well approximated by a branching process where the offspring distribution is 1 + Poisson (1). Since this has mean equal to 2 and cannot get extinct, the Kesten-Stigum theorem says that at time $t$, $A(t)$ really is of order $W 2^t$ for some random variable $W>0$. You see indeed that it thus takes $t =\log_2 n $ to make this equal to $n$, so phase 1 takes $\log_2 n $ + a random variable whose tail probabilities are uniformly bounded in $n$, as needed.

In phase 2, you can either use the ODE approach with Ethier-Kurtz type of arguments, as suggested by QAMS, or simply note the following. The probability that a Binomial $(N,p)$ deviates from its mean $Np$ (say, is less than $Np/2$) is exponential in $Np$. This means that, over a logarithmic number of trials, the probability you would observe one such deviations tends to 0. Hence during phase 2, you know that each step you add at least a $(N-A(t))\epsilon/2$ individuals, which shows that phase 2 indeed only takes a constant number of steps with overwhelming probability.

Phase 3 is a bit more delicate (you want to avoid a coupon-collector effect where collecting the last individual takes more time than it should), but I think this sort of reasoning should help you get started...

Answer by Nathanael Berestycki for A percolation problem

2011-12-02T22:56:40Z

This is a nice model. Call an edge increasing if it is oriented in the direction going away from the origin, and dercreasing otherwise. Of course increasing edges form a usual bond percolation model. For $p<1/2$ we know, by duality, that there exists a closed dual contour. So no increasing edge can cross that contour and hence the origin does not percolate. So $p_c \ge 1/2$ in this model, in the sense that for all $p<1/2$ there is $a.s.$ no infinite cluster.

For $p>1/2$ I agree it seems intuitively likely that the origin does percolate. For instance, is it known whether there always exist northeast paths in supercritical bond percolation in $\mathbb{Z}^2$?

At any rate, a first step would be to prove that the critical probability is $<1$, I think. (By the way, it is not immediately obvious that $p_c$ is well-defined, as there isn't any obvious monotonicity).

Answer by Nathanael Berestycki for Limit shape for fixed-perimeter lattice polygons

2011-11-30T22:03:14Z

The closest thing that comes to mind is the uniform measure on (self-avoiding) polygons with given perimeter. For this there are numerous predictions by physicists: eg, it should be related in the scaling limit to SLE with $\kappa= 8/3$ and so have a fractal dimension of $4/3$

Here the uniform measure is not (or at least, not obviously) the invariant measure of the chain, but maybe on sufficiently large scales it is not so different?

Comment by Nathanael Berestycki

2012-08-25T07:49:32Z

It is a classical (and surprising) feature of continuous Markov chains that they can have an invariant measure while being transient. See, for instance, section 3.5 in James Norris' book on Markov chains. (Notice that the definition of invariant measure is the usual one and does not require the process to be recurrent or non-explosive). In any case, no matter how you would call such a measure, I hope you'll agree it is interesting to know what it means for the process...

Comment by Nathanael Berestycki

2012-08-25T07:46:16Z

Dear Robert, Thanks for your comments and sorry for long time in response. I am not totally comfortable with the derivation of your equation. I always thought this process would satisfy the Kolmogorov backward and forward equations - without being the minimal solution. See, for instance, section 2.9 in James Norris' book on Markov chains. But you may well be right - in which case the question of "what is this invariant measure" is even more puzzling to me !

Comment by Nathanael Berestycki

2011-12-20T22:05:41Z

I don't know if this is what you are looking for, but the left-hand side in your last identity is called the Dirichlet form $\mathcal{E}(f,g)$. For a Markov chain on a countable space and with invariant measure $\pi$, (not necessarily reversible), it is always true that $$\mathcal{E}(f,g) = \sum_{x,y} \pi(x) P(x,y) g(x) \nabla_{x,y} f.$$ But this is an easy calculation, so presumably you are aware of it.

Comment by Nathanael Berestycki

2011-12-19T10:21:08Z

Hi James ! Thanks, very helpful. I guess the story about competing interface in FPP (which results in random slope) shows indeed that there is a nonzero probability that the geodesics have no edge in common at all. That is somehow slightly counterintuitive to me, you'd expect the geodesics to go get the same goodies for a while, before they diverge... So is the covariance $O(1)$ as well?

Comment by Nathanael Berestycki

2011-12-19T10:12:54Z

very cool picture ! what did you use to generate it?

Comment by Nathanael Berestycki

2011-12-05T08:23:22Z

Yes, I agree ! Very interesting...

Comment by Nathanael Berestycki

2011-12-03T11:29:56Z

@Peter: yes, I agree that my comment above is not correct: the model is not strictly equivalent to finding monotone paths. But the argument I outlined initially to show $p_c \ge 1/2$ is still valid, do you agree? ps. sorry to be answering here, but this is the only place I am allowed to put comments...

Comment by Nathanael Berestycki

2011-12-03T08:35:14Z

Come to think of it, the question can be rephrased in terms of standard percolation. It's fairly easy to check that the question is equivalent to asking for the existence of monotone paths (by which I mean, paths for which the x and y coordinates are monotone functions of time, e.g. that travel only in the North and East direction). I think the problem is clearer this way. Phrased this way, it is clear that the problem is monotone in $p$ so $p_c$ is well-defined, and moreover it is obvious that $p_c \ge 1/2$.

Comment by Nathanael Berestycki

2011-12-02T22:28:17Z

@ Vincent : Thanks ! The version you suggest is indeed more natural in that it is easy to check the uniform measure is reversible. There should be a way to say that the invariant measures of both chains are pretty similar! (ps. sorry the comment doesn't really fit here but that's the only place MO will allow me to add a comment ... )