I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, the set of $n$-vertices labeled rooted trees, and $c(v;t)$ be the number of children of vertex $v$ in a fixed tree $t$. Then $\Pi_n(c):=\frac{1}{n}\sharp\{u\in[n]:c(u;T_n)=c\}$ converges in probability to $\mathbb{P}(Poisson(1)=c)$.
In part (a) he proved that $c(1;T_n)$ converges in distribution to Poisson(1) distribution, which is clear to me using the so-called "line-breaking" construction in the lecture note. Then the above, as far as I'm concerned, is just a WLLN, so I want to check the Markov's condition:
$$\frac{1}{n^2}Var(\sum\limits_{u\in[n]}1(c(u;T_n)=c))\rightarrow 0.$$
However I am having problem controlling the "crossing-terms":
$$\frac{1}{n^2}\sum\limits_{u\not=v}[\mathbb{P}(c(u;T_n)=c(v;T_n)=c)-\mathbb{P}^2(c(u;T_n)=c)].$$
By line-breaking construction I can write out the probability of the first, by counting the number of labeled rooted trees with vertices 1 and 2 each has exactly c children:
\begin{aligned}
\mathbb{P}(c(1;T_n)=c(2;T_n)=c) &= \frac{\sharp\{t\in\mathcal{T}_n:c(1;t)=c(2;t)=c\}}{n^{n-1}}\\
&= \frac{\sharp\{v\in[n]^{n-1}:\text{ there are exactly }c\text{ copies of 1,2 in }v=(v_1,\cdots,v_{n-1})\}}{n^{n-1}}\\
&= \frac{1}{n^{n-1}}{n-1\choose c}{n-c-1\choose c}(n-2)^{n-2c-1}\\
&= \frac{1}{(c!)^2}(1-\frac{2}{n})^{n-2c-1}\mathop{\Pi}\limits_{k=1}^{2c}(1-\frac{k}{n}),
\end{aligned}
and the second probability, without the square, is(as proved in earlier context in the lecture note)
$$\mathbb{P}(c(1;T_n)=c)=\mathbb{P}(Bin(n-1,\frac{1}{n})=c)={n-1\choose c}\frac{1}{n^c}(1-\frac{1}{n})^{n-1-c}.$$
Then I have no idea how to bound the difference. Any help is appreciated.
Best Answer
Essentially, you want to show that $$p_{12}-p_1^2\to0,\tag{1}$$ where $$p_{12}:=P(c(1;T_n)=c(2;T_n)=c),\quad p_1:=P(c(1;T_n)=c).$$ We have $$p_1=\binom{n-1}c\frac1{n^c}\Big(1-\frac1n\Big)^{n-1-c} =\Big(1-\frac1n\Big)^{n-1-c}\frac1{c!}\prod_{j=1}^c\Big(1-\frac jn\Big)\to\frac{e^{-1}}{c!}.$$ If your calculation of $p_{12}$ were correct, then we would have $$p_{12} =\Big(1-\frac2n\Big)^{n-2c-1}\prod_{k=1}^{2c}\Big(1-\frac kn\Big)\to e^{-2},$$ so that (1) would fail to hold.
So, apparently the factor $1/(c!)^2$ is missing in your ultimate expression for $p_{12}$.