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?


1 Answer 1


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 http://arxiv.org/abs/1101.1810

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

  • $\begingroup$ 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? $\endgroup$
    – ght
    Sep 24, 2011 at 12:02
  • $\begingroup$ @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 $\endgroup$ Sep 24, 2011 at 13:20
  • 1
    $\begingroup$ @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? $\endgroup$
    – ght
    Sep 24, 2011 at 16:08
  • $\begingroup$ 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). $\endgroup$ Sep 24, 2011 at 16:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – ght
    Sep 24, 2011 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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