Expected depth of a node in an arbitrary tree.

Question

I'm interested to see how the pointer jumping technique in parallel algorithms compares to sequential algorithms for finding the root of a given tree.

Specifically, I want to calculate the expected depth of random node in an arbitrary (random) tree of $n$ nodes. Suppose that the trees are labeled from $\{1,\dots, n\}$ and that thre are all rooted at $1$. I also suppose that the probability of picking a node is $\frac{1}{n}$ (uniform distribution) and the probability of picking a specific (labeled) tree $\frac{1}{n^{n-2}}$ (again uniformly distributed).

My first (and only) approach is the following (for simplicity I won't explain the symbols/notation I've used) $$ E[D] = \sum_{T\in\mathcal{T}_n}\sum_{v\in T}p_{\mathcal{T}}(T)p_{U|\mathcal{T}}(v\ |\ T)d(v) = \frac{1}{n^{n-1}}\sum_{T\in\mathcal{T}_n}\sum_{v\in T}d(v) $$

and since we're talking about labeled trees (suppose we label the nodes from $\{1,\dots, n\}$) $$=\frac{1}{n^{n-1}}\sum_{T\in\mathcal{T}_n}\sum_{v=1}^nd_T(v) = \frac{1}{n^{n-1}}\sum_{v=1}^n\sum_{T\in\mathcal{T}_n}d_T(v) $$

trying to continue the summation somehow... $$= \frac{1}{n^{n-1}}\sum_{v=1}^n \sum_{d=0}^{n-1} \sum_{T\in\mathcal{T}_n;\\d_T(v)=d}d_T(v) = \frac{1}{n^{n-1}}\sum_{v=1}^n \sum_{d=0}^{n-1} d\cdot\left|\left\{T\ |\ T\in\mathcal{T}_n,\ d_T(v) = d \right\}\right|$$

---

Obviously I don't know what I am doing. But I have no other ideas and I wanted to include some amount of work. Any hints, solutions or even ideas for different approaches are welcome.

Answer 1

Start by computing the internal path length of Cayley trees. We get from first principles the functional equation

$$T(z,u) = z \exp T(zu,u).$$

Here a term $u^q \frac{z^n}{n!}$ represents a tree on $n$ nodes having internal path length $q.$ We require

$$n! [z^n] \left. \frac{\partial}{\partial u} T(z, u) \right|_{u=1} = n! [z^n] F(z).$$

We get from the functional equation

$$\frac{\partial}{\partial u} T(z, u) = z \exp T(zu, u) \left( z \frac{\partial}{\partial z} T(z, u) (zu,u) + \frac{\partial}{\partial u} T(z, u) (zu,u) \right).$$

Using the tree function

$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}$$

we get evaluating at $u=1$

$$F(z) = z \exp T(z) ( z T'(z) + F(z) ) = T(z) ( z T'(z) + F(z) )$$

which implies that

$$F(z) = \frac{z T(z) T'(z)}{1-T(z)}.$$

Now using Lagrange inversion by residues (Egorychev method) we seek

$$n! [z^n] F(z) = n! [z^n] \frac{z T(z) T'(z)}{1-T(z)} = n! \;\underset{z}{\mathrm{res}}\; \frac{1}{z^n} \frac{T(z) T'(z)}{1-T(z)}.$$

Next put $T(z)=w$ to get with $z= w \exp(-w)$

$$n! \;\underset{w}{\mathrm{res}}\; \frac{\exp(nw)}{w^n} \frac{w}{1-w} = n! [w^{n-2}] \exp(nw) \frac{1}{1-w} = n! \sum_{q=0}^{n-2} \frac{n^q}{q!}.$$

It follows that the average depth of a node is is

$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{n^n} \sum_{q=0}^{n-2} \frac{n^q}{q!}.}$$

The above result can be verified using the combstruct package, see below. It appears that this one of the standard computations from the cookbook. The Maple code below will produce OEIS A001864, labeled as "total height of rooted trees with $n$ labeled nodes", so we have confirmation of the above starting at $n=2$:

$$2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888, \ldots.$$

with(combstruct);

cayley := {T=Prod(Z, Set(T))}:
cayley_ipl := {ipl(T)= Prod(0, Set(ipl(T)+size(T)))}:

Order := 13;

cayley_ipl_series :=
agfseries(cayley, cayley_ipl, labeled, z, [[u, ipl]])[T(z,u)]:

iplX := n -> n!*add(n^q/q!, q=0..n-2):

subs({u=1}, diff(cayley_ipl_series, u));
seq(iplX(n)/n!, n=0..Order-1);

seq(iplX(n), n=0..Order-1);

agfeqns(cayley, cayley_ipl, labeled, z, [[u, ipl]]);

Now supposing that these trees are always rooted at node one we require

$$(n-1)! [z^{n-1}] \left. \frac{\partial}{\partial u} \exp T(zu, u) \right|_{u=1} = (n-1)! [z^n] \left. \frac{\partial}{\partial u} z \exp T(zu, u) \right|_{u=1} \\ = (n-1)! [z^n] \left. \frac{\partial}{\partial u} T(z, u) \right|_{u=1} \\ = (n-1)! [z^n] F(z) = (n-1)! \sum_{q=0}^{n-2} \frac{n^q}{q!}.$$

The total number of structures is given by

$$(n-1)! [z^{n-1}] \exp T(z) = (n-1)! [z^n] z \exp T(z) = (n-1)! [z^n] T(z) \\ = (n-1)! \frac{n^{n-1}}{n!} = n^{n-2}$$

so the average is

$$\frac{(n-1)!}{n^{n-2}} \sum_{q=0}^{n-2} \frac{n^q}{q!}.$$

The total number of structures also follows by inspection -- if we always root the tree at node one the root marker always stays at the same node and we may as well not mark at all.

This sequence without the average points to OEIS A000435, apparently the sequence that started the OEIS.