Random Walk on Tree

Given a rooted tree, there is a coin on some node of the tree. At a certain moment, the coin moves to an adjacent node with equal probability. Find the expected distance for the coin to move to an adjacent node.

Required Definitions

\(T=(V,E)\): The tree under discussion
\(d(u)\): Degree of node \(u\)
\(w(u,v)\): Edge weight between node \(u\) and node \(v\)
\(p_u\): Parent node of node \(u\)
\(\textit{root}\): Root node of the tree
\(\textit{son}_u\): Set of child nodes of node \(u\)
\(\textit{sibling}_u\): Set of sibling nodes of node \(u\)

Expected Distance to Move to the Parent Node

Let \(f(u)\) denote the expected distance for node \(u\) to move to its parent node \(p_u\). Then:

\[ f(u) = \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v) + f(u))}{d(u)} \]

The first part of the numerator represents moving directly to the parent node, while the second part represents moving to a child node first, then moving back from that child node, and finally moving to the parent node. The denominator \(d(u)\) indicates that the probability of moving from node \(u\) to any of its adjacent nodes is equal.

Simplify as follows:

\[ \begin{aligned} f(u) &= \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v) + f(u))}{d(u)} \\ &= \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v)) + (d(u)-1)f(u)}{d(u)} \\ &= w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v)) \\ &= \sum\limits_{(u,t) \in E}w(u,t) + \sum\limits_{v \in \textit{son}_u}f(v) \end{aligned} \]

For a leaf node \(l\), the initial state is \(f(l) = w(p_l, l)\).

When all edge weights in the tree are \(1\), the above formula simplifies to:

\[ f(u) = d(u) + \sum\limits_{v \in \textit{son}_u}f(v) \]

This is the sum of the degrees of all nodes in the subtree of \(u\), which is also twice the size of the subtree of \(u\) minus \(1\) (each node has exactly one edge connecting to its parent, and except for the edge between \(u\) and \(p_u\), which contributes only \(1\) to the degree, every other edge contributes \(2\) to the degree).

Expected Distance to Move to a Child Node

Let \(g(u)\) denote the expected distance for node \(p_u\) to move to its child node \(u\). Then:

\[ g(u) = \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)+g(u))}{d(p_u)} \]

The first part of the numerator represents moving directly to the child node \(u\). The second part represents moving to the parent node first, then moving back from the parent node, and finally moving to node \(u\). The third part represents moving to a sibling node of \(u\) first, then moving back from that sibling node, and finally moving to node \(u\). The denominator \(d(p_u)\) indicates that the probability of moving from node \(p_u\) to any of its adjacent nodes is equal.

Simplify as follows:

\[ \begin{aligned} g(u) &= \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)+g(u))}{d(p_u)} \\ &= \cfrac{w(p_u,u) + w(p_u,p_{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}\left(w(p_u,s)+f(s)\right)+(d(p_u)-1)g(u)}{d(p_u)} \\ &= w(p_u,u) + w(p_u,p_{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)) \\ &= \sum\limits_{(p_u,t) \in E}w(p_u,t) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}f(s) \\ &= \sum\limits_{(p_u,t) \in E}w(p_u,t) + g(p_u) + \left(f(p_u)-\sum\limits_{(p_u,t) \in E}w(p_u,t)-f(u)\right) \\ &= g(p_u) + f(p_u) - f(u) \end{aligned} \]

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

Code Implementation (Example for 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);
  }
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用