Y25t's blog

By Y25t, history, 3 years ago, In English

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?

  • Vote: I like it
  • +52
  • Vote: I do not like it

»
3 years ago, # |
Rev. 4   Vote: I like it -20 Vote: I do not like 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)$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +91 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      My bad

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I am slightly confused. Why is it different from the expected height of the treap? Does labelling change that much?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Yes, the labeling changes everything. And makes it really hard to analyze.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +34 Vote: I do not like it

          "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).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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})$$$?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 5   Vote: I like it +45 Vote: I do not like it

        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:

        $$$ \displaystyle P(d(1, 2) = k) \propto (k+1) \cdot \prod_{i=1}^{k-1} \frac{n-i-1}{n} $$$

        *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$$$.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, we did this problem today but we couldn't prove the time complexity of it.