5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\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
    Commented 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$
    – Pascal Maillard
    Commented 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
    Commented 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$
    – Pascal Maillard
    Commented 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
    Commented Sep 24, 2011 at 17:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .