In a rooted tree $$$T$$$, let $$$dep_u$$$ be the distance from $$$u$$$ to the root, $$$dis_u$$$ be the distance from $$$u$$$ to the deepest leaf in $$$u$$$'s subtree.
Let $$$f(T)=\sum_{u\in T} dep_u\times dis_u$$$.
Someone says that the expected number of $$$f(T)$$$ is $$$O(n\sqrt{n})$$$ when $$$T$$$ is uniformly randomly chosen from all $$$n$$$ vertices rooted trees.
How to prove it?
What is expected depth of the whole tree? I'm pretty sure it is $$$O(log^k n)$$$, so your sum is not bigger then approx. $$$O(n log^{2k} n)$$$The expected depth is $$$\mathcal{O}(\log n)$$$, but I don't think it proves that the above sum is limited by $$$\mathcal{O}(n \log^2 n)$$$.
Well, maybe it doesn't right away, but if $$$E[H^2] \le B$$$, then $$$\sum_{u} dep_{u} \cdot dis_{u} \le \sum_{u} dep_{u} \cdot (sz_{u} - 1)$$$, which is equal to number of ways to choose three vertices on one vertical path, which is $$$\sum_{u} \binom{dep_{u} - 1}{2}$$$, which is obviously bounded by $$$n E[H^2]$$$ in expectation.
I think that if riadwaw believed that expected height is polynomial in $$$\log n$$$, he also believed that any expected power of height is polynomial in $$$\log n$$$.UPD: Nevermind, that was really stupid assumption on my part, apologies to riadwaw.
No. The expected height is $$$\Theta(\sqrt n)$$$ when the tree is chosen uniformly randomly from the $$$n^{n-2}$$$ trees: https://doi.org/10.1017/S1446788700004432
My bad
I am slightly confused. Why is it different from the expected height of the treap? Does labelling change that much?
Yes, the labeling changes everything. And makes it really hard to analyze.
Creating a random tree is very different from just assigning random parents. That being said, I'm also surprised that the expected height or diameter isn't logarithmic
"Assigning random parents" is also different from treap, although in both cases the expected height is $$$\Theta(\log n)$$$ (not sure about treap, but for some reason, I believed some wise men who proved it and don't want to challenge my beliefs).
Is there some simple (the one written in the article doesn't count as simple for me) way to show for expected diameter to be $$$\Omega(\sqrt{n})$$$? to be $$$O(\sqrt{n})$$$?
I'm actually surprised its expectation is in $$$O(\sqrt{n})$$$! It's easy to show that the distribution of $$$\frac{d(1, 2)}{\sqrt{n}}$$$ converges to a distribution with pdf $$$x \mapsto x \cdot e^{-\frac{x^2}{2}}$$$. To do so, notice that there are $$$\binom{n-2}{k-1} \cdot (k-1)!$$$ possible paths of length $$$k$$$ between $$$1$$$ and $$$2$$$, and each of these paths appears in exactly $$$n^{n-k-2} \cdot (k+1)$$$ labeled trees. This latter formula can be proven in several ways, including by a slightly modified version of Prüfer sequences*. After a little re-arranging, the following proportionality drops out, from which the claimed limit is easy to recover:
*While there are at least $$$k+2$$$ vertices, remove the highest-index vertex which is a leaf and not on the path between $$$1$$$ and $$$2$$$, noting its parent. Then, when there are $$$k+2$$$ vertices, note the parent of the one vertex not on the path between $$$1$$$ and $$$2$$$. This produces a sequence of $$$n-k-1$$$ vertex numbers from $$$1$$$ to $$$n$$$, the last of which is on the path between $$$1$$$ and $$$2$$$. There are thus $$$n^{n-k-2}\cdot (k+1)$$$ such sequences, and every one corresponds to a unique labeled tree containing the path. Generally, the number of ways to merge $$$w$$$ components with sizes $$$s_i$$$ and total size $$$n$$$ is $$$n^{w-2} \prod s_i$$$.
Nice, thanks!
If anyone is interested, I remember a problem, which is probably based on that fact -- H from 2014-2015 ACM-ICPC Northeastern European Regional Contest (NEERC 14)
Yes, we did this problem today but we couldn't prove the time complexity of it.