Skip to main content
MathOverflow

Return to Question

removed capitals from title
Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Probability calculation of Rooted Treesrooted trees

deleted 3 characters in body
Source Link
swami
swami
  • 375
  • 1
  • 6

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the probabilitiesattributes of 2 or more of its subtrees?

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the probabilities of 2 or more of its subtrees?

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the attributes of 2 or more of its subtrees?

Source Link
swami
swami
  • 375
  • 1
  • 6

Probability calculation of Rooted Trees

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the probabilities of 2 or more of its subtrees?