algorithm - 树中从根到叶子的预期最大路径长度

Question

假设，我们有一棵树，其中每条边的长度为 1 或 2 的概率相等。从根到叶子的所有路径都包含相同数量的边。找到从根到叶的预期最大路径长度。

树的例子

     *
    / \
   /   \
  *     *

预期最大路径长度为 1/4 * 1 + 3/4 * 2 = 7/4，因为边的可能长度为 11、12、21、22，后三个给出最大长度 2，第一个 - 1.

Answer 1

这可以递归计算而不会太麻烦。

"""
A distribution is represented as a list of probabilities summing to one.
The probability of outcome i is the entry at position i (zero-based indexing).
"""


def max_distribution(dist1, dist2):
    """
    Given two distributions dist1, dist2, computes the distribution of
    the max of a sample from dist1 and a sample from dist2.
    """
    max_dist = []
    cum1 = 0
    cum2 = 0
    for i in range(max(len(dist1), len(dist2))):
        p1 = dist1[i] if i < len(dist1) else 0
        p2 = dist2[i] if i < len(dist2) else 0
        max_dist.append(cum1 * p2 + p1 * cum2 + p1 * p2)
        cum1 += p1
        cum2 += p2
    return max_dist


def distribution_plus_edge(dist):
    """
    Given a distribution dist, computes the distribution of
    a sample from dist plus an uniform random choice in {1, 2}.
    """
    dist_plus = [0] * (len(dist) + 2)
    for i in range(len(dist)):
        for j in [1, 2]:
            dist_plus[i + j] += 0.5 * dist[i]
    return dist_plus


def expectation(dist):
    """
    Given a distribution dist, returns the expectation.
    """
    return sum(i * p for i, p in enumerate(dist))


def max_path_length_distribution(tree):
    """
    Given a tree represented as a list of the root's subtrees,
    computes the distribution of max path lengths from the root to a leaf.
    """
    dist = [1]
    for child in tree:
        child_dist = distribution_plus_edge(max_path_length_distribution(child))
        dist = max_distribution(dist, child_dist)
    return dist


tree = [[], []]
print(expectation(max_path_length_distribution(tree)))  # 1.75
tree = [[[], []], []]
print(expectation(max_path_length_distribution(tree)))  # 3.25