MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

$$ Z_{v}=\sum_{e\\,\in P_{v}}{\\,w_e}. $$

Now for each $n$ let $Y_{n}=\min_{v\in T_{n}}Z_{v}$. It was proved in Limit distributions for minimal displacement of branching random walks that the sequence of random variables $$ \{Y_{n}-\mathbb{E}(Y_{n})\}_{n\geq 1} $$ is tight.

My question are:

  • Is it known what is the behavior of $\mathbb{E}(Y_{n})$ as $n$ increases in terms of $\mu$ and $\nu$?

  • Is it known for the case $\mu=\delta_{k}$, i.e. when $T$ is a $k+1$ regular tree?

share|cite|improve this question

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

Biggins, J. D. (1977). Chernoff’s Theorem in the Branching Random Walk. Journal of Applied Probability, 14(3), 630. doi:10.2307/3213469

For the second term and for almost sure behaviour of $Y_n$, see

Hu, Y., & 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

For the definite answer for the law of $Y_n$ in the non-lattice case, see

Aïdékon, E. (2011). Convergence in law of the minimum of a branching random walk. Retrieved from

Note that all of this was already known long before for branching Brownian motion, see the references in the respective articles.

UPDATE: I forgot to add the important reference

Addario-Berry, L., & Reed, B. (2009). Minima in branching random walks. The Annals of Probability, 37(3), 1044-1079. doi:10.1214/08-AOP428

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

share|cite|improve this answer
Thank you for the references. Can you please provide us with more details on the constants $a$ and $b$? For instance, what are the values of these constants for the $k$-regular tree? – ght Sep 24 '11 at 12:02
@ght: For the first order, it is basically an extension of Cramer's theorem. For a tree where each node has $k$ children: Define $\varphi(\theta) = \log k + \log E[e^{-\theta w}]$ for $\theta \ge 0$ and $= +\infty$ for $\theta < 0$, with $w\sim \nu$, where we assume that $\varphi(\theta) < \infty$ for some $\theta > 0$. Then define the rate function $I(x) = \sup_\theta [-x \theta - \varphi(\theta)]$. Now $a = \inf(x:I(x) < 0)$. The constant $b$ happens to be $3/(2\theta_0)$, where $\theta_0$ is the maximizer in the definition of $I(x)$. Please recheck all these formulae,I wrote them by heart – Pascal Maillard Sep 24 '11 at 13:20
@Pascal: Then is $\theta_{0}$ is the value such that $I(\theta_{0})\geq I(\theta)$ for all $\theta\geq 0$? In what of the references are these formulas proved? – ght Sep 24 '11 at 16:08
No, $\theta_0$ is the value at which the supremum in the definition of $I(x)$ is attained, i.e. $I(x)=−x\theta_0−\varphi(\theta_0)$. If no such value exists, then $\theta_0=+\infty$. This is proven implicitely in all the newer references, usually they would already assume that $a=0$ and $\theta_0=1$, which can be obtained by a linear transformation of the process (which is very instructive to carry out by hand). – Pascal Maillard Sep 24 '11 at 16:35
@Pascal: Is it clear that exists $\theta_{0}$ such that $I(x)=−x\theta_{0}−\varphi(\theta_{0})$? Also can you please point me to an explicit Lemma/Theorem where these results are proved? Doing a rapid search on the references you mentioned before I couldn't find any of these statements. – ght Sep 24 '11 at 17:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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