World's most popular travel blog for travel bloggers.

Expected number of common edges for a given tree with any other tree

, , No Comments
Problem Detail: 

So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To find the performance of my algorithm, I am trying to use the score as the fraction of edges that I have common in the generated tree and the given tree. I want to compare this score with an expected value of the fraction if we generate the tree randomly (equal probability for all tree structures). What should be my approach to find this? Is there a computable efficient method for this? The brute force method (with some optimizations so that I only iterate on the structure without the labels) usually fails over n>10.

I understand if there is some efficient method to find no. of trees with k common edges then my problem is solved to much extent, but I am having a hard time to solve this as well.

EDIT: The edges are considered to be directed, towards the root.

Asked By : arkanath

Answered By : Yuval Filmus

Let $T$ be your reference tree (on $n$ vertices), and let $R$ be the random tree. Label the edges of the tree randomly from $1$ to $n-1$. Let $X_i$ denote the event that the $i$th edge of $R$ is an edge of $T$. Linearity of expectation shows that the expected size of $T \cap R$ is $\sum_i \Pr[X_i]$. Each $X_i$ is a uniformly random edge, and so it belongs to $T$ with probability $|T|/\binom{n}{2} = 2/n$. Hence the expected size of the intersection is $(n-1) \cdot 2/n = 2(1-1/n)$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback