A drunken person walks randomly on a tree. Each time, he chooses uniformly at random a neighbouring node and walks there. Show that wherever his starting point and goal are, the expected number of steps the person takes to reach the goal is always an integer. houkai
Problem
Source: IMOC 2021 C5
Tags: probability, expected value, combinatorics
15.08.2021 15:20
We prove it by induction. Let the tree graph be $G$ and the target vertex be $T$. Starting from a vertex $V$, let $E_G[V,T]$ be the expected number of steps to reach $T$. It's clear that the drunken man will reach $T$ almost surely, thus $E_G[V,T]$ is finite. If we delete $T$, the graph breaks into several components, and they are "uncorrelated" as we only care about the first time reaching $T$. Consider one component, say $G_1$, let the unique neighbor of $T$ in $G_1$ be $A$. Observe that for any other vertex $V$ in $G_1$, the drunken man should reach $A$ before reaching $T$, therefore $E_G[V,T]=E_{G_1}[V,A]+E_G[A,T]$. By induction hypothesis, $E_{G_1}[V,A]$ is an integer, so we only need to prove $E_G[A,T]$ is an integer. This is easy: just consider $\text{deg}(A)$ choices starting from $A$, \begin{align*} E_G[A,T]&=\frac{1}{\text{deg}_G(A)} \sum_{B \in N(A)} E_G[B,T] +1 \\ &= \frac{1}{\text{deg}_G(A)} \sum_{B \in N(A), B \neq T} \left( E_{G_1}[B,A]+E_G[A,T] \right) +1 \end{align*}Therefore, \[ E_G[A,T]=\text{deg}_G(A) + \sum_{B \in N(A), B \neq T} E_{G_1}[B,A], \]which is a integer by induction hypothesis.
16.08.2021 08:31
Aha, this is a part of a nice result about random walks on trees. An alternate (actually two) solution(s) to this problem have been discussed here. In fact all the binomial moments of this hitting times are integers. The second binomial moment have been discussed here.
05.01.2022 04:26
Let $\mathbb{E}_{a\to b}$ be the expected time a drunk person would go from vertex $a$ to $b$. Note $\mathbb{E}_{a\to b}\ne \mathbb{E}_{b\to a}$. Observation 1: if $u,v$ and $v,w$ are adjacent vertices, then $\mathbb{E}_{u\to w}=\mathbb{E}_{u\to v} + \mathbb{E}_{v\to w}$. Proof: From u, the drunken man needs to go to v to go to w because the path between any pair of vertices in a tree is unique. Let $T$ be the smallest counterexample. Let $L$ be a leaf. We know if $u,w\ne L$ then $\mathbb{E}_{u\to w}$ is an integer by deleting L. By Observation 1, we need to show if $v$ is the vertex adjacent to $L$ then $\mathbb{E}_{v\to L}$ is an integer. (Note $\mathbb{E}_{L\to v}=1$ ) Let $a$ be the expected value. Then $$a=\frac{1}{\deg(v)} \sum\limits_{u\in N(v), u\ne L} \mathbb{E}_{u\to L}+1$$ $$a=(\frac{1}{\deg(v)} \sum\limits_{u\in N(v), u\ne L} (a+\mathbb{E}_{u\to v}))+1$$ $$\deg(v)a=(\deg(v)-1)a + \deg(v)+\sum\limits_{u\in N(v), u\ne L} \mathbb{E}_{u\to v}$$ $$a=\deg(v)+\sum\limits_{u\in N(v), u\ne L} \mathbb{E}_{u\to v} \in \mathbb{Z}$$