Random Walks on Trees

A rooted tree is given, with a coin placed at one of its nodes. At each step, the coin moves to an adjacent node with equal probability. Find the expected distance traveled before the coin reaches an adjacent node.

Definitions

• $T=(V,E)$: the tree under consideration
• $d(u)$: the degree of node $u$
• $w(u,v)$: the weight of the edge between nodes $u$ and $v$
• $p_u$: the parent of node $u$
• $\textit{root}$: the root of the tree
• $\textit{son}_u$: the set of children of node $u$
• $\textit{sibling}_u$: the set of siblings of node $u$

Expected Distance to the Parent

Let $f(u)$ denote the expected distance for the walk starting at node $u$ to reach its parent $p_u$. Then:

The first part of the numerator corresponds to moving directly to the parent. The remaining part corresponds to first moving to a child, returning from that child, and then moving to the parent. The denominator $d(u)$ appears because every adjacent node of $u$ is chosen with the same probability.

The expression simplifies to:

For a leaf $l$, the initial value is $f(l) = w(p_l, l)$.

When every edge of the tree has weight $1$, this becomes:

This is the sum of the degrees of all nodes in the subtree of $u$, equivalently twice the size of the subtree rooted at $u$ $-1$ (each node has exactly one edge to its parent; except for the edge between $u$ and $p_u$, whose contribution is $1$, every edge contributes $2$ degrees).

Expected Distance to a Child

Let $g(u)$ denote the expected distance for the walk starting at the parent $p_u$ to reach its child $u$. Then:

The first part of the numerator corresponds to moving directly to child $u$. The second part corresponds to first moving to the parent, returning from it, and then moving to $u$. The third part corresponds to first moving to a sibling of $u$, returning from that sibling, and then moving to $u$. The denominator $d(p_u)$ appears because all adjacent nodes of $p_u$ are equally likely.

The expression simplifies to:

The initial value is $g(\text{root}) = 0$.

Implementation (for an unweighted tree)

vector<int> G[MAXN];

void dfs1(int u, int p) {
  f[u] = G[u].size();
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs1(v, u);
    f[u] += f[v];
  }
}

void dfs2(int u, int p) {
  if (u != root) g[u] = g[p] + f[p] - f[u];
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs2(v, u);
  }
}