Size-Biased Galton Watson Tree.

434 Views Asked by At

First of all, i am not sure whether this question belongs here or to stack overflow. Let me write here, first, i will give a definition of size-biased distribution. then i will give definition of size-biased Galton-Watson Tree that is defined by Lyons, Pemantle and Peres [1995]. Warning: A lot of part is taken from lecture notes of Zhan Shi(Random Walks and Trees). Let $\nu $ be a distribution on $(\mathbb{R}^{+},\mathcal{B}(\mathbb{R}^{+}))$ with finite and positive mean $\gamma= \int x \nu(dx)=\int x d\nu $. Then the distribution $\widehat{\nu}$ , defined by

\begin{equation*} \widehat{\nu}(B)=\dfrac{1}{\gamma}\int_{B} x \nu(dx), \;\; B\in \mathcal{B}(\mathbb{R}^{+}) \end{equation*} is called the size-biasing of $\nu$ or size-biased distribution associated with $\nu$. Given a random variable X with distribution $\nu$, any random variable $\widehat{X}$ with distribution $\widehat{\nu}$ is called a size-biasing of X.

Or the discrete case, you are usually familiar with this.If $X^{*}$ denotes the size-biasing of a random variable $X$ \begin{equation*} \mathbb{P}(X^{*}=k) = \dfrac{k \mathbb{P}(X=k)}{\mathbb{E}[X]} \end{equation*} now, $\textbf{Size-biased Galton-Watson trees: construction and properties:}$. Let $\Omega$ be the space of all trees. We now endow it with a sigma-algebra. For any $u \in \mathcal{U}$ , let $\Omega_{u}:=\lbrace w\in \Omega: u\in \omega \rbrace $ denote the subspace of $\Omega $ consisting of all the trees containing $u$ as a vertex. [In particular, $\Omega_{\varnothing}=\Omega$ because all the trees contain the root as a vertex.]The promised sigma-algebra associated with $\Omega$ is defined by \begin{equation*} \mathcal{F}:=\sigma\lbrace\Omega_{u},u\in \mathcal{U} \rbrace \end{equation*}

Let $\mathbb{T} :\Omega \rightarrow \Omega$ be the identity application. Let $(p_{k}, k \geq 0)$ be a probability. According to Neveu [1986], there exists a probability $\mathbb{P}$ on $\Omega$ such that the law of $\mathbb{T}$ under $\mathbb{P}$ is the law of the Galton–Watson tree with reproduction distribution $(p_{k})$. Let $\mathcal{F}_{n} := \sigma \lbrace u \in \mathcal{U}, |u|\leq n \rbrace $, where $|u|$ is the length of $u$ (representing the generation of the vertex u in the language of trees). Note that $\mathcal{F}$ is the smallest sigma-field containing every $\mathcal{F}_{n}$.

For any tree $\omega \in \Omega$ , let $Z_{n}(\omega)$ be the number of individuals in the $n$-th generation. It is easily checked that for any $n$, $Z_{n}$ is a random variable taking values in $\mathbb{N} := \lbrace 0,1,2 \ldots \rbrace$.

Let $\widehat{P}$ be the probability on ($\Omega,\mathcal{F} $) such that for any $n$ \begin{equation*} \widehat{P}_{|\mathcal{F}_{n}}= W_{n}\bullet\mathbb{P}_{|\mathcal{F}_{n}} \end{equation*} i.e. $\widehat{P}(A)=\int_{A}W_{n}d\mathbb{P}$ for any $A\in \mathcal{F}_{n}$. Here $\mathbb{P}_{|\mathcal{F}_{n}}$ and $\widehat{P}_{|\mathcal{F}_{n}}$ are restrictions of $\mathbb{P}$ and $\widehat{P} $ on $\mathcal{F}_{n}$, respectively. Since $W_{n}$ is a martingale, the existence of $\widehat{P}$ is guaranteed by Kolmogorov's extension theorem. For any $n$, \begin{equation*} \widehat{P}(Z_{n}>0)=\int_{\lbrace Z_{n}>0\rbrace}W_{n}d\mathbb{P}= \mathbb{E}[\mathbb{1}_{\lbrace Z_{n}>0\rbrace}W_{n}]=\mathbb{E}[W_{n}]=1 \end{equation*} Therefore, $\widehat{P}(Z_{n}>0, \forall n)=1 $. In other words, there is almost surely non-extinction of the Galton–Watson tree $\mathbb{T}$ under the new probability $\widehat{P}$. The Galton–Watson tree $\mathbb{T}$ under $\widehat{P}$ called a size-biased Galton-Watson tree ($\widehat{\textbf{GW}}$). Let us give a description of its paths.

Let $N:=N_{\emptyset}$. If $N\geq 1$, then there are N individuals in the first generation. We write $\mathbb{T}_{1}$, $\mathbb{T}_{2}$, $ \ldots$, $\mathbb{T}_{1}$ for the $N$ subtrees rooted at each of the $N$ individual in the first generation.

Let $k\geq 1$. If $A_{1},A_{2},\ldots, A_{k}$ are elements of $\mathcal{F}$, then \begin{equation} \widehat{P}(N=k, \mathbb{T}_{1}\in A_{1},\mathbb{T}_{2}\in A_{2},\ldots, \mathbb{T}_{k}\in A_{k})=\dfrac{kp_{k}}{m}\dfrac{1}{k}\sum_{i=1}^{k}\mathbb{P}(A_{1})\ldots\mathbb{P}(A_{i-1})\widehat{P}(A_{i})\mathbb{P}(A_{i+1})\ldots\mathbb{P}(A_{k}) \end{equation} This equation tells us the following fact about the size-biased Galton–Watson tree ($\widehat{\textbf{GW}}$): The root has the biased distribution, i.e., having $k$ children with probability $\frac{kp_{k}}{m}$ ($\mathbb{P}(X=k)=p_{k}$) ; among the individuals in the first generation, one of them is chosen randomly (according to the uniform distribution) such that the subtree rooted at this vertex is a size-biased Galton–Watson tree ($\widehat{\textbf{GW}}$), whereas the subtrees rooted at all other vertices in the first generation are independent copies of the usual Galton–Watson tree.

Iterating the procedure, we obtain a decomposition of the size-biased Galton–Watson tree ($\widehat{\textbf{GW}}$) with an (infinite) spine and with i.i.d. copies of the usual Galton–Watson tree: The root $\emptyset=:\omega_{0}$ which is viewed as the ancestor of a given population has the biased distribution, i.e., having k children with probability $\frac{kp_{k}}{m}$. Among the children of the root, one of them is chosen randomly (according to the uniform distribution) as the element of the spine in the first generation (denoted by $\omega_{1}$). We attach subtrees rooted at all other children; these subtrees are independent copies of the usual Galton– Watson tree. This vertex (individual) vertex $\omega_{1}$ has the biased distribution. We attach subtrees rooted at all other children; these subtrees are independent copies of the usual Galton– Watson tree. Among the children of $\omega_{1}$, we choose at random one of them as the element of the spine in the second generation (denoted by $\omega_{2}$). Independent copies of the usual Galton–Watson tree are attached as subtrees rooted at all other children of $\omega_{1}$, whereas $\omega_{2}$ has the biased distribution and so on. As a result, we obtain random tree $\widehat{\textbf{GW}}$ with distinguished infinite path (spine) $S=(\omega_{n})_{n\geq 1}$.

My struggle, I understood the proof Kesten-Stigum Theorem.However, my questions are 1.Why we take $\frac{kp_{k}}{m}$ instead, can we take $\frac{k^{2}p_{k}}{\mathbb{E}[X^{2}]}$ ? what makes it special. intuition, i know we can't take this otherwise $\mathbb{E}[Z\log Z ]$ characterization would be meaningless. i couldn't see any flaw in the theorem if i change $\frac{kp_{k}}{m}$ to $\frac{k^{2}p_{k}}{\mathbb{E}[X^{2}]}$
$\textbf{Thanks in advance. I am so sorry for taking your time.}$