Total progeny of a Galton-Watson branching process - standard textbook question

Question

While analyzing some parallel-computing related algorithm, I came across a probability distribution with a particularly nice property (at least to me), but I am unable to write it down explicitly.

Let $X$ be a r.v., let $F_{X}(s)$ be its p.g.f., and let $$B_{d}(s)=\sum_{i=0}^{d}\binom{d}{i}\left(\frac{1}{d}\right)^{i}\left(1-\frac{1}{d}\right)^{d-i}s^{i}=\left(1-\frac{1}{d}+\frac{s}{d}\right)^{d}$$ be a p.g.f. of $\left(d,\frac{1}{d}\right)$-binomial distributed r.v. $b_{d}$, for any integer $d>1$. The distribution in question may be defined as $$F_{X}\left(s\right)=s\sum_{i=0}^{d}\binom{d}{i}\left(\frac{1}{d}\right)^{i}\left(1-\frac{1}{d}\right)^{d-i}F_{X}^{i}\left(s\right)=s\left(1-\frac{1}{d}+\frac{F_{X}\left(s\right)}{d}\right)^{d}.$$

The r.v. $X$ may be intuitively described as follows: A student arrives into town with $1$, and earns an additional $b_{d}$ each month. At the end of each month, she also pays a rent of $1$. The r.v. $X$ basically measures the time before our student is thrown out of the apartment.

If at some time the balance of our student is $k$, we expect her to stay for an additional $\sum_{i=1}^{k}X$ months (and this is independent of her past affairs). Also, the p.g.f. of $p$-geometric distribution $G_{p}$ is memoryless by the fact that

$$G_{p}(s)=s\cdot\text{Ber}_{p}\left(G_{p}\left(s\right)\right),$$

where $\text{Ber}_{p}$ is p.g.f. of $p$-Bernulli distributed r.v.. Similarly, in our case we can clearly write $F_{X}$ as

$$F_{X}\left(s\right)=s\cdot B_{d}\left(F_{X}\left(s\right)\right).$$

So far, I am only able to calculate (by derivation of $F_X$) that $\mathbb{E}(X)=\infty$, and also the first few coefficients of $F_X$, but I would be very interested in the precise description of $F_{X}$, either in a closed-form of p.g.f., or its coefficients, or cumulative distribution function of $X$.

Answer 1

The answer above is fine, nevertheless I make some hopefully useful supplementary remarks (the first two essentially reformulating Did's answer)

(1) It is well known (see e.g. Feller I, 3rd ed., p.299) that the generating function $r(s)$ of the total progeny in a Galton-Watson process (started with one individual) with reproduction function $h(s)$ is the unique positive solution of the implicit equation $$r(s)=s h(r(s))\;\;\;.$$ Your $X$ thus describes the total progeny of a GW-process with binomial reproduction $b_d(s)=(q+ps)^d$ in the ''critical'' case $p=\frac{1}{d}$.

(2) For $h(s)=b_d(s)$ the coefficients of $F_X(s)$ are (use Lagrange-inversion) $[s^0] F_X(s)=0$ and for $n\geq 1$

$$ [s^n] F_X(s)= \frac{1}{n} [t^{n-1}] (q+pt)^{nd}= \frac{1}{n} {nd \choose n-1} p^{n-1} q^{n(d-1)+1}=\frac{1}{nd+1}{nd+1 \choose n} p^{n-1} q^{n(d-1)+1}$$

(This is a (special) case of the Otter-Dwass formula.)

(3) The $d$-ary tree function $T_d(z)=\sum_{n\geq 0} \frac{1}{n(d-1)+1}{nd \choose n} z^n$ is the (formal) solution of the equation $$T_d(z)=1+z(T_d(z))^d$$ $T_d$ is known from combinatorics: the $n$-th coefficient of $T_d$ is the no. of $d-$ary trees with $n$ nodes. $F_X$ is related to $T_d$ as follows: $$F_X(s)=s\left(qT_d(spq^{d-1})\right)^d$$ Thus $X$ is distributed as $1+\sum_{i=1}^d Y_i$, where the $Y_i$ are iid with g.f. $g_Y(s)=qT_d(spq^{d-1})$

Answer 2

The random variable $X$ is distributed like the total progeny of a critical branching process $(Z_n)$ with binomial $(d,\frac1d)$ reproduction distribution, starting from $Z_0=1$. As such, indeed $E(X)$ is infinite.

The distribution of $X$ is known, the general formula being, for every $k\geqslant1$, $$P(X=k)=\frac1kP(Z_1=k-1\mid Z_0=k)$$ which in the present case yields $$P(X=k)=\frac1k{kd\choose k-1}\frac{(d-1)^{kd-k+1}}{d^{kd}}$$