First Passage Percolation on Trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:53:11Z http://mathoverflow.net/feeds/question/76224 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76224/first-passage-percolation-on-trees First Passage Percolation on Trees ght 2011-09-23T17:56:42Z 2011-09-24T15:11:48Z <p>Let $T$ be a rooted Galton-Watson random tree generated accordingly to a probability distribution $\mu$. Now assign to each edge $e$ a random non-negative weight $w_e$ distributed a accordingly to a distribution $\nu$. We also assume that the weights are independent for different edges.</p> <p>Let $T_{n}$ be the collection of nodes at (hop) distance $n$ from the root. For each $v\in T_{n}$, let $P_{v}$ denote the path from the root to $v$. Define</p> <p>$$Z_{v}=\sum_{e\,\in P_{v}}{\,w_e}.$$</p> <p>Now for each $n$ let $Y_{n}=\min_{v\in T_{n}}Z_{v}$. It was proved in <a href="http://www.springerlink.com/content/q71713275vk42443/" rel="nofollow">Limit distributions for minimal displacement of branching random walks</a> that the sequence of random variables $$\{Y_{n}-\mathbb{E}(Y_{n})\}_{n\geq 1}$$ is tight.</p> <p>My question are: </p> <ul> <li><p>Is it known what is the behavior of $\mathbb{E}(Y_{n})$ as $n$ increases in terms of $\mu$ and $\nu$?</p></li> <li><p>Is it known for the case $\mu=\delta_{k}$, i.e. when $T$ is a $k+1$ regular tree?</p></li> </ul> http://mathoverflow.net/questions/76224/first-passage-percolation-on-trees/76243#76243 Answer by Pascal Maillard for First Passage Percolation on Trees Pascal Maillard 2011-09-23T23:19:44Z 2011-09-24T15:11:48Z <p>This paper by Dekking and Host is quite old and much has been done in this area since. Today we know that under reasonable assumptions, there are constants $a\in\mathbb{R}$, $b\ge 0$, such that $E(Y_n) = an + b \log n + O(1)$. How to get the constant $a$ was known for quite a long time, see</p> <p>Biggins, J. D. (1977). Chernoff’s Theorem in the Branching Random Walk. Journal of Applied Probability, 14(3), 630. doi:10.2307/3213469</p> <p>For the second term and for almost sure behaviour of $Y_n$, see</p> <p>Hu, Y., &amp; Shi, Z. (2009). Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. The Annals of Probability, 37(2), 742-789. doi:10.1214/08-AOP419</p> <p>For the definite answer for the law of $Y_n$ in the non-lattice case, see</p> <p>Aïdékon, E. (2011). Convergence in law of the minimum of a branching random walk. Retrieved from <a href="http://arxiv.org/abs/1101.1810" rel="nofollow">http://arxiv.org/abs/1101.1810</a></p> <p>Note that all of this was already known long before for branching Brownian motion, see the references in the respective articles.</p> <p>UPDATE: I forgot to add the important reference </p> <p>Addario-Berry, L., &amp; Reed, B. (2009). Minima in branching random walks. The Annals of Probability, 37(3), 1044-1079. doi:10.1214/08-AOP428 </p> <p>Here, the authors show the above-mentioned result for $E[Y_n]$ in almost complete generality, and exponential tails for $Y_n−E[Y_n]$ as well</p>